research-article

Algorithm 931: An algorithm and software for computing multiplicity structures at zeros of nonlinear systems

Authors:

Andrew J. Sommese,

Zhonggang ZengAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 40, Issue 1

Article No.: 5, Pages 1 - 16

https://doi.org/10.1145/2513109.2513114

Published: 03 October 2013 Publication History

Abstract

A Matlab implementation, multiplicity, of a numerical algorithm for computing the multiplicity structure of a nonlinear system at an isolated zero is presented. The software incorporates a newly developed equation-by-equation strategy that significantly improves the efficiency of the closedness subspace algorithm and substantially reduces the storage requirement. The equation-by-equation strategy is actually based on a variable-by-variable closedness subspace approach. As a result, the algorithm and software can handle much larger nonlinear systems and higher multiplicities than their predecessors, as shown in computational experiments on the included test suite of benchmark problems.

Supplementary Material

ZIP File (931.zip)

Software for An algorithm and software for computing multiplicity structures at zeros of nonlinear systems

Download
28.45 KB

References

[1]

Bates, D., Hauenstein, J., Peterson, C., and Sommese, A. 2009. A numerical local dimension test for points on the solution set of a system of polynomial equations. SIAM J. Num. Anal. 47, 3608--3623.

Digital Library

[2]

Bates, D., Hauenstein, J., Sommese, A., and Wampler, C. 2010. Bertini: Software for numerical algebraic geometry. www.nd.edu/&sim; sommese/bertini.

[3]

Bates, D., Peterson, C., and Sommese, A. 2006. A numerical-symbolic algorithm for computing the multiplicity of a component of an algebraic set. J. Complexity 22, 475--489.

Digital Library

[4]

Dayton, B. H., Li, T.-Y., and Zeng, Z. 2011. Multiple zeros of nonlinear systems. Math. Comput. 80, 2143--2168.

[5]

Dayton, B. H. and Zeng, Z. 2005. Computing the multiplicity structure in solving polynomial systems. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC). ACM, New York, 116--123.

Digital Library

[6]

Decker, D. W., Keller, H. B., and Kelly, C. T. 1983. Convergence rate for Newton's method at singular points. SIAM J. Numer. Anal. 20, 296--314.

[7]

Duo, J., Shi, J., and Wang, Y. 2008. Structure of the solution set for a class of semilinear elliptic equations with asymptotic linear nonlinearity. Nonlinear Anal. 69, 8, 2369--2378.

[8]

Fulton, W. 1998. Intersection Theory. Springer-Verlag, Berlin.

[9]

Göttsche, L. 1994. Hilbert Schemes of Zero-Dimensional Subschemes of Smooth Varieties. Springer-Verlag, Berlin.

[10]

Griffin, Z., Hauenstein, J., Peterson, C., and Sommese, A. 2011. Numerical computation of the Hilbert function of a zero-scheme. http://www.math.nd.edu/&sim; sommeset/preprints.

[11]

Hauenstein, J. D. 2010. Algebraic computations using Macaulay dual spaces. http://www4.ncsu.edu/&sim; jhauenst/preprints/index.html.

[12]

Hauenstein, J. D. and Wampler, C. W. 2010. Isosingular sets and deflation. http://www4.ncsu.edu/&sim; jhauenst/preprints/index.html.

[13]

Kahan, W. 1972. Conserving confluence curbs ill-condition. Tech. rep. 6, Computer Science, University of California, Berkeley.

[14]

Leykin, A., Verschelde, J., and Zhao, A. 2006. Newton's method with deflation for isolated singularities of polynomial systems. Theor. Comp. Sci. 359, 111--122.

Digital Library

[15]

Macaulay, F. 1916. The Algebraic Theory of Modular Systems. CUP, Cambridge, UK.

[16]

Morgan, A. 1987. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice Hall Inc., Englewood Cliffs, NJ.

[17]

Morgan, A. P. and Sommese, A. J. 1989. Coefficient-parameter polynomial continuation. Appl. Math. Comput. 29, 2, 123--160. (Erratum: ibid., vol. 51, p. 207 (1992)).

Digital Library

[18]

Moritsugu, S. and Kuriyama, K. 1999. On multiple zeros of systems of algebraic equations. In Proceedings of the International Symposium on Symbolic and Algebraic Computation. (ISSAC). ACM, New York, 23--30.

Digital Library

[19]

Ojika, T. 1987. Modified deflation algorithm for the solution of singular problems.J. Math. Anal. Appl. 123, 199--221.

[20]

Stetter, H. J. 2004. Numerical Polynomial Algebra. EngineeringPro Collection, SIAM, Philadelphia, PA.

Digital Library

[21]

Sturmfels, B. 2002. Solving systems of polynomial equations. Regional Conference Series in Mathematics, vol. 97. AMS, Providence, RI.

[22]

Verschelde, J. 1996. Homotopy continuation methods for solving polynomial systems. Ph.D. thesis, Katholieke Universiteit Leuven.

[23]

Ward, J. R. 2005. Rotation numbers and global bifurcation in systems of ordinary differential equations. Adv. Nonlinear Stud. 5, 375--392.

[24]

Ward, J. R. 2007. Existence, multiplicity, and bifurcation in systems of ordinary differential equations. Electronic J. Diff. Eqns. 15, 399--415.

[25]

Zeng, Z. 2003. A method for computing multiple roots of inexact polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISAAC). ACM Press, New York, 266--272.

Digital Library

[26]

Zeng, Z. 2008. Apatools: A Maple and Matlab toolbox for approximate polynomial algebra. In Software for Algebraic Geometry, M. Stillman, N. Takayama, and J. Verschelde, Eds., Vol. 148, Springer, New York, 149--167.

[27]

Zeng, Z. 2009. The closedness subspace method for computing the multiplicity structure of a polynomial system. InInteractions of Classical and Numerical Algebraic Geometry, D. J. Bates, G. Besana, S. D. Rocco, and C. W. Wampler, Eds., Contemporary Mathematics, vol. 496, American Mathematics Society, Providence, RI, 347--362.

Cited By

Xu JWang DLu D(2024)Squarefree normal representation of zeros of zero-dimensional polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2023.102273122:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.jsc.2023.102273
Mantzaflaris AMourrain BSzanto A(2023)A certified iterative method for isolated singular rootsJournal of Symbolic Computation10.1016/j.jsc.2022.08.006115:C(223-247)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.08.006
Hao WZheng C(2022)Learn bifurcations of nonlinear parametric systems via equation-driven neural networksChaos: An Interdisciplinary Journal of Nonlinear Science10.1063/5.007830632:1Online publication date: 11-Jan-2022
https://doi.org/10.1063/5.0078306
Show More Cited By

Index Terms

Algorithm 931: An algorithm and software for computing multiplicity structures at zeros of nonlinear systems
1. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on polynomials
  2. Mathematical software

Recommendations

Numerical factorization of multivariate complex polynomials
Algebraic and numerical algorithm

One can consider the problem of factoring multivariate complex polynomials as a special case of the decomposition of a pure dimensional solution set of a polynomial system into irreducible components. The importance and nature of this problem however ...
Exact polynomial factorization by approximate high degree algebraic numbers
SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation

For factoring polynomials in two variables with rational coefficients, an algorithm using transcendental evaluation was presented by Hulst and Lenstra. In their algorithm, transcendence measure was computed. However, a constant c is necessary to compute ...
Nearest multivariate system with given root multiplicities

We present a symbolic-numeric technique to find the closest multivariate polynomial system to a given one which has roots with prescribed multiplicity structure. Our method generalizes the ''Weierstrass iteration'', defined by Ruatta, to the case when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 40, Issue 1

September 2013

165 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2513109

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 October 2013

Accepted: 01 September 2012

Revised: 01 June 2012

Received: 01 January 2012

Published in TOMS Volume 40, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Mathematical Sciences
Duncan Chair of the University of Notre Dame

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
286
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu JWang DLu D(2024)Squarefree normal representation of zeros of zero-dimensional polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2023.102273122:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.jsc.2023.102273
Mantzaflaris AMourrain BSzanto A(2023)A certified iterative method for isolated singular rootsJournal of Symbolic Computation10.1016/j.jsc.2022.08.006115:C(223-247)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.08.006
Hao WZheng C(2022)Learn bifurcations of nonlinear parametric systems via equation-driven neural networksChaos: An Interdisciplinary Journal of Nonlinear Science10.1063/5.007830632:1Online publication date: 11-Jan-2022
https://doi.org/10.1063/5.0078306
Hauenstein JRodriguez J(2020)Multiprojective witness sets and a trace testAdvances in Geometry10.1515/advgeom-2020-0006Online publication date: 17-Feb-2020
https://doi.org/10.1515/advgeom-2020-0006
Mantzaflaris AMourrain BSzanto AEmiris IZhi LMantzaflaris A(2020)Punctual Hilbert scheme and certified approximate singularitiesProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404024(336-343)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3404024
Cheng JDou XWen J(2020)A new deflation method for verifying the isolated singular zeros of polynomial systemsJournal of Computational and Applied Mathematics10.1016/j.cam.2020.112825376(112825)Online publication date: Oct-2020
https://doi.org/10.1016/j.cam.2020.112825
Hauenstein JMourrain BSzanto A(2017)On deflation and multiplicity structureJournal of Symbolic Computation10.1016/j.jsc.2016.11.01383(228-253)Online publication date: Nov-2017
https://doi.org/10.1016/j.jsc.2016.11.013
Romanovski VFernandes WOliveira R(2017)Bi-center problem for some classes of Z2-equivariant systemsJournal of Computational and Applied Mathematics10.1016/j.cam.2017.02.003320:C(61-75)Online publication date: 15-Aug-2017
https://dl.acm.org/doi/10.1016/j.cam.2017.02.003
Bourne MWinkler JSu Y(2017)A non-linear structure-preserving matrix method for the computation of the coefficients of an approximate greatest common divisor of two Bernstein polynomialsJournal of Computational and Applied Mathematics10.1016/j.cam.2017.01.035320:C(221-241)Online publication date: 15-Aug-2017
https://dl.acm.org/doi/10.1016/j.cam.2017.01.035
Batselier KWong N(2017)Inverse multivariate polynomial root-findingJournal of Computational and Applied Mathematics10.1016/j.cam.2017.01.034320:C(15-29)Online publication date: 15-Aug-2017
https://dl.acm.org/doi/10.1016/j.cam.2017.01.034
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents