Accurate Solution of Polynomial Equations Using Macaulay Resultant Matrices Export

@misc{citeulike:6095669, 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 roundo\# error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundo\# 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 Introduction In introductory linear algebra courses, eigenvalues of a matrix are computed by finding the roots of its characteristic polynomial. However, this is not how robust numerical eigenvalue algorithms work. The QR-algorithm, one of the major breakthroughs of scientific computing, computes the eigenvalues through an iteration of matrix factorizations. ...}, author = {J\'{o}nsson, Guðbj\"{o}rn and Vavasis, Stephen A.}, citeulike-article-id = {6095669}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.9156}, keywords = {algebraic, eigenvalue, generalized, geometry, macaulay, polynomial, polynomials, resultants, solving, system}, posted-at = {2009-11-10 19:05:26}, priority = {0}, title = {Accurate Solution of Polynomial Equations Using Macaulay Resultant Matrices}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.9156}, year = {2001} }

TY - ELEC ID - citeulike:6095669 L3 - citeulike-article-id:6095669 N2 - 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 roundo# error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundo# 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 Introduction In introductory linear algebra courses, eigenvalues of a matrix are computed by finding the roots of its characteristic polynomial. However, this is not how robust numerical eigenvalue algorithms work. The QR-algorithm, one of the major breakthroughs of scientific computing, computes the eigenvalues through an iteration of matrix factorizations. ... TI - Accurate Solution of Polynomial Equations Using Macaulay Resultant Matrices KW - algebraic KW - eigenvalue KW - generalized KW - geometry KW - macaulay KW - polynomial KW - polynomials KW - resultants KW - solving KW - system AU - Jónsson, Guðbjörn AU - Vavasis, Stephen PY - 2001/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.9156 ER -