Numerical instability of resultant methods for multidimensional rootfinding
From MaRDI portal
Abstract: Hidden-variable resultant methods are a class of algorithms for solving multidimensional polynomial rootfinding problems. In two dimensions, when significant care is taken, they are competitive practical rootfinders. However, in higher dimensions they are known to miss zeros, calculate roots to low precision, and introduce spurious solutions. We show that the hidden variable resultant method based on the Cayley (Dixon or B'ezout) matrix is inherently and spectacularly numerically unstable by a factor that grows exponentially with the dimension. We also show that the Sylvester matrix for solving bivariate polynomial systems can square the condition number of the problem. In other words, two popular hidden variable resultant methods are numerically unstable, and this mathematically explains the difficulties that are frequently reported by practitioners. Regardless of how the constructed polynomial eigenvalue problem is solved, severe numerical difficulties will be present. Along the way, we prove that the Cayley resultant is a generalization of Cramer's rule for solving linear systems and generalize Clenshaw's algorithm to an evaluation scheme for polynomials expressed in a degree-graded polynomial basis.
Recommendations
Cites work
- A numerical method for polynomial eigenvalue problems using contour integral
- Accuracy and Stability of Numerical Algorithms
- Accurate solution of polynomial equations using Macaulay resultant matrices
- Algorithms for intersecting parametric and algebraic curves I
- An Algorithm for Quadratic Eigenproblems with Low Rank Damping
- An Extension of Chebfun to Two Dimensions
- Backward error and condition of polynomial eigenvalue problems
- Block tensor unfoldings
- Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
- Computation of a specified root of a polynomial system of equations using eigenvectors
- Computer Algebra in Scientific Computing
- Computing curve intersection by means of simultaneous iterations
- Computing the common zeros of two bivariate functions via Bézout resultants
- Computing Zeros on a Real Interval through Chebyshev Expansion and Polynomial Rootfinding
- Discriminants, resultants, and multidimensional determinants
- Fast computation of the Bézout and Dixon resultant matrices
- Fiedler companion linearizations and the recovery of minimal indices
- Finding all real zeros of polynomial systems using multi-resultant
- Functions of Matrices
- scientific article; zbMATH DE number 51877 (Why is no real title available?)
- scientific article; zbMATH DE number 1254250 (Why is no real title available?)
- scientific article; zbMATH DE number 1263357 (Why is no real title available?)
- scientific article; zbMATH DE number 1004889 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 3110365 (Why is no real title available?)
- Introduction to residues and resultants
- Numerical solution of bivariate and polyanalytic polynomial systems
- Numerically solving polynomial systems with Bertini
- Polynomial evaluation and associated polynomials
- Solving polynomial eigenvalue problems by means of the Ehrlich-Aberth method
- Solving transcendental equations. The Chebyshev polynomial proxy and other numerical rootfinders, perturbation series, and oracles
- Symbolic and numeric methods for exploiting structure in constructing resultant matrices
- THE COLLEAGUE MATRIX, A CHEBYSHEV ANALOGUE OF THE COMPANION MATRIX
- The Ehrlich-Aberth method for palindromic matrix polynomials represented in the Dickson basis
- The Method of Resultants for Computing Real Solutions of Polynomial Systems
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- The quadratic eigenvalue problem
- Using Algebraic Geometry
- Vector Spaces of Linearizations for Matrix Polynomials
- Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach
Cited in
(12)- Computing the homology of semialgebraic sets. II: General formulas
- High-order quadrature on multi-component domains implicitly defined by multivariate polynomials
- Analysis of normal-form algorithms for solving systems of polynomial equations
- Numerical stability of barycentric Hermite root-finding
- Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach
- Solving Singular Generalized Eigenvalue Problems. Part II: Projection and Augmentation
- Chebyshev subdivision and reduction methods for solving multivariable systems of equations
- Computing the homology of real projective sets
- Numerical instability of algebraic rootfinders
- A hidden variable resultant method for the polynomial multiparameter eigenvalue problem
- Symbolic mathematical computation 1965--1975. The view from a half-century perspective
- Symbolic mathematical computation 1965--1975: the emergence of a discipline
This page was built for publication: Numerical instability of resultant methods for multidimensional rootfinding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796860)
