More Web Proxy on the site http://driver.im/

research-article

A certified iterative method for isolated singular roots

Authors:

Angelos Mantzaflaris,

Bernard Mourrain,

Agnes SzantoAuthors Info & Claims

Volume 115, Issue C

Pages 223 - 247

https://doi.org/10.1016/j.jsc.2022.08.006

Published: 01 March 2023 Publication History

Abstract

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system f = ( f 1, …, f N ) ∈ C [ x 1, …, x n ] N, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.

References

[1]

T. Ayyildiz Akoglu, J.D. Hauenstein, A. Szanto, Certifying solutions to overdetermined and singular polynomial systems over Q, J. Symb. Comput. 84 (2018) 147–171.

[2]

D. Bejleri, D. Stapleton, The tangent space of the punctual Hilbert scheme, Mich. Math. J. 66 (3) (Aug. 2017) 595–610.

[3]

L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, NY, 1998.

[4]

J. Briançon, Description de H i l b n C { x, y }, Invent. Math. 41 (1977) 45–90.

[5]

J. Briançon, A. Iarrobino, Dimension of the punctual Hilbert scheme, J. Algebra 55 (2) (1978) 536–544.

[6]

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

[7]

B.H. Dayton, Z. Zeng, Computing the multiplicity structure in solving polynomial systems, in: Proc. of ISSAC '05, NY, USA, 2005, ACM, 2005, pp. 116–123.

[8]

J.-P. Dedieu, M. Shub, On simple double zeros and badly conditioned zeros of analytic functions of n variables, Math. Comput. 70 (233) (2001) 319–327.

[9]

P. Doubilet, G.-C. Rota, J. Stein, On the foundations of combinatorial theory, Stud. Appl. Math. 53 (3) (1974) 185–216.

[10]

I.Z. Emiris, B. Mourrain, E. Tsigaridas, The DMM bound: multivariate (aggregate) separation bounds, in: S. Watt (Ed.), Proceedings of the ISSAC’10, Munich, Germany, July 2010, ACM, 2010, pp. 243–250.

[11]

M. Giusti, G. Lecerf, B. Salvy, J.-C. Yakoubsohn, On location and approximation of clusters of zeros of analytic functions, Found. Comput. Math. 5 (3) (2005) 257–311.

[12]

M. Giusti, G. Lecerf, B. Salvy, J.-C. Yakoubsohn, On location and approximation of clusters of zeros: case of embedding dimension one, Found. Comput. Math. 7 (2007) 1–58.

[13]

M. Giusti, J.-C. Yakoubsohn, Multiplicity hunting and approximating multiple roots of polynomial systems, Contemp. Math. 604 (2013) 105–128.

[14]

M. Giusti, J.-C. Yakoubsohn, Approximation numérique de racines isolées multiples de systèmes analytiques, Ann. Henri Lebesgue 3 (2020) 901–957,.

[15]

W. Hao, A.J. Sommese, Z. Zeng, Algorithm 931: an algorithm and software for computing multiplicity structures at zeros of nonlinear systems, ACM Trans. Math. Softw. 40 (1) (2013).

[16]

J.D. Hauenstein, B. Mourrain, A. Szanto, On deflation and multiplicity structure, J. Symb. Comput. 83 (2016) 228–253.

[17]

J.D. Hauenstein, F. Sottile, Algorithm 921: alphaCertified: certifying solutions to polynomial systems, ACM Trans. Math. Softw. 38 (4) (2012).

Digital Library

[18]

A.A. Iarrobino, Punctual Hilbert Schemes, Memoirs of the American Mathematical Society, vol. 188, AMS, Providence, 1977.

[19]

Y. Kanzawa, S. Oishi, Singular solutions of nonlinear equations and a numerical method of proving their existence, in: Proc. of the ‘97 International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, 1997, pp. 29–32.

[20]

Lee, K.; Li, N.; Zhi, L. (2019): On isolation of singular zeros of multivariate analytic systems. arXiv:1904.0793.

[21]

A. Leykin, J. Verschelde, A. Zhao, Newton's method with deflation for isolated singularities of polynomial systems, Theor. Comput. Sci. 359 (1–3) (2006) 111–122.

[22]

A. Leykin, J. Verschelde, A. Zhao, Higher-order deflation for polynomial systems with isolated singular solutions, in: A. Dickenstein, F.-O. Schreyer, A. Sommese (Eds.), Algorithms in Algebraic Geometry, in: The IMA Volumes in Mathematics and Its Applications, vol. 146, Springer, 2008, pp. 79–97.

[23]

N. Li, L. Zhi, Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one, Theor. Comput. Sci. 479 (2013) 163–173.

[24]

N. Li, L. Zhi, Verified error bounds for isolated singular solutions of polynomial systems, SIAM J. Numer. Anal. 52 (4) (2014) 1623–1640.

[25]

Z. Li, H. Sang, Verified error bounds for singular solutions of nonlinear systems, Numer. Algorithms 70 (2) (2015) 309–331.

[26]

A. Mantzaflaris, B. Mourrain, Deflation and certified isolation of singular zeros of polynomial systems, in: Proc. of ISSAC ’11, ACM, 2011, pp. 249–256.

[27]

A. Mantzaflaris, B. Mourrain, Singular zeros of polynomial systems, in: T. Dokken, G. Muntingh (Eds.), Advances in Shapes, Geometry, and Algebra, in: Geometry and Computing, vol. 10, Springer, 2014, pp. 77–103.

[28]

A. Mantzaflaris, B. Mourrain, Szanto A. Punctual, Hilbert scheme and certified approximate singularities, in: Proc. of ISSAC ’20, ACM, 2020, pp. 336–343.

[29]

B. Mourrain, Isolated points, duality and residues, J. Pure Appl. Algebra 117–118 (1997) 469–493.

[30]

S. Rump, S. Graillat, Verified error bounds for multiple roots of systems of nonlinear equations, Numer. Algorithms 54 (2010) 359–377.

[31]

I.R. Shafarevich, Basic Algebraic Geometry 1: Varieties in Projective Space, 3rd edition, Springer, New York, 2013.

[32]

X. Wu, L. Zhi, Computing the multiplicity structure from geometric involutive form, in: Proceedings of ISSAC ’08, NY, USA, 2008, ACM, 2008, pp. 325–332.

[33]

X. Wu, L. Zhi, Determining singular solutions of polynomial systems via symbolic-numeric reduction to geometric involutive form, J. Symb. Comput. 27 (2008) 104–122.

[34]

J.-C. Yakoubsohn, Finding a cluster of zeros of univariate polynomials, in: Complexity Theory, Real Machines, and Homotopy, vol. 16, Oxford, 1999, 2000, pp. 603–638.

[35]

J.-C. Yakoubsohn, Simultaneous computation of all the zero-clusters of a univariate polynomial, in: Foundations of Computational Mathematics, Hong Kong, 2000, World Sci. Publ., River Edge, NJ, 2002, pp. 433–455.

[36]

Z. Zeng, The Closedness Subspace Method for Computing the Multiplicity Structure of a Polynomial System, Contemp. Math., vol. 496, Amer. Math. Soc., Providence, RI, 2009, pp. 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

Index Terms

A certified iterative method for isolated singular roots
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
  2. Probability and statistics
    1. Probabilistic reasoning algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

General local convergence theory for a class of iterative processes and its applications to Newton's method

General local convergence theorems with order of convergence r>=1 are provided for iterative processes of the type x"n"+"1=Tx"n, where T:D@?X->X is an iteration function in a metric space X. The new local convergence theory is applied to Newton ...
Method for finding multiple roots of polynomials

Conventional numerical methods for finding multiple roots of polynomials are inaccurate. The accuracy is unsatisfactory because the derivatives of the polynomial in the intermediate steps of the associated root-finding procedures are eliminated. ...
Two-Level Newton Iterative Method for the 2D/3D Stationary Incompressible Magnetohydrodynamics

In this paper, Newton iteration and two-level finite element algorithm are combined for solving numerically the stationary incompressible magnetohydrodynamics (MHD) under a strong uniqueness condition. The method consists of solving the nonlinear MHD ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Symbolic Computation

Journal of Symbolic Computation Volume 115, Issue C

Mar 2023

518 pages

ISSN:0747-7171

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Jan 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

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents