Geodesic
Rigid continuation paths II. structured polynomial systems
Forum of Mathematics, Pi, Tome 11 (2023)

Voir la notice de l'article provenant de la source Cambridge University Press

This work studies the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most ${D}$ in n variables with only $\operatorname {poly}(n, {D}) L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem. 
@article{10_1017_fmp_2023_7,
     author = {Peter B\"urgisser and Felipe Cucker and Pierre Lairez},
     title = {Rigid continuation paths {II.} structured polynomial systems},
     journal = {Forum of Mathematics, Pi},
     publisher = {mathdoc},
     volume = {11},
     year = {2023},
     doi = {10.1017/fmp.2023.7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2023.7/}
}
TY  - JOUR
AU  - Peter Bürgisser
AU  - Felipe Cucker
AU  - Pierre Lairez
TI  - Rigid continuation paths II. structured polynomial systems
JO  - Forum of Mathematics, Pi
PY  - 2023
VL  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2023.7/
DO  - 10.1017/fmp.2023.7
LA  - en
ID  - 10_1017_fmp_2023_7
ER  - 
%0 Journal Article
%A Peter Bürgisser
%A Felipe Cucker
%A Pierre Lairez
%T Rigid continuation paths II. structured polynomial systems
%J Forum of Mathematics, Pi
%D 2023
%V 11
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2023.7/
%R 10.1017/fmp.2023.7
%G en
%F 10_1017_fmp_2023_7
Peter Bürgisser; Felipe Cucker; Pierre Lairez. Rigid continuation paths II. structured polynomial systems. Forum of Mathematics, Pi, Tome 11 (2023). doi: 10.1017/fmp.2023.7

[1] Armentano, D., Beltrán, C., Bürgisser, P., Cucker, F. and Shub, M., ‘Condition length and complexity for the solution of polynomial systems’, Found. Comput. Math. 16(6) (2016), 1401–1422.Google Scholar | DOI | DOI

[2] Baur, W. and Strassen, V., ‘The complexity of partial derivatives’, Theor. Comput. Sci. 22(3) (1983), 317–330.Google Scholar | DOI

[3] Beltrán, C., ‘A continuation method to solve polynomial systems and its complexity’, Numer. Math. 117(1) (2011), 89–113.Google Scholar | DOI | DOI

[4] Beltrán, C. and Leykin, A., ‘Certified numerical homotopy tracking’, Exp. Math. 21(1) (2012), 69–83.Google Scholar | DOI

[5] Beltrán, C. and Leykin, A., ‘Robust certified numerical homotopy tracking’, Found. Comput. Math. 13(2) (2013), 253–295.Google Scholar | DOI | DOI

[6] Beltrán, C. and Pardo, L. M., ‘On Smale’s 17th problem: A probabilistic positive solution’, Found. Comput. Math. 8(1) (2008), 1–43.Google Scholar | DOI | DOI

[7] Beltrán, C. and Pardo, L. M., ‘Smale’s 17th problem: Average polynomial time to compute affine and projective solutions’, J. Am. Math. Soc. 22(2) (2009), 363–385.Google Scholar | DOI

[8] Beltrán, C. and Pardo, L. M., ‘Fast linear homotopy to find approximate zeros of polynomial systems’, Found. Comput. Math. 11(1) (2011), 95–129.Google Scholar | DOI | DOI

[9] Beltrán, C. and Shub, M. (2009). ‘Complexity of Bezout’s theorem. VII. Distance estimates in the condition metric’, Found. Comput. Math., 9(2), 179–195.Google Scholar | DOI | DOI

[10] Boucheron, S., Lugosi, G. and Massart, P., Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, Oxford, 2013).Google Scholar | DOI | DOI

[11] Bürgisser, P., Completeness and reduction in algebraic complexity theory, (Springer, 2000).Google Scholar | DOI

[12] Bürgisser, P., Condition of intersecting a projective variety with a varying linear subspace’, SIAM J. Appl. Algebra Geom. 1(1) (2017), 111–125.Google Scholar | DOI

[13] Bürgisser, P., Clausen, M. and Shokrollahi, M. A., Algebraic Complexity Theory, vol. 315 (Springer, New York, 1997).Google Scholar | DOI

[14] Bürgisser, P. and Cucker, F., ‘On a problem posed by Steve Smale’, Ann. of Math. (2) 174(3) (2011), 1785–1836.Google Scholar | DOI | DOI

[15] Bürgisser, P. and Cucker, F., Condition: The Geometry of Numerical Algorithms (Springer, New York, 2013). 10/dsfq.Google Scholar | DOI

[16] Dedieu, J.-P., Points fixes, zéros et la méthode de Newton, vol. 54 (Springer, New York, 2006).Google Scholar | DOI

[17] Dedieu, J.-P. and Shub, M., ‘Multihomogeneous Newton methods’, Math. Comput. 69(231) (1999), 1071–1099.Google Scholar | DOI

[18] Demmel, J. W., On condition numbers and the distance to the nearest ill-posed problem’, Numer. Math. 51(3) (1987), 251–289.Google Scholar | DOI

[19] Federer, H., ‘Curvature measures. Trans. Am. Math. Soc. 93(3) (1959), 418–491.Google Scholar | DOI

[20] Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A. and Rubin, D. B., Bayesian Data Analysis, 3rd ed. (CRC Press, Boca Raton, 2014).Google Scholar

[21] Giusti, M., Lecerf, G. and Salvy, B., A Gröbner free alternative for polynomial system solving’, J. Complex. 17(1) (2001), 154–211.Google Scholar | DOI | DOI

[22] Griffiths, P. A. and Harris, J., Principles of Algebraic Geometry (Wiley-Interscience, New York, 1978).Google Scholar

[23] Hauenstein, J. D. and Liddell, A. C., ‘Certified predictor-corrector tracking for Newton homotopies’, J. Symb. Comput. 74 (2016), 239–254.Google Scholar | DOI | DOI

[24] Hauenstein, J. D. and Sottile, F., ‘Algorithm 921: alphaCertified: certifying solutions to polynomial systems’, ACM Trans. Math. Softw. 38(4) (2012), 1–20.Google Scholar | DOI

[25] Howard, R., ‘The kinematic formula in Riemannian homogeneous spaces’, Mem. Amer. Math. Soc. 106(509) (1993).Google Scholar | DOI

[26] Ji, S., Kollar, J. and Shiffman, B., ‘A global Lojasiewicz inequality for algebraic varieties’, Trans. Am. Math. Soc. 329(2) (1992), 813.Google Scholar | DOI

[27] Kahan, W., Accurate eigenvalues of a symmetric tri-diagonal matrix (CS41) (Stanford University, Stanford, 1966).Google Scholar

[28] Lairez, P., ‘A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time’, Found. Comput. Math. 17(5) (2017), 1265–1292.Google Scholar | DOI | DOI

[29] Lairez, P., ‘Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems’, J. Am. Math. Soc., 33(2) (2020), 487–526.Google Scholar | DOI | DOI

[30] Lakshman, Y. N., ‘A single exponential bound on the complexity of computing Gröbner bases of zero dimensional ideals’, in Effective Methods in Algebraic Geometry (Birkhäuser, Boston, 1991), 227–234.Google Scholar | DOI

[31] Malod, G. and Portier, N., ‘Characterizing Valiant’s algebraic complexity classes’, J. Complex. 24(1) (2008), 16–38.Google Scholar | DOI | DOI

[32] Nisan, N., ‘Lower bounds for non-commutative computation’, Proc. Twenty-Third Annu. ACM Symp. Theory Comput. (1991), 410–418.Google Scholar | DOI

[33] Pan, V. Y., ‘Univariate polynomials: Nearly optimal algorithms for factorization and rootfinding’, Proc. 2001 Int. Symp. Symb. Algebr. Comput. (2001), 253–267.Google Scholar | DOI

[34] Pan, V., ‘Optimal and nearly optimal algorithms for approximating polynomial zeros’, Comput. Math. Appl. 31(2) (1996), 97–138.Google Scholar | DOI

[35] Renegar, J., ‘On the worst-case arithmetic complexity of approximating zeros of polynomials’, J. Complex. 3(2) (1987), 90–113.Google Scholar | DOI

[36] Renegar, J., ‘On the worst-case arithmetic complexity of approximating zeros of systems of polynomials’, SIAM J. Comput. 18(2) (1989), 350–370.Google Scholar | DOI

[37] Rudin, W., Function Theory in the Unit Ball of (Springer, New York, 1980).Google Scholar

[38] Rump, S. M. and Graillat, S., ‘Verified error bounds for multiple roots of systems of nonlinear equations’, Numer. Algorith. 54(3) (2010), 359–377.Google Scholar | DOI | DOI

[39] Shub, M. ‘Complexity of Bezout’s theorem. VI. Geodesics in the condition (number) metric’, Found. Comput. Math., 9(2) (2009), 171–178.Google Scholar | DOI | DOI

[40] Shub, M. and Smale, S., ‘Complexity of Bézout’s theorem. I. Geometric aspects’, J. Am. Math. Soc. 6(2) (1993), 459–501.Google Scholar | DOI

[41] Shub, M. and Smale, S., ‘Complexity of Bezout’s theorem II volumes and probabilities’, in Computational Algebraic Geometry (Birkhäuser, Boston, 1993), 267–285.Google Scholar | DOI

[42] Shub, M. and Smale, S., Complexity of Bezout’s theorem. III. Condition number and packing’, J. Complex. 9(1) (1993), 4–14.Google Scholar | DOI | DOI

[43] Shub, M. and Smale, S., ‘Complexity of Bezout’s theorem. V. Polynomial time’, Theor. Comput. Sci. 133(1) (1994), 141–164. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993)Google Scholar | DOI

[44] Shub, M. and Smale, S., ‘Complexity of Bezout’s theorem. IV. Probability of success; extensions’, SIAM J. Numer. Anal. 33(1) (1996), 128–148.Google Scholar | DOI

[45] Smale, S., ‘Newton’s method estimates from data at one point’, in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (Laramie, Wyo., 1985) (Springer, New York, 1986), 185–196.Google Scholar | DOI

[46] Smale, S., ‘Complexity theory and numerical analysis’, Acta Numer. 6 (1997), 523–551.Google Scholar | DOI

[47] Smale, S., ‘Mathematical problems for the next century’, Math. Intell. 20(2) (1998), 7–15.Google Scholar | DOI

[48] Telen, S., Vanbarel, M. and Verschelde, J., ‘A robust numerical path tracking algorithm for polynomial homotopy continuation’, SIAM J. Sci. Comput. 42(6) (2020), A3610–A3637.Google Scholar | DOI

[49] Timme, S., ‘Mixed precision path tracking for polynomial homotopy continuation’, Adv. Comput. Math. 47(5) (2021), 75.Google Scholar | DOI | DOI

[50] Toda, S., ‘Classes of arithmetic circuits capturing the complexity of computing the determinant’, IEICE Trans. Inf. Syst. E75-D(1) (1992), 116–124.Google Scholar

[51] Valiant, L. G., ‘Completeness classes in algebra’, Proc. Elev. Annu. ACM Symp. Theory Comput. (1979), 249–261.Google Scholar | DOI

[52] Valiant, L. G., ‘Reducibility by algebraic projections’, in Logic and algorithmic (Zurich, 1980) (Univ. Genève, Genève, 1982), 365–380.Google Scholar

Cité par Sources :