Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Regeneration homotopies for solving systems of polynomials


Authors: Jonathan D. Hauenstein, Andrew J. Sommese and Charles W. Wampler
Journal: Math. Comp. 80 (2011), 345-377
MSC (2010): Primary 65H10; Secondary 13P05, 14Q99, 68W30
DOI: https://doi.org/10.1090/S0025-5718-2010-02399-3
Published electronically: June 9, 2010
MathSciNet review: 2728983
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new technique, based on polynomial continuation, for solving systems of $ n$ polynomials in $ N$ complex variables. The method allows equations to be introduced one-by-one or in groups, obtaining at each stage a representation of the solution set that can be extended to the next stage until finally obtaining the solution set for the entire system. At any stage where positive dimensional solution components must be found, they are sliced down to isolated points by the introduction of hyperplanes. By moving these hyperplanes, one may build up the solution set to an intermediate system in which a union of hyperplanes ``regenerates'' the intersection of the component with the variety of the polynomial (or system of polynomials) brought in at the next stage. The theory underlying the approach guarantees that homotopy paths lead to all isolated solutions, and this capability can be used to generate witness supersets for solution components at any dimension, the first step in computing an irreducible decomposition of the solution set of a system of polynomial equations. The method is illustrated on several challenging problems, where it proves advantageous over both the polyhedral homotopy method and the diagonal equation-by-equation method, formerly the two leading approaches to solving sparse polynomial systems by numerical continuation.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65H10, 13P05, 14Q99, 68W30

Retrieve articles in all journals with MSC (2010): 65H10, 13P05, 14Q99, 68W30


Additional Information

Jonathan D. Hauenstein
Affiliation: Department of Mathematics, Mailstop 3368, Texas A&M University, College Station, Texas 77843
Email: jhauenst@math.tamu.edu

Andrew J. Sommese
Affiliation: Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, Indiana 46556
Email: sommese@nd.edu

Charles W. Wampler
Affiliation: General Motors Research and Development, Mail Code 480-106-359, 30500 Mound Road, Warren, Michigan 48090
Email: charles.w.wampler@gm.com

DOI: https://doi.org/10.1090/S0025-5718-2010-02399-3
Keywords: Algebraic set, component of solutions, diagonal homotopy, embedding, equation-by-equation solver, generic point, homotopy continuation, irreducible component, numerical irreducible decomposition, numerical algebraic geometry, path following, polynomial system, witness point
Received by editor(s): September 23, 2008
Received by editor(s) in revised form: July 24, 2009, and October 27, 2009
Published electronically: June 9, 2010
Additional Notes: The first author was supported by the Duncan Chair of the University of Notre Dame, the University of Notre Dame Center for Applied Mathematics, NSF Grant DMS-0410047, NSF Grant DMS-0712910, and the Fields Institute.
The second author was supported by the Duncan Chair of the University of Notre Dame, NSF Grant DMS-0410047, and NSF Grant DMS-0712910.
The third author was supported by NSF Grant DMS-0410047 and NSF Grant DMS-0712910.
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.