Numerical Instability of Resultant Methods for Multidimensional Rootfinding
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...
| Główni autorzy: | , |
|---|---|
| Kolejni autorzy: | |
| Format: | Artykuł |
| Język: | en_US |
| Wydane: |
2016
|
| Dostęp online: | http://hdl.handle.net/1721.1/103587 |
| _version_ | 1826208142119141376 |
|---|---|
| author | Noferini, Vanni Townsend, Alex John |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Noferini, Vanni Townsend, Alex John |
| author_sort | Noferini, Vanni |
| collection | MIT |
| description | 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ézout) 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. |
| first_indexed | 2024-09-23T14:01:11Z |
| format | Article |
| id | mit-1721.1/103587 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:01:11Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | mit-1721.1/1035872022-10-01T18:38:21Z Numerical Instability of Resultant Methods for Multidimensional Rootfinding Noferini, Vanni Townsend, Alex John Massachusetts Institute of Technology. Department of Mathematics Townsend, Alex John 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ézout) 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. 2016-07-13T16:01:27Z 2016-07-13T16:01:27Z 2016-03 2016-01 Article http://purl.org/eprint/type/JournalArticle 0036-1429 1095-7170 http://hdl.handle.net/1721.1/103587 Noferini, Vanni, and Alex Townsend. “Numerical Instability of Resultant Methods for Multidimensional Rootfinding.” SIAM J. Numer. Anal. 54, no. 2 (January 2016): 719–743. © 2016, Society for Industrial and Applied Mathematics. en_US http://dx.doi.org/10.1137/15m1022513 SIAM Journal on Numerical Analysis Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf SIAM |
| spellingShingle | Noferini, Vanni Townsend, Alex John Numerical Instability of Resultant Methods for Multidimensional Rootfinding |
| title | Numerical Instability of Resultant Methods for Multidimensional Rootfinding |
| title_full | Numerical Instability of Resultant Methods for Multidimensional Rootfinding |
| title_fullStr | Numerical Instability of Resultant Methods for Multidimensional Rootfinding |
| title_full_unstemmed | Numerical Instability of Resultant Methods for Multidimensional Rootfinding |
| title_short | Numerical Instability of Resultant Methods for Multidimensional Rootfinding |
| title_sort | numerical instability of resultant methods for multidimensional rootfinding |
| url | http://hdl.handle.net/1721.1/103587 |
| work_keys_str_mv | AT noferinivanni numericalinstabilityofresultantmethodsformultidimensionalrootfinding AT townsendalexjohn numericalinstabilityofresultantmethodsformultidimensionalrootfinding |