TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Fri, 09 Jun 2023 22:39:41 GMT2023-06-09T22:39:41Z50301- Near optimal subdivision algorithms for real root isolationhttp://hdl.handle.net/11420/7829Title: Near optimal subdivision algorithms for real root isolation
Authors: Sharma, Vikram; Batra, Prashant
Abstract: Isolating 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.
Wed, 24 Jun 2015 00:00:00 GMThttp://hdl.handle.net/11420/78292015-06-24T00:00:00Z
- Some applications of complex analysis to questions of stability and stabilizabilityhttp://hdl.handle.net/11420/8863Title: Some applications of complex analysis to questions of stability and stabilizability
Authors: Batra, Prashant
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11420/88632006-01-01T00:00:00Z
- On Goldberg's constant A2http://hdl.handle.net/11420/8654Title: On Goldberg's constant A2
Authors: Batra, Prashant
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11420/86542007-01-01T00:00:00Z
- Addendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107]http://hdl.handle.net/11420/5276Title: Addendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107]
Authors: Rump, Siegfried M.; Batra, Prashant
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/52762019-01-01T00:00:00Z
- Globally convergent, iterative path-following for algebraic equationshttp://hdl.handle.net/11420/8532Title: Globally convergent, iterative path-following for algebraic equations
Authors: Batra, Prashant
Abstract: Homotopy methods are of great importance for the solution of systems of equations. It is a major problemto ensure well-defined iterations along the homotopy path. Many investigations have considered the complexityof path-following methods depending on the unknown distance of some given path to the variety of ill-posed problems. It is shown here that there exists a construction method for safe paths for a single algebraic equation. A safepath may be effectively determined with bounded effort. Special perturbation estimates for the zeros together withconvergence conditions for Newton's method in simultaneous mode allow our method to proceed on the safe path. This yields the first globally convergent, never-failing, uniformly iterative path-following algorithm. The maximumnumber of homotopy steps in our algorithm reaches a theoretical bound forecast by Shub and Smale i. e., the numberof steps is at most quadratic in the condition number. A constructive proof of the fundamental theorem of algebrameeting demands by Gauß, Kronecker and Weierstraß is a consequence of our algorithm.
Wed, 01 Dec 2010 00:00:00 GMThttp://hdl.handle.net/11420/85322010-12-01T00:00:00Z
- On upper bounds for real proportional stabilising controllershttp://hdl.handle.net/11420/8723Title: On upper bounds for real proportional stabilising controllers
Authors: Batra, Prashant
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/11420/87232003-01-01T00:00:00Z
- On necessary conditions for real robust Schur-stabilityhttp://hdl.handle.net/11420/8725Title: On necessary conditions for real robust Schur-stability
Authors: Batra, Prashant
Abstract: A coefficient diameter of real Schur-stable interval polynomials is bounded using meromorphic functions. The resulting bound is the best possible. A known bound for the ratio of the two leading coefficients is improved for large diameters.
Sat, 01 Feb 2003 00:00:00 GMThttp://hdl.handle.net/11420/87252003-02-01T00:00:00Z
- Value-restricted functions for robust and simultaneous stabilityhttp://hdl.handle.net/11420/8684Title: Value-restricted functions for robust and simultaneous stability
Authors: Batra, Prashant
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11420/86842005-01-01T00:00:00Z
- Simultaneous point estimates for Newton's methodhttp://hdl.handle.net/11420/8918Title: Simultaneous point estimates for Newton's method
Authors: Batra, Prashant
Abstract: Beside the classical Kantorovich theory there exist convergence criteria for the Newton iteration which only involve data at one point, i.e. point estimates. Given a polynomial P, these conditions imply the point evaluation of n = deg(P) functions (from a certain Taylor expansion). Such sufficient conditions ensure quadratic convergence to a single zero and have been used by several authors in the design and analysis of robust, fast and efficient root-finding methods for polynomials. In this paper a sufficient condition for the simultaneous convergence of the one-dimensional Newton iteration for polynomials will be given. The new condition involves only n point evaluations of the Newton correction and the minimum mutual distance of approximations to ensure "simultaneous" quadratic convergence to the pairwise distinct n roots.
Sun, 01 Sep 2002 00:00:00 GMThttp://hdl.handle.net/11420/89182002-09-01T00:00:00Z
- On coefficient diameters of real schur-stable interval polynomialshttp://hdl.handle.net/11420/8703Title: On coefficient diameters of real schur-stable interval polynomials
Authors: Batra, Prashant
Abstract: A new necessary, sharp condition for Schur-stability of real interval polynomials is established here. Moreover, a way to study perturbation effects on the coefficient range is outlined. The results may be used in a preprocessing rejection scheme when testing for robust Schur-stability.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/11420/87032003-01-01T00:00:00Z
- Deriving inequalities in the laguerre-pólya class from properties of half-plane mappingshttp://hdl.handle.net/11420/7889Title: Deriving inequalities in the laguerre-pólya class from properties of half-plane mappings
Authors: Batra, Prashant
Abstract: Newton, 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.
Tue, 28 Feb 2012 00:00:00 GMThttp://hdl.handle.net/11420/78892012-02-28T00:00:00Z
- Real interpolating units via positive functionshttp://hdl.handle.net/11420/8938Title: Real interpolating units via positive functions
Authors: Batra, Prashant
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/11420/89382004-01-01T00:00:00Z
- Abschätzungen und Iterationsverfahren für Polynom-Nullstellenhttp://hdl.handle.net/11420/9354Title: Abschätzungen und Iterationsverfahren für Polynom-Nullstellen
Authors: Batra, Prashant
Fri, 01 Jan 1999 00:00:00 GMThttp://hdl.handle.net/11420/93541999-01-01T00:00:00Z
- On small circles containing zeros and ones of analytic functionshttp://hdl.handle.net/11420/9633Title: On small circles containing zeros and ones of analytic functions
Authors: Batra, Prashant
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/11420/96332004-01-01T00:00:00Z
- Omitted values and real robust schur stabilityhttp://hdl.handle.net/11420/9629Title: Omitted values and real robust schur stability
Authors: Batra, Prashant
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/11420/96292001-01-01T00:00:00Z
- On small circles containing zeros and ones of analytic functionshttp://hdl.handle.net/11420/8919Title: On small circles containing zeros and ones of analytic functions
Authors: Batra, Prashant
Abstract: Gol'dberg considered the class of functions with unequal positive numbers of zeros and ones inside the unit disc. The maximum modulus of zeros and ones in this class is bounded from below by a universal constant. This constant determines the limits of certain controller designs as well as covering regions of certain composites with schlicht functions. Considering lower bounds in a zero-free region of the extremal function the best known estimates of this constant are improved.; Gol'dberg considered the class of functions with unequal positive numbers of zeros and ones inside the unit disc. The maximum modulus of zeros and ones in this class is bounded from below by a universal constant. This constant determines the limits of certain controller designs as well as covering regions of certain composites with schlicht functions. Considering lower bounds in a zero-free region of the extremal function the best known estimates of this constant are improved.
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/11420/89192004-01-01T00:00:00Z
- On Fibonacci-type polynomial recurrences of order two and the accumulation points of their set of zeroshttp://hdl.handle.net/11420/2193Title: On Fibonacci-type polynomial recurrences of order two and the accumulation points of their set of zeros
Authors: Batra, Prashant
Abstract: 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.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/11420/21932018-01-01T00:00:00Z
- Componentwise products of totally non-negative matrices generated by functions in the Laguerre–Pólya classhttp://hdl.handle.net/11420/4779Title: Componentwise products of totally non-negative matrices generated by functions in the Laguerre–Pólya class
Authors: Batra, Prashant
Abstract: In 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.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11420/47792017-01-01T00:00:00Z
- On the quality of some root-boundshttp://hdl.handle.net/11420/6290Title: On the quality of some root-bounds
Authors: Batra, Prashant
Abstract: Bounds 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.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11420/62902016-01-01T00:00:00Z
- Newton's method and the computational complexity of the fundamental theorem of algebrahttp://hdl.handle.net/11420/2925Title: Newton's method and the computational complexity of the fundamental theorem of algebra
Authors: Batra, Prashant
Abstract: Several different uses of Newton's method in connection with the Fundamental Theorem of Algebra are pointed out. Theoretical subdivision schemes have been combined with the numerical Newton iteration to yield fast root-approximation methods together with a constructive proof of the fundamental theorem of algebra. The existence of the inverse near a simple zero may be used globally to convert topological methods like path-following via Newton's method to numerical schemes with probabilistic convergence. Finally, fast factoring methods which yield root-approximations are constructed using some algebraic Newton iteration for initial factor approximations. © 2008 Elsevier B.V. All rights reserved.
Fri, 21 Mar 2008 00:00:00 GMThttp://hdl.handle.net/11420/29252008-03-21T00:00:00Z
- Improvements of Lagrange's bound for polynomial rootshttp://hdl.handle.net/11420/3857Title: Improvements of Lagrange's bound for polynomial roots
Authors: Batra, Prashant; Mignotte, Maurice; Ştefănescu, Doru
Abstract: 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.
Fri, 01 Sep 2017 00:00:00 GMThttp://hdl.handle.net/11420/38572017-09-01T00:00:00Z
- Near optimal subdivision algorithms for real root isolationhttp://hdl.handle.net/11420/3775Title: Near optimal subdivision algorithms for real root isolation
Authors: Batra, Prashant; Sharma, Vikram
Abstract: 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/σ)).
Wed, 01 Nov 2017 00:00:00 GMThttp://hdl.handle.net/11420/37752017-11-01T00:00:00Z
- Bounds on absolute positiveness of multivariate polynomialshttp://hdl.handle.net/11420/3922Title: Bounds on absolute positiveness of multivariate polynomials
Authors: Batra, Prashant; Sharma, Vikram
Abstract: We propose and study a weighting framework for obtaining bounds on absolute positiveness of multivariate polynomials. It is shown that a well-known bound BG by Hong is obtainable in this framework, and w.r.t. any bound in this framework BG has a multiplicative overestimation which is at most linear in the number of variables. We also propose a general method to algorithmically improve any bound within the framework. In the univariate case, we derive the minimum number of weights necessary to obtain a bound with limited overestimation w.r.t. the absolute positiveness of the polynomial. © 2010 Elsevier Ltd.
Tue, 01 Jun 2010 00:00:00 GMThttp://hdl.handle.net/11420/39222010-06-01T00:00:00Z
- Necessary stability conditions for differential-difference systemshttp://hdl.handle.net/11420/8851Title: Necessary stability conditions for differential-difference systems
Authors: Batra, Prashant
Tue, 23 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11420/88512007-01-23T00:00:00Z
- Subordination and stabilization of plant familieshttp://hdl.handle.net/11420/8864Title: Subordination and stabilization of plant families
Authors: Batra, Prashant
Abstract: We introduce a new tool for the analysis of robust stability and simultaneous stabilizability questions. By a single approach we derive limits for controller parameters in low-order synthesis schemes as well as constraints for unit interpolation problems. Especially, we answer a question by Vijay V. Patel on stabilization of three special systems.
Sat, 01 Jul 2006 00:00:00 GMThttp://hdl.handle.net/11420/88642006-07-01T00:00:00Z
- On upper bounds for real proportional stabilizing controllershttp://hdl.handle.net/11420/8862Title: On upper bounds for real proportional stabilizing controllers
Authors: Batra, Prashant
Abstract: The explicit determination of the largest admissible constant controller is difficult. For linear systems with all poles in the domain of stability but at least one non-minimum phase zero outside, an improved upper bound on real proportional gain controllers is given. Examples show the improvement and further possible margins. © 2006 WILEY-VCH Verlag GmbH & Co. KGaA,.
Fri, 16 Dec 2005 00:00:00 GMThttp://hdl.handle.net/11420/88622005-12-16T00:00:00Z
- A family of necessary stability inequalities via quadratic formshttp://hdl.handle.net/11420/7924Title: A family of necessary stability inequalities via quadratic forms
Authors: Batra, Prashant
Abstract: Inequalities 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.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11420/79242011-01-01T00:00:00Z
- Bound for all coefficient diameters of real Schur-stable interval polynomialshttp://hdl.handle.net/11420/8920Title: Bound for all coefficient diameters of real Schur-stable interval polynomials
Authors: Batra, Prashant
Abstract: A sharp diameter bound for all coefficient intervals of real robustly Schur-stable polynomials is established. The results may be used in a preprocessing rejection scheme when testing for robust Schur-stability. © 2004 IEEE.
Fri, 01 Oct 2004 00:00:00 GMThttp://hdl.handle.net/11420/89202004-10-01T00:00:00Z
- A property of the nearly optimal root-boundhttp://hdl.handle.net/11420/7831Title: A property of the nearly optimal root-bound
Authors: Batra, Prashant
Abstract: The importance of root-bounds for practical and theoretical algorithms for polynomial root-approximation is well-known. The root-bound by Fujiwara was shown to be near optimal by van der Sluis, and is the most often used in practice. We show here that this bound always compares favorably with Kojima's bound, a question left open in the work of van der Sluis. © 2003 Elsevier B.V. All rights reserved.
Fri, 13 Feb 2004 00:00:00 GMThttp://hdl.handle.net/11420/78312004-02-13T00:00:00Z
- Improvement of a convergence condition for the Durand-Kerner iterationhttp://hdl.handle.net/11420/8888Title: Improvement of a convergence condition for the Durand-Kerner iteration
Authors: Batra, Prashant
Abstract: The Durand-Kerner iteration is a well-known simultaneous method for approximation of (simple) zeros of a polynomial. By relating Weierstrass' correction and the minimal distance between approximations practical conditions for convergence have been obtained. These conditions also ensure the existence of isolating discs for the polynomial roots, i.e. each iteration step gives a refined set of inclusion discs. In this paper refined conditions of convergence are given. © 1998 Elsevier Science B.V. All rights reserved.
Tue, 15 Sep 1998 00:00:00 GMThttp://hdl.handle.net/11420/88881998-09-15T00:00:00Z