Computing Isolated Singular Solutions of Polynomial Systems using Newton's Method with Deflation

Abstract:

Homotopy Continuation methods are well suited to approximate all isolated solutions of a polynomial system. As the Jacobian matrix at a multiple root is singular, Newton's method no longer converges and fails to deliver an approximate approximation. In the eighties, Ojika, Wanatabe, and Mitsui showed how to restore the quadratic convergence by repeated deflation. A symbolic deflation algorithm was developed more recently by Gregoire Lecerf.

In a joint work with Anton Leykin and Ailing Zhao, denoting the rank of the Jacobian matrix A by R, one deflation step adds R+1 multipliers, multiplied to R+1 random combinations of the columns of A to the system. We prove that the number of deflation steps needed to restore quadratic convergence is bounded by the multiplicity of the root. Our method depends on only one numerical tolerance: the one needed to determine the rank. Our preliminary implementations works well on many examples.

NCTS International Symposium on Dynamical Systems and Numerical Analysis in honor of Tien-Yien Li's 60th Birthday, May 10-12, 2005, National Center for Theoretical Sciences Mathematics Division, Taiwan.

slides of the talk