31 results
Now showing1 - 10 of 31
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Complexity of a root clustering algorithm for holomorphic functionsApproximating the roots of a holomorphic function in an input box is a fundamental problem in many domains. Most algorithms in the literature for solving this problem are conditional, i.e., they make some simplifying assumptions, such as, all the roots are simple or there are no roots on the boundary of the input box, or the underlying machine model is Real RAM. Root clustering is a generalization of the root approximation problem that allows for errors in the computation and makes no assumption on the multiplicity of the roots. An unconditional algorithm for computing a root clustering of a holomorphic function was given by Yap, Sagraloff and Sharma in 2013 [36]. They proposed a subdivision based algorithm using effective predicates based on Pellet's test while avoiding any comparison with zeros (using soft zero comparisons instead). In this paper, we analyze the running time of their algorithm. We use the continuous amortization framework to derive an upper bound on the size of the subdivision tree. We specialize this bound to the case of polynomials and some simple transcendental functions such as exponential and trigonometric sine. We show that the algorithm takes exponential time even for these simple functions, unlike the case of polynomials. We also derive a bound on the bit-precision used by the algorithm. To the best of our knowledge, this is the first such result for holomorphic functions. We introduce new geometric parameters, such as the relative growth of the function on the input box, for analyzing the algorithm. Thus, our estimates naturally generalize the known results, i.e., for the case of polynomials.Publicationtype: Journal Article23 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Addendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107](2019); Publicationtype: Journal Article81 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , On Fibonacci-type polynomial recurrences of order two and the accumulation points of their set of zeros(2018)We identify the accumulation points of the zero set of the polynomial family G n+1 (z):= zG n (z) + G n−1 (z), n ∈ N, generated from complex polynomial seeds G 0 , G 1 . This problem has been treated recently, for seed pairings of constants with linear polynomials, by Böttcher and Kittaneh (2016). We determine the accumulation points in the general case of arbitrary co-prime polynomial seeds, thus simplifying and streamlining previous approaches.Publicationtype: Journal Article113 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Near optimal subdivision algorithms for real root isolation(2017-11); Isolating real roots of a square-free polynomial in a given interval is a fundamental problem in computational algebra. Subdivision based algorithms are a standard approach to solve this problem. For instance, Sturm's method, or various algorithms based on the Descartes's rule of signs. For the benchmark problem of isolating all the real roots of a polynomial of degree n and root separation σ, the size of the subdivision tree of most of these algorithms is bounded by O(log1/σ) (assume σ<1). Moreover, it is known that this is optimal for subdivision algorithms that perform uniform subdivision, i.e., the width of the interval decreases by some constant. Recently Sagraloff (2012) and Sagraloff–Mehlhorn (2016) have developed algorithms for real root isolation that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O(n(log(nlog1/σ))). We describe a subroutine that reduces the size of the subdivision tree of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on either the Descartes's rule of signs or Sturm sequences is bounded by O(nlogn), which is close to the optimal value of O(n). The corresponding bound for the algorithm EVAL, which uses certain interval-arithmetic based predicates, is O(n2logn). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr–Krahmer–Yap (2009), and extend it to handle non-uniform subdivisions; second, we use the geometry of clusters of roots instead of root bounds. The latter aspect enables us to derive a bound on the subdivision tree that is independent of the root separation σ. The number of Newton iterations is bounded by O(nloglog(1/σ)).Publicationtype: Journal Article111 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Improvements of Lagrange's bound for polynomial roots(2017-09-01); ; An upper bound for the roots of Xd+a1Xd−1+⋯+ad−1X+ad is given by the sum of the largest two of the terms |ai|1/i. This bound by Lagrange has gained attention from different sides recently, while a succinct proof seems to be missing. We present a short, original proof of Lagrange's bound. Our approach leads to some definite improvements. To benefit computationally from these improvements, we construct a modified Lagrange bound which at the same asymptotic computational complexity is at most 11 per cent from optimal for degrees d≥16.Publicationtype: Journal Article143 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Componentwise products of totally non-negative matrices generated by functions in the Laguerre–Pólya classIn connection with the characterisation of real polynomials which have exclusively negative zeros Holtz and Tyaglov exposed in 2012 a new, totally non-negative, infinite matrix. This matrix resembles the matrices considered in the stability problem, and was called a matrix of “Hurwitz-type”. No precise connection to the Hurwitz matrices of the stability problem or structural properties could be established. We identify those matrices as limits of Hurwitz matrices generated by Hurwitz-stable polynomials. This allows to give a new and concise proof of the Holtz–Tyaglov characterisation as we connect it here to the classical theorem of Aissen, Edrei, Schoenberg and Whitney. Our approach naturally extends to entire functions in the Laguerre–Pólya class which have exclusively non-negative Taylor coefficients. Results on Hurwitz-stable polynomials are employed to show that certain positive pairs of real functions in the Laguerre–Pólya class generate totally non-negative matrices. Finally, we give the first composition result on the structured, infinite matrices considered: We show that the componentwise product of any of the considered infinite matrices is totally non-negative.Publicationtype: Conference Paper79 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , On the quality of some root-boundsBounds for the maximum modulus of all positive (or all complex) roots of a polynomial are a fundamental building block of algorithms involving algebraic equations. We apply known results to show which are the salient features of the Lagrange (real) root-bound as well as the related bound by Fujiwara. For a polynomial of degree n, we construct a bound of relative overestimation at most 1.72n which overestimates the Cauchy root by a factor of two at most. This can be carried over to the bounds by Kioustelidis and Hong. Giving a very short variant of a recent proof presented by Collins, we sketch a way to further definite, measurable improvement.Publicationtype: Conference Paper49 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Near optimal subdivision algorithms for real root isolationIsolating real roots of a square-free polynomial in a given interval is a fundamental problem. Subdivision based algorithms are a standard approach to solve this problem. E.g., Sturm's method, or various algorithms based on the Descartes's rule of signs. For isolating all the real roots of a degree n polynomial with root separation σ, the subdivision tree size of most of these algorithms is bounded by O(log 1/σ) (assume σ < 1). Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2013) have developed algorithms that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O(n(log(n log 1/σ))). Their algorithms and analysis crucially depend on the terminating predicates. We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on the Descartes's rule of signs is bounded by O(n log n). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and hence the analysis extends to other predicates; and second, we use the geometry of clusters of roots instead of root bounds.Publicationtype: Conference Paper28 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Deriving inequalities in the laguerre-pólya class from properties of half-plane mappingsNewton, Euler and many after them gave inequalities for real polynomials with only real zeros. We show how to extend classical inequalities ensuring a guaranteed minimal improvement. Our key is the construction of mappings with bounded image domains such that existing coefficient criteria from complex analysis are applicable. Our method carries over to the Laguerre-Pólya class 𝓛–𝓟 which contains real polynomials with exclusively real zeros and their uniform limits. The class 𝓛–𝓟 covers quasi-polynomials describing delay-differential inequalities as well as infinite convergent products representing entire functions, while it is at present not known whether the Riemann ξ-function belongs to this class. For the class 𝓛–𝓟 we obtain a new infinite family of inequalities which contains and generalizes the Laguerre-Turán inequalities.Publicationtype: Book Part51 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A family of necessary stability inequalities via quadratic formsInequalities relating three coefficients of the even or odd part of a Hurwitz-stable polynomial have been established recently via the Newton-MacLaurin inequalities, and via optimization techniques for multivariate functions on the positive orthant. From the theory of quadratic forms we derive a family of strict inequalities which includes and generalizes the known inequalities. For polynomials of higher degree quantifiable improvements are obtained. Benefit of these inequalities is low-cost instability testing for polynomials with varying coefficients. © by Element.Publicationtype: Journal Article34