Cited By
View all- Li NZhi L(2022)Improved two-step Newton’s method for computing simple multiple zeros of polynomial systemsNumerical Algorithms10.1007/s11075-022-01253-791:1(19-50)Online publication date: 2-Feb-2022
Punctual Hilbert scheme and certified approximate singularities
Pages 336 - 343
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 = (f1, ..., fN) ∈ C[x1, ..., xn]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]
Ayyildiz Akoglu, T., Hauenstein, J. D., and Szanto, A. Certifying solutions to overdetermined and singular polynomial systems over Q. Journal of Symbolic Computation 84 (2018), 147--171.
[2]
Bejleri, D., and Stapleton, D. The tangent space of the punctual Hilbert scheme. The Michigan Mathematical Journal 66, 3 (Aug. 2017), 595--610.
[3]
Blum, L., Cucker, F., Shub, M., and Smale, S. Complexity and Real Computation. Springer, NY, 1998.
[4]
Briançon, J. Description de HilbnC {x, y}. Inventiones mathematicae 41 (1977), 45--90.
[5]
Briançon, J., and Iarrobino, A. Dimension of the punctual Hilbert scheme. Journal of Algebra 55, 2 (Dec. 1978), 536--544.
[6]
Dayton, B. H., Li, T.-Y., and Zeng, Z. Multiple zeros of nonlinear systems. Math. Comput. 80, 276 (2011), 2143--2168.
[7]
Dayton, B. H., and Zeng, Z. Computing the multiplicity structure in solving polynomial systems. In Proc. of ISSAC '05 (NY, USA, 2005), ACM, pp. 116--123.
[8]
Dedieu, J.-P., and Shub, M. On simple double zeros and badly conditioned zeros of analytic functions of n variables. Math. Comp. 70, 233 (2001), 319--327.
[9]
Doubilet, P., Rota, G.-C., and Stein, J. On the Foundations of Combinatorial Theory. Studies in Applied Mathematics 53, 3 (1974), 185--216.
[10]
Emiris, I. Z., Mourrain, B., and Tsigaridas, E. The DMM bound: multivariate (aggregate) separation bounds. In Proceedings of the ISSAC'10 (Munich, Germany, July 2010), S. Watt, Ed., ACM, pp. 243--250.
[11]
Giusti, M., Lecerf, G., Salvy, B., and Yakoubsohn, J.-C. On location and approximation of clusters of zeros of analytic functions. Found. Comput. Math. 5, 3 (2005), 257--311.
[12]
Giusti, M., Lecerf, G., Salvy, B., and Yakoubsohn, J.-C. On location and approximation of clusters of zeros: Case of embedding dimension one. Foundations of Computational Mathematics 7 (2007), 1--58.
[13]
Giusti, M., and Yakoubsohn, J.-C. Multiplicity hunting and approximating multiple roots of polynomial systems. vol. 604 of Contemp. Math., AMS, pp. 105--128.
[14]
Giusti, M., and Yakoubsohn, J.-C. Approximation numérique de racines isolées multiples de systèmes analytiques, 2018. arXiv:1809.05446.
[15]
Hao, W., Sommese, A. J., and Zeng, Z. Algorithm 931: an algorithm and software for computing multiplicity structures at zeros of nonlinear systems. ACM Trans. Math. Software 40, 1 (2013), Art. 5, 16.
[16]
Hauenstein, J. D., Mourrain, B., and Szanto, A. On deflation and multiplicity structure. Journal of Symbolic Computation 83 (2016), 228--253.
[17]
Iarrobino, A. A. Punctual Hilbert Schemes, vol. 188 of Memoirs of the American Mathematical Society. AMS, Providence, 1977.
[18]
Kanzawa, Y., and Oishi, S. Approximate singular solutions of nonlinear equations and a numerical method of proving their existence. No. 990. 1997, pp. 216--223.
[19]
Lee, K., Li, N., and Zhi, L. On isolation of singular zeros of multivariate analytic systems, 2019. arXiv:1904.0793.
[20]
Leykin, A., Verschelde, J., and Zhao, A. Newton's method with deflation for isolated singularities of polynomial systems. Theor. Computer Science 359, 1--3 (2006), 111--122.
[21]
Leykin, A., Verschelde, J., and Zhao, A. Higher-order deflation for polynomial systems with isolated singular solutions. In Algorithms in Algebraic Geometry, A. Dickenstein, F.-O. Schreyer, and A. Sommese, Eds., vol. 146 of The IMA Volumes in Mathematics and its Applications. Springer, 2008, pp. 79--97.
[22]
Li, N., and Zhi, L. Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one. Theoret. Comput. Sci. 479 (2013), 163--173.
[23]
Li, N., and Zhi, L. Verified error bounds for isolated singular solutions of polynomial systems. SIAM J. Numer. Anal. 52, 4 (2014), 1623--1640.
[24]
Li, Z., and Sang, H. Verified error bounds for singular solutions of nonlinear systems. Numer. Algorithms 70, 2 (2015), 309--331.
[25]
Mantzaflaris, A., and Mourrain, B. Deflation and certified isolation of singular zeros of polynomial systems. In Proc. of ISSAC '11 (2011), ACM, pp. 249--256.
[26]
Mantzaflaris, A., and Mourrain, B. Singular zeros of polynomial systems. In Advances in Shapes, Geometry, and Algebra, T. Dokken and G. Muntingh, Eds., vol. 10 of Geometry and Computing. Springer, 2014, pp. 77--103.
[27]
Mourrain, B. Isolated points, duality and residues. Journal of Pure and Applied Algebra 117--118 (1997), 469--493.
[28]
Rump, S., and Graillat, S. Verified error bounds for multiple roots of systems of nonlinear equations. Numerical Algorithms 54 (2010), 359--377.
[29]
Shafarevich, I. R. Basic Algebraic Geometry 1: Varieties in Projective Space, 3rd edition ed. Springer, New York, 2013.
[30]
Wu, X., and Zhi, L. Computing the multiplicity structure from geometric involutive form. In Proceedings of ISSAC"08 (NY, USA, 2008), ACM, pp. 325--332.
[31]
Wu, X., and Zhi, L. Determining singular solutions of polynomial systems via symbolic-numeric reduction to geometric involutive form. J. Symb. Comput. 27 (2008), 104--122.
[32]
Yakoubsohn, J.-C. Finding a cluster of zeros of univariate polynomials. vol. 16. 2000, pp. 603--638. Complexity theory, real machines, and homotopy (Oxford, 1999).
[33]
Yakoubsohn, J.-C. 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.
[34]
Zeng, Z. The closedness subspace method for computing the multiplicity structure of a polynomial system. vol. 496 of Contemp. Math. Amer. Math. Soc., Providence, RI, 2009, pp. 347--362.
- Punctual Hilbert scheme and certified approximate singularities
Recommendations
Deflation and certified isolation of singular zeros of polynomial systems
ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computationWe develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented,...
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 ...
A certified iterative method for isolated singular roots
AbstractIn 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2020
480 pages
ISBN:9781450371001
DOI:10.1145/3373207
- General Chairs:
- Ioannis Z. Emiris,
- Lihong Zhi,
- Publications Chair:
- Angelos Mantzaflaris
Copyright © 2020 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 the author(s) 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].
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 July 2020
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISSAC '20
ISSAC '20: International Symposium on Symbolic and Algebraic Computation
July 20 - 23, 2020
Kalamata, Greece
Acceptance Rates
ISSAC '20 Paper Acceptance Rate 58 of 102 submissions, 57%;
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 33Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
Cited By
View all- Li NZhi L(2022)Improved two-step Newton’s method for computing simple multiple zeros of polynomial systemsNumerical Algorithms10.1007/s11075-022-01253-791:1(19-50)Online publication date: 2-Feb-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in