Session B7 - Numerical Linear Algebra
July 15, 17:30 ~ 18:00 - Room B5
Numerical instability of algebraic-geometric methods to solve polynomial equations
University of Essex, United Kingdom - firstname.lastname@example.org
Among the existing algorithms to solve systems of polynomial equations, those based on algebraic geometry have particular relevance. In practice, they are often implemented either in a mixed symbolic-numeric environment, or purely in floating point arithmetic.
We focus on two important classes of methods, those based on resultant matrices and those based on Groebner bases. The common paradigm is to convert first the polynomial root-finding problem into a related eigenvalue problem, and then to find approximate solutions to the latter with standard, and reliable, numerical linear algebra algorithms. One can then recover an approximate solution to the original problem from the computed eigenvalues and eigenvectors. However, even if the conversion step is performed symbolically, the eigenvalue problem is potentially worse conditioned than the original problem. As a result, the polynomial system solver may be numerically unstable, even if the eigenvalue problem is formed without any approximation error and even it is then solved in a numerically stable manner.
This issue has been long known to practitioners. Here, we provide recent theoretical developments that quantitatively describe a worst-case spectacular increase of the condition number. We also comment on the difference between the various variants of these "numerical algebraic geometry" algorithms, discussing whether and how this effect can be mitigated when implementing these methods.
Joint work with Sujit Rao (Cornell University, United States) and Alex Townsend (Cornell University, United States).