Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\). (English) Zbl 1415.65121
Summary: This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods to compute an exact rational univariate representation (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using \(\alpha\)-theory. To certify isolated singular roots, we use a determinantal form of the isosingular deflation, which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.
MSC:
| 65H99 | Nonlinear algebraic or transcendental equations |
| 12D10 | Polynomials in real and complex fields: location of zeros (algebraic theorems) |
Keywords:
overdetermined; polynomial system; singular solutions; certification; rational univariate representation; isosingular deflationReferences:
| [1] | Abbott, J., Bounds on factors in \(Z [x]\), J. Symb. Comput., 50, 532-563 (2013) · Zbl 1295.12010 |
| [2] | Allamigeon, X.; Gaubert, S.; Magron, V.; Werner, B., Formal proofs for nonlinear optimization, J. Formaliz. Reason., 8, 1, 1-24 (2015) · Zbl 1451.90131 |
| [3] | Alonso, M.; Becker, E.; Roy, M.-F.; Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems, Prog. Math., 143, 1-15 (1996) · Zbl 0879.14033 |
| [4] | Arnold, E. A., Modular algorithms for computing Gröbner bases, J. Symb. Comput., 35, 403-419 (2003) · Zbl 1046.13018 |
| [5] | Bates, D. J.; Hauenstein, J. D.; McCoy, T. M.; Peterson, C.; Sommese, A. J., Recovering exact results from inexact numerical data in algebraic geometry, Exp. Math., 22, 1, 38-50 (2013) · Zbl 1284.14084 |
| [6] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler. Bertini, C. W., Software for numerical algebraic geometry (2013), Available at |
| [7] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Numerically solving polynomial systems with Bertini, Software, Environments, and Tools, vol. 25 (2013), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1295.65057 |
| [8] | Beltrán, C.; Leykin, A., Certified numerical homotopy tracking, Exp. Math., 21, 1, 69-83 (2012) · Zbl 1238.14048 |
| [9] | Beltrán, C.; Leykin, A., Robust certified numerical homotopy tracking, Found. Comput. Math., 13, 2, 253-295 (2013) · Zbl 1267.14075 |
| [10] | Björck, G., Functions of modulus 1 on \(Z_n\) whose Fourier transforms have constant modulus, and “cyclic \(n\)-roots”, (Recent Advances in Fourier Analysis and Its Applications. Recent Advances in Fourier Analysis and Its Applications, Il Ciocco, 1989. Recent Advances in Fourier Analysis and Its Applications. Recent Advances in Fourier Analysis and Its Applications, Il Ciocco, 1989, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 315 (1990), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 131-140 · Zbl 0726.43004 |
| [11] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer-Verlag: Springer-Verlag New York |
| [12] | Bozóki, S.; Lee, T.-L.; Rónyai, L., Seven mutually touching infinite cylinders, Comput. Geom., 48, 2, 87-93 (2015) · Zbl 1310.65022 |
| [13] | Bright, C.; Storjohann, A., Vector rational number reconstruction, (ISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation (2011), ACM: ACM New York), 51-57 · Zbl 1323.68587 |
| [14] | Brownawell, W. D.; Yap, C. K., Lower bounds for zero-dimensional projections, (ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (2009), ACM: ACM New York), 79-85 · Zbl 1237.68253 |
| [15] | Canny, J., Generalised characteristic polynomials, J. Symb. Comput., 9, 3, 241-250 (1990) · Zbl 0704.12004 |
| [16] | Castro, D.; Pardo, L. M.; Hägele, K.; Morais, J. E., Kronecker’s and Newton’s approaches to solving: a first comparison, J. Complex., 17, 1, 212-303 (2001) · Zbl 1013.68296 |
| [17] | Dahan, X.; Schost, É., Sharp estimates for triangular sets, (ISSAC 2004 (2004), ACM: ACM New York), 103-110 · Zbl 1134.13308 |
| [18] | Dayton, B. H.; Zeng, Z., Computing the multiplicity structure in solving polynomial systems, (ISSAC’05 (2005), ACM: ACM New York), 116-123 · Zbl 1360.65151 |
| [19] | Dedieu, J. P.; Shub, M., Newton’s method for overdetermined systems of equations, Math. Comput., 69, 231, 1099-1115 (2000) · Zbl 0949.65061 |
| [20] | Ferguson, H. R.P.; Bailey, D. H.; Arno, S., Analysis of PSLQ, an integer relation finding algorithm, Math. Comput., 68, 225, 351-369 (1999) · Zbl 0927.11055 |
| [21] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2013), Cambridge University Press: Cambridge University Press New York · Zbl 1277.68002 |
| [22] | Giusti, M.; Hägele, K.; Heintz, J.; Morais, J. E.; Montãna, J. L.; Pardo, L. M., Lower bounds for Diophantine approximations, J. Pure Appl. Algebra, 117-118, 277-317 (1997) · Zbl 0871.68101 |
| [23] | Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 1-3, 101-146 (1998) · Zbl 0944.12004 |
| [24] | Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complex., 17, 1, 154-211 (2001) · Zbl 1003.12005 |
| [25] | Griewank, A.; Osborne, M. R., Analysis of Newton’s method at irregular singularities, SIAM J. Numer. Anal., 20, 4, 747-773 (1983) · Zbl 0525.65025 |
| [26] | Hauenstein, J. D.; Haywood, I.; Liddell, A. C., An a posteriori certification algorithm for Newton homotopies, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14 (2014), ACM), 248-255 · Zbl 1325.65074 |
| [27] | Hauenstein, J. D.; Liddell, A. C., Certified predictor-corrector tracking for Newton homotopies, J. Symb. Comput., 74, 239-254 (2016) · Zbl 1329.65110 |
| [28] | Hauenstein, J. D.; Mourrain, B.; Szanto, A., Certifying isolated singular points and their multiplicity structure, (Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation, ISSAC’15 (2015), ACM: ACM New York), 213-220 · Zbl 1345.68286 |
| [29] | Hauenstein, J. D.; Pan, V. Y.; Szanto, A., Global Newton iteration over Archimedian and non-Archimedian fields, (Proceedings of Computer Algebra in Scientific Computing. Proceedings of Computer Algebra in Scientific Computing, CASC 2014. Proceedings of Computer Algebra in Scientific Computing. Proceedings of Computer Algebra in Scientific Computing, CASC 2014, Lecture Notes in Computer Science (2014), Springer-Verlag) |
| [30] | Hauenstein, J. D.; Sottile, F., Algorithm 921: alphaCertified: certifying solutions to polynomial systems, ACM Trans. Math. Softw., 38, 4, 28 (2012) · Zbl 1365.65148 |
| [31] | Hauenstein, J. D.; Wampler, C. W., Isosingular sets and deflation, Found. Comput. Math., 13, 3, 371-403 (2013) · Zbl 1276.65029 |
| [32] | Heintz, J.; Krick, T.; Puddu, S.; Sabia, J.; Waissbein, A., Deformation techniques for efficient polynomial equation solving. Real computation and complexity, J. Complex., 16, 1, 70-109 (2000), (Schloss Dagstuhl, 1998) · Zbl 1041.65044 |
| [33] | Heintz, J.; Roy, M.-F.; Solernó, P., Sur la complexité du principe de Tarski-Seidenberg, Bull. Soc. Math. Fr., 118, 101-126 (1990) · Zbl 0767.03017 |
| [34] | Hindry, M.; Silverman, J. H., Diophantine Geometry, Graduate Texts in Mathematics, vol. 201 (2000), Springer-Verlag: Springer-Verlag New York · Zbl 0948.11023 |
| [35] | van der Hoeven, J., Reliable Homotopy Continuation (2015), Technical Report, HAL |
| [36] | Jeronimo, G.; Perrucci, D., On the minimum of a positive polynomial over the standard simplex, J. Symb. Comput., 45, 4, 434-442 (2010) · Zbl 1239.90086 |
| [37] | Jeronimo, G.; Perrucci, D.; Tsigaridas, E., On the minimum of a polynomial function on a basic closed semialgebraic set and applications, SIAM J. Optim., 23, 1, 241-255 (2013) · Zbl 1272.14042 |
| [38] | Kaltofen, E., Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput., 14, 2, 469-489 (1985) · Zbl 0605.12001 |
| [39] | Kaltofen, E., Sparse Hensel lifting, (EUROCAL ’85, vol. 2. EUROCAL ’85, vol. 2, Linz, 1985. EUROCAL ’85, vol. 2. EUROCAL ’85, vol. 2, Linz, 1985, Lecture Notes in Comput. Sci., vol. 204 (1985), Springer: Springer Berlin), 4-17 · Zbl 0605.12011 |
| [40] | Kaltofen, E.; Li, B.; Yang, Z.; Zhi, L., Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars, (Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation. Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, ISSAC ’08 (2008), ACM: ACM New York, NY, USA), 155-164 · Zbl 1493.68402 |
| [41] | Kaltofen, E. L.; Li, B.; Yang, Z.; Zhi, L., Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symb. Comput., 47, 1, 1-15 (2012) · Zbl 1229.90115 |
| [42] | Kannan, R.; Lenstra, A. K.; Lovász, L., Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comput., 50, 181, 235-250 (1988) · Zbl 0654.12001 |
| [43] | Kanzawa, Y.; Kashiwagi, M.; Oishi, S., An algorithm for finding all solutions of parameter-dependent nonlinear equations with guaranteed accuracy, Electron. Commun. Jpn., Part 3, Fundam. Electron. Sci., 82, 10, 33-39 (1999) |
| [44] | Kanzawa, Y.; Oishi, S., Approximate singular solutions of nonlinear equations and a numerical method of proving their existence, Theory and Application of Numerical Calculation in Science and Technology, II (Japanese). Theory and Application of Numerical Calculation in Science and Technology, II (Japanese), Kyoto, 1996. Theory and Application of Numerical Calculation in Science and Technology, II (Japanese). Theory and Application of Numerical Calculation in Science and Technology, II (Japanese), Kyoto, 1996, Sūrikaisekikenkyūsho Kōkyūroku, 990, 216-223 (1997) · Zbl 0942.65513 |
| [45] | Krawczyk, R., Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken, Computing, 4, 3, 187-201 (1969) · Zbl 0187.10001 |
| [46] | Krick, T.; Pardo, L. M.; Sombra, M., Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J., 109, 3, 521-598 (2001) · Zbl 1010.11035 |
| [47] | Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen (1882), Druck und Verlag von G. Reimer: Druck und Verlag von G. Reimer Berlin · JFM 14.0038.02 |
| [48] | Lecerf, G., Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions, (Proceedings of ISSAC 2000 (2000), ACM: ACM New York), 2091-7216 |
| [49] | Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 4, 515-534 (1982) · Zbl 0488.12001 |
| [50] | Leykin, A.; Verschelde, J.; Zhao, A., Newton’s method with deflation for isolated singularities of polynomial systems, Theor. Comput. Sci., 359, 1-3, 111-122 (2006) · Zbl 1106.65046 |
| [51] | Leykin, A.; Verschelde, J.; Zhao, A., Higher-order deflation for polynomial systems with isolated singular solutions, (Algorithms in Algebraic Geometry. Algorithms in Algebraic Geometry, IMA Vol. Math. Appl., vol. 146 (2008), Springer: Springer New York), 79-97 · Zbl 1138.65038 |
| [52] | Li, N.; Zhi, L., Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one, Theor. Comput. Sci., 479, 163-173 (2013) · Zbl 1291.65161 |
| [53] | Li, N.; Zhi, L., Verified error bounds for isolated singular solutions of polynomial systems, SIAM J. Numer. Anal., 52, 4, 1623-1640 (2014) · Zbl 1310.65056 |
| [54] | Lichtblau, D., Half-GCD and fast rational recovery, (ISSAC’05 (2005), ACM: ACM New York), 231-236 · Zbl 1360.68943 |
| [55] | Mantzaflaris, A.; Mourrain, B., Deflation and certified isolation of singular zeros of polynomial systems, (Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ISSAC ’11 (2011), ACM: ACM New York, NY, USA), 249-256 · Zbl 1323.65054 |
| [56] | Monniaux, D.; Corbineau, P., On the generation of positivstellensatz witnesses in degenerate cases, (van Eekelen, M.; Geuvers, H.; Schmaltz, J.; Wiedijk, F., Interactive Theorem Proving. Interactive Theorem Proving, Lecture Notes in Computer Science, vol. 6898 (2011), Springer: Springer Berlin Heidelberg), 249-264 · Zbl 1342.68296 |
| [57] | Moore, R., A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal., 14, 4, 611-615 (1977) · Zbl 0365.65034 |
| [58] | Moritsugu, S.; Kuriyama, K., On multiple zeros of systems of algebraic equations, (Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation. Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC ’99 (1999), ACM: ACM New York, NY, USA), 23-30 |
| [59] | Nakaya, Y.; Oishi, S.; Kashiwagi, M.; Kanzawa, Y., Numerical verification of nonexistence of solutions for separable nonlinear equations and its application to all solutions algorithm, Electron. Commun. Jpn., Part 3, Fundam. Electron. Sci., 86, 5, 45-53 (2003) |
| [60] | Ojika, T., Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations, J. Math. Anal. Appl., 123, 1, 199-221 (1987) · Zbl 0625.65043 |
| [61] | Ojika, T.; Watanabe, S.; Mitsui, T., Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl., 96, 2, 463-479 (1983) · Zbl 0525.65027 |
| [62] | Pan, V. Y.; Wang, X., On rational number reconstruction and approximation, SIAM J. Comput., 33, 2, 502-503 (2004) · Zbl 1101.68997 |
| [63] | Peyrl, H.; Parrilo, P. A., A Macaulay2 package for computing sum of squares decompositions of polynomials with rational coefficients, (SNC (2007)), 207-208 |
| [64] | Peyrl, H.; Parrilo, P. A., Computing sum of squares decompositions with rational coefficients, Theor. Comput. Sci., 409, 2, 269-281 (Dec. 2008) · Zbl 1156.65062 |
| [65] | Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008 |
| [66] | Rump, S.; Graillat, S., Verified error bounds for multiple roots of systems of nonlinear equations, Numer. Algorithms, 54, 3, 359-377 (2010) · Zbl 1201.65081 |
| [67] | Rump, S. M., Solving algebraic problems with high accuracy, (Proc. of the Symposium on a New Approach to Scientific Computation (1983), Academic Press Professional, Inc.: Academic Press Professional, Inc. San Diego, CA, USA), 51-120 · Zbl 0597.65018 |
| [68] | Safey El Din, M.; Zhi, L., Computing rational points in convex semialgebraic sets and sum of squares decompositions, SIAM J. Optim., 20, 6, 2876-2889 (2010) · Zbl 1279.90127 |
| [69] | Schost, É., Sur la résolution des systèmes polynomiaux à paramètres (2001), Ph.D. Thesis |
| [70] | Schrijver, A., Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics (1986), John Wiley & Sons Ltd.: John Wiley & Sons Ltd. Chichester, A Wiley-Interscience Publication · Zbl 0665.90063 |
| [71] | Smale, S., Newton’s method estimates from data at one point, (The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, Laramie, Wyo., 1985 (1986), Springer: Springer New York), 185-196 · Zbl 0613.65058 |
| [72] | Sombra, M., Estimaciones para el teorema de ceros de Hilbert (1998), U. de Buenos Aires, PhD thesis |
| [73] | Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials (2005), World Scientific Publishing Co. Pte. Ltd.: World Scientific Publishing Co. Pte. Ltd. Hackensack, NJ · Zbl 1091.65049 |
| [74] | Steffy, D. E., Exact solutions to linear systems of equations using output sensitive lifting, ACM Commun. Comput. Algebra, 44, 4, 160-182 (Dec. 2010) · Zbl 1308.68190 |
| [75] | Szanto, A., Solving over-determined systems by the subresultant method, J. Symb. Comput., 43, 1, 46-74 (2008), With an appendix by Marc Chardin · Zbl 1132.13312 |
| [76] | Trinks, W., On improving approximate results of Buchberger’s algorithm by Newton’s method, (Caviness, B., EUROCAL ’85. EUROCAL ’85, Lecture Notes in Computer Science, vol. 204 (1985), Springer: Springer Berlin Heidelberg), 608-612 · Zbl 0568.00019 |
| [77] | Wang, X.; Pan, V. Y., Acceleration of Euclidean algorithm and rational number reconstruction, SIAM J. Comput., 32, 2, 548-556 (2003) · Zbl 1031.68149 |
| [78] | Winkler, F., A \(p\)-adic approach to the computation of Gröbner bases, J. Symb. Comput., 6, 2-3, 287-304 (1988) · Zbl 0669.13009 |
| [79] | Yamamura, K.; Kawata, H.; Tokue, A., Interval solution of nonlinear equations using linear programming, BIT Numer. Math., 38, 1, 186-199 (1998) · Zbl 0908.65038 |
| [80] | Yang, Z.; Zhi, L.; Zhu, Y., Verified error bounds for real solutions of positive-dimensional polynomial systems, (Proceedings of the 38th International Symposium on International Symposium on Symbolic and Algebraic Computation. Proceedings of the 38th International Symposium on International Symposium on Symbolic and Algebraic Computation, ISSAC ’13 (2013), ACM: ACM New York, NY, USA), 371-378 · Zbl 1360.65156 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
