Improved bounds on absolute positiveness of multivariate polynomials. (November 2020)

• Record Type: Journal Article
• Authors: Prabhakar, Swaroop N.; Sharma, Vikram
• Is Part Of: Journal of symbolic computation. Volume 101(2020)
• Page Start: 170
• Page End: 188
• Publication Date: 2020-11
• Subjects: Absolute positiveness -- Root bounds -- Range trees; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2019.07.025
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: A multivariate polynomial F ( x 1, x 2, …, x n ) is said to be absolutely positive from a real number B if F and all its partial derivatives are non-negative for x 1, x 2, …, x n ≥ B . One of the well known bounds on absolute positiveness in the literature is due to Hong. His bound is dependent on the largest number in a certain sequence of radicals defined using the absolute value of the coefficients of the polynomial. In the univariate setting, a bound due to Lagrange considers the first and the second largest numbers in the same radical sequence and is shown by Collins to be better than Hong's bound. In the 1930's, Westerfield had proposed a bound that considers every value in the same radical sequence and improves on Lagrange's bound. In this paper, we provide a hierarchy of bounds generalizing Westerfield's bound to the multivariate setting. One of the bounds in this hierarchy is a generalization of Lagrange's bound. All the bounds are strict quantitative improvements over Hong's bound. We also give an algorithm to compute the multivariate Lagrange bound. The running time of this algorithm matches the running time of the best known algorithm to compute Hong's bound. The algorithm uses the range tree data structure to implement orthogonal range querying. Relying on a result of Fredman (1984), we show that the efficiency of this algorithm cannot be improved by using any other data structure for orthogonal range querying.