research-article

Random polynomials and expected complexity of bisection methods for real solving

Authors:

Ioannis Z. Emiris,

André Galligo,

Elias P. TsigaridasAuthors Info & Claims

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

Pages 235 - 242

https://doi.org/10.1145/1837934.1837980

Published: 25 July 2010 Publication History

Abstract

Our probabilistic analysis sheds light to the following questions: Why do random polynomials seem to have few, and well separated real roots, on the average? Why do exact algorithms for real root isolation may perform comparatively well or even better than numerical ones?

We exploit results by Kac, and by Edelman and Kostlan in order to estimate the real root separation of degree d polynomials with i.i.d. coefficients that follow two zero-mean normal distributions: for SO(2) polynomials, the i-th coefficient has variance (d/i), whereas for Weyl polynomials its variance is 1/i!. By applying results from statistical physics, we obtain the expected (bit) complexity of STURM solver, Õ_B(rd²τ), where r is the number of real roots and τ the maximum coefficient bitsize. Our bounds are two orders of magnitude tighter than the record worst case ones. We also derive an output-sensitive bound in the worst case.

The second part of the paper shows that the expected number of real roots of a degree d polynomial in the Bernstein basis is √2d ± O(1), when the coefficients are i.i.d. variables with moderate standard deviation. Our paper concludes with experimental results which corroborate our analysis.

References

[1]

A. Akritas. An implementation of Vincent's theorem. Numerische Mathematik, 36:53--62, 1980.

Digital Library

[2]

D. Armentano and J.-P. Dedieu. A note about the average number of real roots of a Bernstein polynomial system. J. Complexity, 25(4):339--342, 2009.

Digital Library

[3]

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

[4]

P. Bleher and X. Di. Correlations between zeros of a random polynomial. J. Stat. Physics, 88(1):269--305, 1997.

[5]

A. Bloch and G. Polya. On the roots of certain algebraic equations. Proc. London Math. Soc, 33:102--114, 1932.

[6]

C-P. Chen and F. Qi. The best bound in Wallis' inequality. Proc. AMS, 133(2):397--401, 2004.

[7]

J. H. Davenport. Cylindrical algebraic decomposition. Technical Report 88--10, School of Mathematical Sciences, University of Bath, England, http://www.bath.ac.uk/masjhd/, 1988.

[8]

Z. Du, V. Sharma, and C. K. Yap. Amortized bound for root isolation via Sturm sequences. In D. Wang and L. Zhi, editors, Int. Workshop on Symbolic Numeric Computing, pages 113--129, Beijing, China, 2005. Birkhauser.

[9]

A. Edelman and E. Kostlan. How may zeros of a random polynomial are real? Bulletin AMS, 32(1):1--37, 1995.

[10]

A. Eigenwillig, V. Sharma, and C. K. Yap. Almost tight recursion tree bounds for the Descartes method. In Proc. Annual ACM ISSAC, pages 71--78, New York, USA, 2006.

Digital Library

[11]

I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. Real Algebraic Numbers: Complexity Analysis and Experimentation. In P. Hertling, C. Hoffmann, W. Luther, and N. Revol, editors, Reliable Implementations of Real Number Algorithms: Theory and Practice, volume 5045 of LNCS, pages 57--82, 2008.

Digital Library

[12]

P. Erdös and P. Turán. On the distribution of roots of polynomials. Annals of Mathematics, 51(1):105--119, 1950.

[13]

J. M. Hammersley. The zeros of a random polynomial. In Proc. of the 3rd Berkeley Symposium on Mathematical Statistics and Probability, volume 1955, pages 89--111, 1954.

[14]

J. H. Hannay. Chaotic analytic zero points: exact statistics for those of a random spin state. J. Physics A: Math. & General, 29:L101--L105, 1996.

[15]

L. E. Heindel. Integer arithmetic algorithms for polynomial real zero determination. J. of the Association for Computing Machinery, 18(4):533--548, October 1971.

Digital Library

[16]

H. Hong. Bounds for absolute positiveness of multivariate polynomials. J. Symbolic Comp., 25(5):571--585, 1998.

Digital Library

[17]

C. P. Hughes and A. Nikeghbali. The zeros of random polynomials cluster uniformly near the unit circle. Compositio Mathematica, 144:734--746, Mar 2008.

[18]

J. R. Johnson. Algorithms for Polynomial Real Root Isolation. PhD thesis, The Ohio State University, 1991.

Digital Library

[19]

J. R. Johnson, W. Krandick, K. Lynch, D. Richardson, and A. Ruslanov. High-performance implementations of the Descartes method. In Proc. Annual ACM ISSAC, pages 154--161, NY, 2006.

Digital Library

[20]

M. Kac. On the average number of real roots of a random algebraic equation. Bulletin AMS, 49:314--320 & 938, 1943.

[21]

E. Kowalski. Bernstein polynomials and Brownian motion. American Mathematical Monthly, 113(10):865--886, 2006.

[22]

W. Krandick. Isolierung reeller nullstellen von polynomen. In J. Herzberger, editor, Wissenschaftliches Rechnen, pages 105--154. Akademie-Verlag, Berlin, 1995.

[23]

T. Lickteig and M-F. Roy. Sylvester-Habicht Sequences and Fast Cauchy Index Computation. J. Symb. Comput., 31(3):315--341, 2001.

Digital Library

[24]

J. E. Littlewood and A. C. Offord. On the number of real roots of a random algebraic equation. J. London Math. Soc, 13:288--295, 1938.

[25]

K. Mehlhorn and S. Ray. Faster algorithms for computing Hong's bound on absolute positiveness. J. Symbolic Computation, 45(6):677--683, 2010.

Digital Library

[26]

M. Mignotte and D. Ştefănescu. Polynomials: An algorithmic approach. Springer, 1999.

[27]

V. Y. Pan. Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding. J. Symbolic Computation, 33(5):701--733, 2002.

Digital Library

[28]

A. Papoulis and S. U. Pillai. Probability, random variables, and stochastic processes. McGraw-Hill, 3rd edition, 1991.

[29]

D. Reischert. Asymptotically fast computation of subresultants. In Proc. Annual ACM ISSAC, pages 233--240, 1997.

Digital Library

[30]

F. Rouillier and Z. Zimmermann. Efficient isolation of polynomial's real roots. J. Comput. & Applied Math., 162(1):33--50, 2004.

Digital Library

[31]

G. Schehr and S. N. Majumdar. Real roots of random polynomials and zero crossing properties of diffusion equation. J. Stat. Physics, 132(2):235--273, 2008.

[32]

A. Schönhage. The fundamental theorem of algebra in terms of computational complexity. Manuscript. Univ. of Tübingen, Germany, 1982.

[33]

V. Sharma. Complexity of real root isolation using continued fractions. Theor. Comput. Sci., 409(2):292--310, 2008.

Digital Library

[34]

M. Shub and S. Smale. Complexity of bézout's theorem II: volumes and probabilities. In F. Eyssette and A. Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267--285. Birkhäuser, 1993.

[35]

E. P. Tsigaridas and I. Z. Emiris. On the complexity of real root isolation using Continued Fractions. Theoretical Computer Science, 392:158--173, 2008.

Digital Library

[36]

C. K. Yap. Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York, 2000.

Digital Library

Cited By

Praharaj SGuha S(2023)An Interesting Class of Non-Kac Random PolynomialsJournal of the Indian Society for Probability and Statistics10.1007/s41096-023-00166-524:2(545-564)Online publication date: 10-Oct-2023
https://doi.org/10.1007/s41096-023-00166-5
Ergür ATonelli-Cueto JTsigaridas EMaza MZhi L(2022)Beyond Worst-Case Analysis for Root Isolation AlgorithmsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535475(139-148)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535475
Duong MTran HHan T(2018)On the Expected Number of Internal Equilibria in Random Evolutionary Games with Correlated Payoff MatrixDynamic Games and Applications10.1007/s13235-018-0276-49:2(458-485)Online publication date: 28-Jul-2018
https://doi.org/10.1007/s13235-018-0276-4
Show More Cited By

Index Terms

Random polynomials and expected complexity of bisection methods for real solving
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The DMM bound: multivariate (aggregate) separation bounds
ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (DMM), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the ...
Symbolic-Numeric Computation of the Bernstein Coefficients of a Polynomial from Those of One of Its Partial Derivatives and of the Product of Two Polynomials
Computer Algebra in Scientific Computing
Abstract
The expansion of a given multivariate polynomial into Bernstein polynomials is considered. Matrix methods for the calculation of the Bernstein expansion of the product of two polynomials and of the Bernstein expansion of a polynomial from the ...
Approximation of multivariate function by using new multivariate Bernstein α-polynomials

In this paper the approximation of multivariate function by using multivariate Bernstein @a-polynomials is considered. The Bernstein @a-polynomials are given and an identity is constructed. With these the well-known multivariate Bernstein approximation ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

July 2010

366 pages

ISBN:9781450301503

DOI:10.1145/1837934

Program Chair:
Wolfram Koepf
London, Ontario, Canada

Copyright © 2010 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 ACM 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]

Sponsors

Gesellschaft fur Informtatik

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: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

ISSAC '10

Sponsor:

ISSAC '10: International Symposium on Symbolic and Algebraic Computation

July 25 - 28, 2010

Munich, Germany

Acceptance Rates

ISSAC '10 Paper Acceptance Rate 45 of 110 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
138
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Praharaj SGuha S(2023)An Interesting Class of Non-Kac Random PolynomialsJournal of the Indian Society for Probability and Statistics10.1007/s41096-023-00166-524:2(545-564)Online publication date: 10-Oct-2023
https://doi.org/10.1007/s41096-023-00166-5
Ergür ATonelli-Cueto JTsigaridas EMaza MZhi L(2022)Beyond Worst-Case Analysis for Root Isolation AlgorithmsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535475(139-148)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535475
Duong MTran HHan T(2018)On the Expected Number of Internal Equilibria in Random Evolutionary Games with Correlated Payoff MatrixDynamic Games and Applications10.1007/s13235-018-0276-49:2(458-485)Online publication date: 28-Jul-2018
https://doi.org/10.1007/s13235-018-0276-4
Strzeboński ATsigaridas E(2017)Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic NumbersApplications of Computer Algebra10.1007/978-3-319-56932-1_27(425-445)Online publication date: 27-Jul-2017
https://doi.org/10.1007/978-3-319-56932-1_27
Kerber MSagraloff M(2015)Root refinement for real polynomials using quadratic interval refinementJournal of Computational and Applied Mathematics10.1016/j.cam.2014.11.031280:C(377-395)Online publication date: 15-May-2015
https://dl.acm.org/doi/10.1016/j.cam.2014.11.031
Tsigaridas E(2014)Algebraic Algorithms*Computing Handbook, Third Edition10.1201/b16812-13(1-30)Online publication date: 8-May-2014
https://doi.org/10.1201/b16812-13
Pan VTsigaridas EMonagan MCooperman GGiesbrecht M(2013)On the boolean complexity of real root refinementProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465938(299-306)Online publication date: 26-Jun-2013
https://dl.acm.org/doi/10.1145/2465506.2465938
McNamee JPan V(2013)Nearly Optimal Universal Polynomial Factorization and Root-FindingNumerical Methods for Roots of Polynomials - Part II10.1016/B978-0-444-52730-1.00009-6(633-717)Online publication date: 2013
https://doi.org/10.1016/B978-0-444-52730-1.00009-6
Bordenave CChafaï D(2012)Around the circular lawProbability Surveys10.1214/11-PS1839:noneOnline publication date: 1-Jan-2012
https://doi.org/10.1214/11-PS183
Sharma VYap Cvan der Hoeven Jvan Hoeij M(2012)Near optimal tree size bounds on a simple real root isolation algorithmProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442875(319-326)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442875
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten