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

research-article

Public Access

A Faster Solution to Smale's 17th Problem I: Real Binomial Systems

Authors:

Grigoris Paouris,

Kaitlyn Phillipson,

J. Maurice RojasAuthors Info & Claims

ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

Pages 323 - 330

https://doi.org/10.1145/3326229.3326267

Published: 08 July 2019 Publication History

Abstract

Suppose F:=(f_1,łdots,f_n) is a system of random n-variate polynomials with f_i having degree łeq\!d_i and the coefficient of x^a_1 _1\cdots x^a_n _n in f_i being an independent complex Gaussian of mean 0 and variance \fracd_i! a_1!\cdots a_n!łeft(d_i-\sum^n_j=1 a_j \right)! . Recent progress on Smale's 17þth Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, Bü rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of F using just N^O(1) arithmetic operations on average, where N\!:=\!\sum^n_i=1 \frac(n+d_i)! n!d_i! (=n(n+\max_i d_i)^O(\min\n,\max_i d_i)\ ) is the maximum possible total number of monomial terms for such an F. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when F is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just O(n^3łog^2(n\max_i d_i)) arithmetic operations on average. Furthermore, our approach allows real Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in nłog \max_i d_i when F has more terms.

References

[1]

Gernot Akemann; Jinho Baik; Philippe Di Francesco; The Oxford Handbook of Random Matrix Theory, Oxford University Press, 2011.

[2]

Josh Alman, "Limits on the Universal Method for Matrix Multiplication," proceedings of the 34th Computational Complexity Conference (CCC 2019, July 18--20 in New Brunswick, NJ, USA), to appear. Also available as Math ArXiV preprint 1812.08731 .

[3]

Sanjeev Arora and Boaz Barak, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009.

Digital Library

[4]

Osbert Bastani; Chris Hillar, Dimitar Popov, and J. Maurice Rojas, "Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond," Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 145--166, AMS Press, 2011.

[5]

Daniel J. Bates; Jonathan D. Hauenstein; Andrew J. Sommese; and Charles W. Wampler, Numerically Solving Polynomial Systems with Bertini, Software, Environments and Tools series, Society for Industrial and Applied Mathematics, 2013.

Digital Library

[6]

Carlos Beltr´an and Luis M. Pardo, "On Smale's 17th Problem: A Probabilistic Positive answer," Foundations of Computational Mathematics 8 (1): pp. 1--43.

Digital Library

[7]

Carlos Beltr´an and Luis M. Pardo, "Smale's 17th Problem: Average Polynomial Time to compute affine and projective solutions," Journal of the American Mathematical Society, 22 (2009), pp. 363--385.

[8]

Carlos Beltr´an and Luis M. Pardo, "Efficient Polynomial System Solving by Numerical Methods," in Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 37--60, AMS Press, 2011.

[9]

Carlos Beltr´an and Mike Shub, "Complexity of Bezouts Theorem VII: Distance Estimates in the Condition Metric," Foundations of Computational Mathematics, April 2009, Volume 9, Issue 2, pp. 179--195.

Digital Library

[10]

David Naumovich Bernstein, "The Number of Roots of a System of Equations," Functional Analysis and its Applications (translated from Russian), Vol. 9, No. 2, (1975), pp. 183--185.

[11]

A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Academic Press, Orland, 1986.

[12]

Pavel Bleher; Bernard Shiffman; and Steve Zelditch; "Poincare- Lelong approach to universality and scaling of correlations between zeros," Commun. Math. Phys. 208 (2000), pp. 771--785.

[13]

Lenore Blum; Felipe Cucker; Mike Shub; and Steve Smale; Complexity and Real Computation, Springer-Verlag, 1998.

Digital Library

[14]

C. Borell Convex set functions in d-space, Period. Math. Hungar. 6 (2), pp. 111--136 (1975).

[15]

Alfred Brauer, "On addition chains," Bull. Amer. Math. Soc. 45, (1939), pp. 736--739.

[16]

Nader H. Bshouty; Yishay Mansour; Baruch Schieber; and Prasoon Tiwari; "A tight bound for approximating the square root," Inform. Process. Lett. 63 (1997), no. 4, pp. 211--213.

Digital Library

[17]

Peter B¨urgisser and Felipe Cucker, On a problem posed by Steve Smale," Annals of Mathematics, Vol. 174 (2011), Issue 3, pp. 1785--1836.

[18]

Tianran Chen and Tien-Yien Li, "Solutions to Systems of Binomial Equations," Annales Mathematicae Silesianae 28 (2014), pp. 7--34.

[19]

Alan Edelman, "Eigenvalues and condition numbers of random matrices," SIAM Journal on Matrix Analysis and Applications 9 (1988), pp. 543--560.

Digital Library

[20]

Alan Edelman and Eric Kostlan, "How Many Zeros of a Random Polynomial are Real?," Bull. Amer. Math. Soc., 32, January (1995), pp. 1--37.

[21]

David Eisenbud and Bernd Sturmfels, "Binomial Ideals," Duke Mathematical Journal, Vol. 84, No. 1, July 1996.

[22]

Alperen Erg¨ur, Grigoris Paouris, and J. Maurice Rojas, "Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions," Foundations of Computational Mathematics, Feb. 2019, Vol. 19, No. 1, pp. 131--157.

Digital Library

[23]

Yan V. Fyodorov, Antonio Lerario, and Erik Lundberg, "On the Number of Connected Components of Random Algebraic Hypersurfaces," J. Geom. Phys. (2015), pp. 1--20.

[24]

John Hubbard and Barbara Burke Hubbard, Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, 5th edition, Matrix Editions, 2015.

[25]

Birk Huber and Bernd Sturmfels, "A polyhedral method for solving sparse polynomial systems," Math. Comp. 64 (1995), pp. 1541--1555.

Digital Library

[26]

Askold G. Khovanskii, Fewnomials, AMS Press, Providence, Rhode Island, 1991.

[27]

Pascal Koiran, "Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties," Proceedings of the 38th Annual IEEE Computer Society Conference on Foundations of Computer Science (FOCS), Oct. 20--22, 1997, ACM Press.

Digital Library

[28]

Eric Kostlan, "On the distribution of roots of random polynomials," From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990), pp. 419--431, Springer, New York, 1993.

[29]

Pierre Lairez, "A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time," Foundations of computational mathematics 17.5 (2017), pp. 1265-- 1292.

Digital Library

[30]

Tsung-Lin Lee and Tien-Yien Li, "Mixed volume computation in solving polynomial systems," in Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 97--112, AMS Press, 2011.

[31]

Francois Legall, "Powers of Tensors and Fast Matrix Multiplication," Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 296--303, 2014.

Digital Library

[32]

L. Leindler, "On a certain converse of H¨older's inequality II," Acta Sci. Math. (Szeged) 33 (1972), pp. 217--223.

[33]

Tien-Yien Li, "Numerical solution of multivariate polynomial systems by homotopy continuation methods," Acta numerica, 1997, pp. 399--436, Acta Numer., 6, Cambridge Univ. Press, Cambridge, 1997.

[34]

Tien-Yien Li and Xiaoshen Wang, "Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant," Math. Comp. 56 (1991), no. 194, pp. 693--710.

[35]

Vitaly D. Milman and Gideon Schechtman, "Asymptotic Theory of Finite Dimensional Normed Spaces," Springer (Lecture Notes in Mathematics 1200), Berlin, 1986.

Digital Library

[36]

Wellington de Melo and Benar Fux Svaiter, "The cost of computing integers," Proc. Amer. Math. Soc. 124 (1996), pp. 1377--1378.

[37]

Gustavo T. de Araujo Moreira, "On asymptotic estimates for arithmetic cost functions," Proccedings of the American Mathematical Society, Vol. 125, no. 2, Feb. 1997, pp. 347--353.

[38]

Alexander Morgan and Andrew Sommese, "A homotopy for solving general polynomial systems that respects m-homogeneous structures," Appl. Math. Comput. 24 (1987), no. 2, pp. 101--113.

Digital Library

[39]

Christos H. Papadimitriou, Computational Complexity, Addison- Wesley, 1995.

[40]

Kaitlyn Phillipson, Quantitative Aspects of Sums of Squares and Sparse Polynomial Systems, doctoral dissertation, Texas A&M University, department of mathematics, 2016.

[41]

David A. Plaisted, "New NP-Hard and NP-Complete Polynomial and Integer Divisibility Problems," Theoret. Comput. Sci. 31 (1984), no. 1--2, pp. 125--138.

[42]

A. Pr'ekopa, "On logarithmic concave measures and functions," Acta Sci. Math. (Szeged) 34 (1975), pp. 335--343.

[43]

J. Maurice Rojas, "On the Average Number of Real Roots of Certain Random Sparse Polynomial Systems," in The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, vol. 32, (Jim Renegar, Mike Shub, and Steve Smale eds.), pp. 689-- 699, American Mathematical Society, 1996.

[44]

J. Maurice Rojas, "Why Polyhedra Matter in Non-Linear Equation Solving," in: Contemporary Mathematics, vol. 334, pp. 293-- 320, American Mathematical Society, 2003.

[45]

J. Maurice Rojas and Yinyu Ye, "On Solving Sparse Polynomials in Logarithmic Time," Journal of Complexity, special issue for the 2002 Foundations of Computation Mathematics (FOCM) meeting, February 2005, pp. 87--110.

Digital Library

[46]

Michael Sagraloff, "A near-optimal algorithm for computing real roots of sparse polynomials," in Proc. ISSAC 2014 (39th International Symposium on Symbolic and Algebraic Computation), pp. 359--366, ACM Press, 2014.

Digital Library

[47]

Mike Shub, "Complexity of Bezouts Theorem VI: Geodesics in the Condition (Number) Metric," Foundations of Computational Mathematics 9(2):171--178, January 2009.

Digital Library

[48]

Mike Shub and Steve Smale, "The Complexity of Bezout's Theorem II: Volumes and Probabilities," Computational Algebraic Geometry (F. Eyssette and A. Galligo, Eds.), pp. 267--285, Birkhauser, 1992.

[49]

Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012.

[50]

Steve Smale, "Newton's Method Estimates from Data at One Point," The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (Laramie, Wyo., 1985), pp. 185--196, Springer, New York, 1986.

[51]

Steve Smale, "Mathematical Problems for the Next Century," Math. Intelligencer 20 (1998), no. 2, pp. 7--15.

[52]

Steve Smale, "Mathematical Problems for the Next Century," Mathematics: Frontiers and Perspectives, pp. 271--294, Amer. Math. Soc., Providence, RI, 2000.

[53]

Joseph H. Silverman and John Tate, Rational Points on Elliptic Curves, Undergraduate Texts in Mathematics, Springer, corrected edition, 1994.

[54]

H. J. S. Smith, "On Systems of Integer Equations and Congruences," Philos. Trans. 151, pp. 293--326 (1861).

[55]

Andrew J. Sommese and Charles W. Wampler, "The Numerical Solution to Systems of Polynomials Arising in Engineering and Science," World Scientific, Singapore, 2005.

[56]

Arne Storjohann, "Algorithms for matrix canonical forms," doctoral dissertation, Swiss Federal Institute of Technology, Zurich, 2000.

[57]

Terence Tao and Van Vu, "From the Littlewood-Offord Problem to the Circular Law: Universality of the Spectral Distribution of Random Matrices," Bulletin of the American Mathematical Society, vol. 46, no. 3, July 2009, pp. 377--396.

[58]

Terence Tao and Van Vu, "Local Universality of Zeroes of Random Polynomials," IMRN, Vol. 2015, Issue 13, 2015, pp. 5053-- 5139.

[59]

Virginia Vassilevska Williams, "Multiplying matrices in time," submitted for publication (earlier version in proceedings of STOC 2012 (ACM Symposium on Theory of Computing, May 19--22, NYU), ACM Press), 2014.

[60]

Jan Verschelde, "Polynomial Homotopy Continuation with PHCpack," ACM Communications in Computer Algebra 44(4):217--220, 2010.

Digital Library

[61]

Yinyu Ye, "Combining Binary Search and Newton's Method to Compute Real Roots for a Class of Real Functions," J. Complexity 10 (1994), no. 3, 271--280.

Digital Library

Cited By

Coons JCuriel MGross E(2024)Mixed volumes of networks with binomial steady-statesJournal of Symbolic Computation10.1016/j.jsc.2024.102395(102395)Online publication date: Oct-2024
https://doi.org/10.1016/j.jsc.2024.102395
Ergür AWolff T(2022)A Polyhedral Homotopy Algorithm for Real ZerosArnold Mathematical Journal10.1007/s40598-022-00219-w9:3(305-338)Online publication date: 27-Oct-2022
https://doi.org/10.1007/s40598-022-00219-w
Rojas J(2022)Counting Real Roots in Polynomial-Time via Diophantine ApproximationFoundations of Computational Mathematics10.1007/s10208-022-09599-z24:2(639-681)Online publication date: 28-Nov-2022
https://doi.org/10.1007/s10208-022-09599-z

Index Terms

A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Numeric approximation algorithms

Recommendations

On solving univariate sparse polynomials in logarithmic time
Special issue: Foundations of computational mathematics 2002 workshops

Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m = 3 we can approximate within ε all the roots of f in the interval [0,R] using just O(log(D)log(D log R/ε)) arithmetic ...
Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields

We present a deterministic $2^{O(t)}q^{\frac{t-2}{t-1}+o(1)}$ algorithm to decide whether a univariate polynomial $f$, with $t$ monomial terms and degree $<q$, has a root in the finite field $\mathbb{F}_q$. Our method is the first with complexity sublinear ...
Smale's Fundamental Theorem of Algebra Reconsidered

In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

July 2019

418 pages

ISBN:9781450360845

DOI:10.1145/3326229

General Chairs:
James Davenport
University of Bath, UK
,
Dongming Wang
Beihang University, China; Guangxi University for Nationalities, China; Centre National de la Recherche Scientifique, France
,
Program Chair:
Manuel Kauers
Johannes Kepler University, Austria
,
Publications Chair:
Russell Bradford
University of Bath, UK

Copyright © 2019 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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ISSAC '19

ISSAC '19: International Symposium on Symbolic and Algebraic Computation

July 15 - 18, 2019

Beijing, China

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
239
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Coons JCuriel MGross E(2024)Mixed volumes of networks with binomial steady-statesJournal of Symbolic Computation10.1016/j.jsc.2024.102395(102395)Online publication date: Oct-2024
https://doi.org/10.1016/j.jsc.2024.102395
Ergür AWolff T(2022)A Polyhedral Homotopy Algorithm for Real ZerosArnold Mathematical Journal10.1007/s40598-022-00219-w9:3(305-338)Online publication date: 27-Oct-2022
https://doi.org/10.1007/s40598-022-00219-w
Rojas J(2022)Counting Real Roots in Polynomial-Time via Diophantine ApproximationFoundations of Computational Mathematics10.1007/s10208-022-09599-z24:2(639-681)Online publication date: 28-Nov-2022
https://doi.org/10.1007/s10208-022-09599-z

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Table of Contents