Evaluation of Jacobian Matrices for Newton's Method with Deflation to approximate Isolated Singular Solutions of Polynomial Systems

Anton Leykin, Jan Verschelde, and Ailing Zhao

Abstract:

For isolated singular solutions of polynomial systems, we can restore the quadratic convergence of Newton's method by deflation. The number of deflation stages is bounded by the multiplicity of the root. A preliminary implementation performs well in case only a few deflation stages are needed, but suffers from expression swell as the number of deflation stages grows. In this paper we describe how a directed acyclic graph of derivative operators guides an efficient evaluation of the Jacobian matrices produced by our deflation algorithm. We illustrate how the symbolic-numeric deflation algorithm can be used within PHCmaple, interfacing Maple with PHCpack.

In Symbolic-Numeric Computation, edited by Dongming Wang and Lihong Zhi. Pages 269-278. Trends in Mathematics. Birkhäuser, 2007.