Accurate solution of polynomial equations using Macaulay resultant matrices

Authors:
Guðbjörn F. Jónsson and Stephen A. Vavasis

Journal:
Math. Comp. **74** (2005), 221-262

MSC (2000):
Primary :, 13P10, 65F15.; Secondary :, 68W30

DOI:
https://doi.org/10.1090/S0025-5718-04-01722-3

Published electronically:
July 22, 2004

MathSciNet review:
2085409

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose an algorithm for solving two polynomial equations in two variables. Our algorithm is based on the Macaulay resultant approach combined with new techniques, including randomization, to make the algorithm accurate in the presence of roundoff error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundoff of the method, showing that with high probability the roots are computed accurately, assuming that the input data (that is, the two polynomials) are well conditioned. Our analysis requires a novel combination of algebraic and numerical techniques.

**1.**W. Auzinger and H. J. Stetter,*An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equation*, Numerical mathematics, Singapore 1988, ISNM vol. 86, Birkhäuser, 1988, pp. 11-30. MR**91g:65112****2.**L. Busé, M. Elkadi, and B. Mourrain,*Resultant over the residual of a complete intersection*, Journal of Pure and Applied Algebra**164**(2001), 35-57. MR**2002h:13042****3.**Arthur Cayley,*On the theory of elimination*, Cambridge and Dublin Math. J.**III**(1848), 116-120, Can also be found as Appendix B of [10].**4.**M. Chardin,*Multivariate subresultants*, Journal of Pure and Applied Algebra**101**(1995), 129-138. MR**96j:12002****5.**Robert M. Corless, Patrizia M. Gianni, and Barry M. Trager,*A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots*, ISSAC '97. Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (Wolfgang W. Küchlin, ed.), ACM Press, 1997, pp. 133-140.**6.**David Cox, John Little, and Donal O'Shea,*Using algebraic geometry*, Springer-Verlag, 1998. MR**99h:13033****7.**J. Dennis and R. Schnabel,*Numerical methods for unconstrained optimization and nonlinear equations*, SIAM, Philadelphia, 1996. MR**96i:90002****8.**Alan Edelman and H. Murakami,*Polynomial roots from companion matrix eigenvalues*, Math. Comp.**64**(1995), no. 210, 763-776. MR**95f:65075****9.**Ioannis Z. Emiris and Bernard Mourrain,*Matrices in elimination theory*, J. Symbolic Comput.**28**(1999), no. 1-2, 3-44. MR**2000h:68249****10.**I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky,*Discriminants, resultants, and multidimensional determinants*, Birkhäuser, 1994. MR**95e:14045****11.**Gene H. Golub and Charles F. Van Loan,*Matrix computations*, 3rd ed., John Hopkins University Press, 1996. MR**97g:65006****12.**I. S. Gradshteyn and I. M. Ryzhik,*Table of integrals, series, and products*, 5th ed., Academic Press, 1994. MR**97c:00014****13.**Ming Gu and Stanley C. Eisenstat,*Efficient algorithms for computing a strong rank-revealing QR factorization*, SIAM J. Sci. Comput.**17**(1996), no. 4, 848-869. MR**97h:65053****14.**Thomas Hawkins,*Another look at Cayley and the theory of matrices*, Arch. Internat. Historie Sci.**27**(1977), no. 100, 82-112. MR**58:10105****15.**G. Jónsson,*Eigenvalue methods for accurate solution of polynomial equations*, Ph.D. thesis, Center for Applied Mathematics, Cornell University, Ithaca, NY, 2001.**16.**G. F. Jónsson and S. A. Vavasis,*Solving polynomials with small leading coefficients*, to appear in SIAM J. Matrix Anal. Appl.**17.**T. Krick, L. Pardo, and M. Sombra,*Sharp estimates for the arithmetic nullstellensatz*, Duke Math. J.**109**(2001), 521-598. MR**2002h:11060****18.**T. Y. Li,*Numerical solutions of multivariate polynomial systems by homotopy continuation methods*, Acta Numerica**6**(1997), 399-436. MR**2000i:65084****19.**F. S. Macaulay,*On some formulæin elimination*, Proc. London Math. Soc.**35**(1902), 3-27.**20.**-,*The algebraic theory of modular systems*, Cambridge University Press, 1916.**21.**Dinesh Manocha and James Demmel,*Algorithms for intersecting parametric and algebraic curves I: Simple intersections*, ACM Trans. Graphics**13**(1994), no. 1, 73-100.**22.**Dinesh Manocha and Shankar Krishnan,*Solving algebraic systems using matrix computations*, SIGSAM Bulletin**30**(1996), no. 4, 4-21.**23.**Scott A. Mitchell and Stephen A. Vavasis,*Quality mesh generation in higher dimensions*, SIAM J. Computing**29**(2000), no. 4, 1334-1370. MR**2000m:65146****24.**Bernard Mourrain and Victor Y. Pan,*Multivariate polynomials, duality, and structured matrices*, J. Complexity**16**(2000), no. 1, 110-180. MR**2002c:15048****25.**J. Rosen, H. Park, and J. Glick,*Total least norm formulation and solution for structured problems*, SIAM J. Matrix Anal. App.**17**(1996), 110-126. MR**96m:65046****26.**M. Sombra,*Private email communication*, 2003.**27.**G. W. Stewart,*Perturbation theory for the generalized eigenvalue problem*, Recent Advances in Numerical Analysis (Carl de Boor and Gene H. Golub, eds.), Academic Press, 1978, pp. 193-206. MR**80c:65092****28.**Kim-Chuan Toh and Lloyd N. Trefethen,*Pseudozeros of polynomials and pseudospectra of companion matrices*, Numer. Math.**68**(1994), 403-425. MR**95m:65085****29.**B. L. van der Waerden,*Modern algebra*, vol. II, Frederick Ungar Publishing Co., 1950, English translation of Moderne Algebra, Springer-Verlag, Berlin, 1931.**30.**Paul Van Dooren and Patrick Dewilde,*The eigenstructure of an arbitrary polynomial matrix: Computational aspects*, Lin. Alg. Appl.**50**(1983), 545-579. MR**84j:15009****31.**Stephen A. Vavasis,*QMG: Software for finite-element mesh generation*, See`http://www.cs.cornell.edu/home/vavasis/qmg-home.html`, 1996.**32.**Layne T. Watson, Maria Sosonkina, Robert C. Melville, Alexander P. Morgan, and Homer F. Walker,*Algorithm 777. HOMPACK90: A suite of Fortran 90 codes for globally convergent homotopy algorithms*, ACM Trans. Math. Software**23**(1997), no. 4, 514-549.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
:,
13P10,
65F15.,
:,
68W30

Retrieve articles in all journals with MSC (2000): :, 13P10, 65F15., :, 68W30

Additional Information

**Guðbjörn F. Jónsson**

Affiliation:
Center for Applied Mathematics, Rhodes Hall, Cornell University, Ithaca, New York 14853

Address at time of publication:
deCODE Genetics, Lynghals 1, IS-110 Reykjavik, Iceland

Email:
gfj@decode.is

**Stephen A. Vavasis**

Affiliation:
Department of Computer Science, Upson Hall, Cornell University, Ithaca, New York 14853

Email:
vavasis@cs.cornell.edu

DOI:
https://doi.org/10.1090/S0025-5718-04-01722-3

Received by editor(s):
March 7, 2001

Received by editor(s) in revised form:
December 30, 2002

Published electronically:
July 22, 2004

Additional Notes:
This work was supported in part by NSF grants CCR-9619489 and EIA-9726388. Research also supported in part by NSF through grant DMS-9505155 and ONR through grant N00014-96-1-0050.

Article copyright:
© Copyright 2004
American Mathematical Society