Numerical instability of resultant methods for multidimensional rootfinding. (English) Zbl 1382.65144
Summary: 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.
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 13P15 | Solving polynomial systems; resultants |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
References:
| [1] | E. L. Allgower, K. Georg, and R. Miranda, {\it The method of resultants for computing real solutions of polynomial systems}, SIAM J. Numer. Anal., 29 (1992), pp. 831-844. · Zbl 0756.65077 |
| [2] | J. Asakura, T. Sakurai, H. Tadano, T. Ikegami, and K. Kimura, {\it A numerical method for polynomial eigenvalue problems using contour integral}, Jpn. J. Ind. Appl. Math., 27 (2010), pp. 73-90. · Zbl 1204.65056 |
| [3] | D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, {\it Numerically Solving Polynomial Systems with Bertini}, Software Environ. Tools 25, SIAM, Philadelphia, 2013. · Zbl 1295.65057 |
| [4] | D. A. Bini and A. Marco, {\it Computing curve intersection by means of simultaneous iterations}, Numer. Algorithms, 43 (2006), pp. 151-175. · Zbl 1111.65019 |
| [5] | D. A. Bini and V. Noferini, {\it Solving polynomial eigenvalue problems by means of the Ehrlich-Aberth method}, Linear Algebra Appl., 439 (2013), pp. 1130-1149. · Zbl 1281.65061 |
| [6] | D. Bondyfalat, B. Mourrain, and V. Y. Pan, {\it Solution of a polynomial system of equations via the eigenvector computation}, Linear Algebra Appl., 319 (2000), pp. 193-209. · Zbl 0973.65038 |
| [7] | J. P. Boyd, {\it Computing zeros on a real interval through Chebyshev expansion and polynomial rootfinding}, SIAM J. Numer. Anal., 40 (2002), pp. 1666-1682. · Zbl 1034.65028 |
| [8] | J. P. Boyd, {\it Solving Transcendental Equations: The Chebyshev Polynomial Proxy and Other Numerical Rootfinders}, SIAM, Philadelphia, 2014. · Zbl 1311.65047 |
| [9] | B. Buchberger, {\it An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal}, J. Symbolic Comput., 41 (2006), pp. 475-511. · Zbl 1158.01307 |
| [10] | L. Busé, H. Khalil, and B. Mourrain, {\it Resultant-based methods for plane curves intersection problems}, in Computer Algebra in Scientific Computing, Lecture Notes in Comput. Sci. 3718, Springer, Berlin, 2005, pp. 75-92. · Zbl 1169.65316 |
| [11] | E. Cattani and A. Dickenstein, {\it Introduction to residues and resultants}, in {\it Solving Polynomial Equations. Foundations, Algorithms, and Applications}, A. Dickenstein and I. Z. Emiris, eds., Springer, New York, 2005. · Zbl 1152.14312 |
| [12] | A. Cayley, {\it On the theory of elimination}, Cambridge Dublin Math. J., 3 (1848), pp. 116-120. |
| [13] | E.-W. Chionh, M. Zhang, and R. N. Goldman, {\it Fast computation of the Bézout and Dixon resultant matrices}, J. Symbolic Comput., 33 (2002), pp. 13-29. · Zbl 0996.65046 |
| [14] | C. W. Clenshaw, {\it A note on the summation of Chebyshev series}, Math. Comput., 9 (1955), pp. 118-120. · Zbl 0065.05403 |
| [15] | D. A. Cox, J. Little, and D. O’Shea, {\it Using Algebraic Geometry}, Springer, New York, 2013. · Zbl 1079.13017 |
| [16] | F. De Teran, F. M. Dopico, and D. S. Mackey, {\it Fiedler companion linearizations and the recovery of minimal indices}, SIAM J. Math. Anal. Appl., 31 (2010), pp. 2181-2204. · Zbl 1205.15024 |
| [17] | P. Dreesen, K. Batselier, and B. De Moor, {\it Back to the roots: Polynomial system solving, linear algebra, systems theory}, in Proceedings of the 16th IFAC Symposium on System Identification (SYSID), 2012, pp. 1203-1208. |
| [18] | I. Z. Emiris, {\it Sparse Elimination and Applications in Kinematics}, Ph. D. dissertation, University of California, Berkeley, 1994. |
| [19] | I. Z. Emiris and V. Z. Pan, {\it Symbolic and numeric methods for exploiting structure in constructing resultant matrices}, J. Symbolic Comput., 33 (2002), pp. 393-413. · Zbl 1017.65049 |
| [20] | I. M. Gelfand, M. Kapranov, and A. Zelevinsky, {\it Discriminants, Resultants, and Multidimensional Determinants}, Birkhäuser, Boston, 2008. · Zbl 1138.14001 |
| [21] | L. Gemignani, and V. Noferini, {\it The Ehrlich-Aberth method for palindromic matrix polynomials represented in the Dickson basis}, Linear Algebra Appl., 438 (2013), pp. 1645-1666. · Zbl 1269.65034 |
| [22] | I. Gohberg, P. Lancaster, and L. Rodman, {\it Matrix Polynomials}, Classics in Appl. Math., SIAM, Philadelphia, 2009. |
| [23] | I. J. Good, {\it The colleague matrix, a Chebyshev analogue of the companion matrix}, Q. J. Math., 12 (1961), pp. 61-68. · Zbl 0103.01003 |
| [24] | N. J. Higham, {\it Accuracy and Stability of Numerical Algorithms}, 2nd ed., SIAM, Philadelphia, 2002. · Zbl 1011.65010 |
| [25] | N. J. Higham, {\it Function of Matrices: Theory and Computation}, SIAM, Philadelphia, 2008. · Zbl 1167.15001 |
| [26] | R. A. Horn, and C. R. Johnson, {\it Matrix Analysis}, 2nd ed., Cambridge University Press, New York, 2013. · Zbl 1267.15001 |
| [27] | G. Jónsson and S. Vavasis, {\it Accurate solution of polynomial equations using Macaulay resultant matrices}, Math. Comput., 74 (2005), pp. 221-262. · Zbl 1083.65052 |
| [28] | D. Kapur and T. Saxena, {\it Comparison of various multivariate resultant formulations}, in ACM Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1995. · Zbl 0916.65048 |
| [29] | F. C. Kirwan, {\it Complex Algebraic Curves}, Cambridge University Press, Cambridge, UK, 1992. · Zbl 0744.14018 |
| [30] | H. Li, {\it A simple solution to the six-point two-view focal-length problem}, proceedings of Computer Vision-ECCV, Springer, Berlin, 2006, pp. 200-213. |
| [31] | D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, {\it Vector spaces of linearizations for matrix polynomials}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 971-1004. · Zbl 1132.65027 |
| [32] | D. Manocha and J. F. Canny, {\it Multipolynomial resultants and linear algebra}, presented at International Symposium on Symbolic and Algebraic Computation, ACM, 1992. · Zbl 0920.65006 |
| [33] | D. Manocha and J. Demmel, {\it Algorithms for intersecting parametric and algebraic curves {\it I}: Simple intersections}, ACM Trans. Graphics, 13 (1994), pp. 73-100. · Zbl 0802.65147 |
| [34] | Y. Nakatsukasa, V. Noferini, and A. Townsend, {\it Vector spaces of linearizations for matrix polynomials: A bivariate polynomial approach}, submitted. · Zbl 1355.65058 |
| [35] | Y. Nakatsukasa, V. Noferini, and A. Townsend, {\it Computing the common zeros of two bivariate functions via Bézout resultants}, Numer. Math., 129 (2015), pp. 181-209. · Zbl 1308.65076 |
| [36] | S. Ragnarsson and C. F. Van Loan, {\it Block tensor unfoldings}, SIAM J. Math. Anal. Appl., 33 (2012), pp. 149-169. · Zbl 1246.15028 |
| [37] | M.-R. Skrzipek, {\it Polynomial evaluation and associated polynomials}, Numer. Math., 79 (1998), pp. 601-613. · Zbl 0909.65007 |
| [38] | A. J. Sommese and C. W. Wampler, {\it The Numerical Solution of Systems of Polynomials Arising in Engineering and Science}, World Scientific, Singapore, 2005. · Zbl 1091.65049 |
| [39] | L. Sorber, M. Van Barel, and L. De Lathauwer, {\it Numerical solution of bivariate and polyanalytic polynomial systems}, SIAM J. Numer. Anal., 52 (2014), pp. 1551-1572. · Zbl 1302.65135 |
| [40] | M. I. Syam, {\it Finding all real zeros of polynomial systems using multi-resultant}, J. Comput. Appl. Math., 167 (2004), pp. 417-428. · Zbl 1053.65039 |
| [41] | L. Taslaman, {\it An algorithm for quadratic eigenproblems with low rank damping}, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 251-272. · Zbl 1315.65039 |
| [42] | F. Tisseur, {\it Backward error and condition of polynomial eigenvalue problems}, Linear Algebra Appl., 309 (2000), pp. 339-361. · Zbl 0955.65027 |
| [43] | F. Tisseur and K. Meerbergen, {\it The quadratic eigenvalue problem}, SIAM Rev., 43 (2001), pp. 235-286. · Zbl 0985.65028 |
| [44] | A. Townsend, {\it Computing with Functions of Two Variables}, D.Phil. thesis, University of Oxford, 2014. |
| [45] | A. Townsend and L. N. Trefethen, {\it An extension of Chebfun to two dimensions}, SIAM J. Sci. Comput., 35 (2013), C495-C518. · Zbl 1300.65010 |
| [46] | J. Weiss, {\it Resultant methods for the inverse kinematics problem}, in Computational Kinematics, Solid Mech. Appl. 28, Springer, New York, 1993, pp. 41-52. · Zbl 0873.70003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
