×

zbMATH — the first resource for mathematics

Univariate real root isolation over a single logarithmic extension of real algebraic numbers. (English) Zbl 1393.11086
Kotsireas, Ilias S. (ed.) et al., Applications of computer algebra, Kalamata, Greece, July 20–23, 2015. Cham: Springer (ISBN 978-3-319-56930-7/hbk; 978-3-319-56932-1/ebook). Springer Proceedings in Mathematics & Statistics 198, 425-445 (2017).
Summary: We present algorithmic, complexity, and implementation results for the problem of isolating the real roots of a univariate polynomial \(B \in L[x]\), where \(L=\mathbb {Q} [ \lg (\alpha)]\) and \(\alpha \) is a positive real algebraic number. The algorithm approximates the coefficients of \( B\) up to a sufficient accuracy and then solves the approximate polynomial. For this we derive worst-case (aggregate) separation bounds. We also estimate the expected number of real roots when we draw the coefficients from a specific distribution and illustrate our results experimentally. A generalization to bivariate polynomial systems is also presented. We implemented the algorithm in C as part of the core library of mathematica for the case \(B \in \mathbb {Z} [ \lg (q)][x]\) where \( q\) is positive rational number and we demonstrate its efficiency over various data sets.
For the entire collection see [Zbl 1379.13001].
MSC:
11Y16 Number-theoretic algorithms; complexity
11R04 Algebraic numbers; rings of algebraic integers
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
68W30 Symbolic computation and algebraic computation
Software:
ISOLATE; Mathematica
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. Alefeld, G., Herzberger, J.: Introduction to Interval Computations. Academic Press, New York (1983) · Zbl 0552.65041
[2] 2. Baker, A.: Linear forms in the logarithms of algebraic numbers (IV). Mathematika 15 (02), 204-216 (1968) · Zbl 0169.37802
[3] 3. Baker, A.: The theory of linear forms in logarithms. In: Transcendence Theory: Advances and Applications, pp. 1-27 (1977)
[4] 4. Bates, D.J., Sottile, F.: Khovanskii-Rolle continuation for real solutions. Found. Comput. Math. 11 (5), 563-587 (2011) · Zbl 1231.14047
[5] 5. Bodrato, M., Zanoni, A.: Long integers and polynomial evaluation with Estrin’s scheme. In: Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pp. 39-46. IEEE (2011) · Zbl 1373.11085
[6] 6. Bouzidi, Y., Lazard, S., Moroz, G., Pouget, M., Rouillier, F., Sagraloff, M.: Solving bivariate systems using rational univariate representations. J. Complex. 37 , 34-75 (2016) · Zbl 1351.65033
[7] 7. Brent, R.: Fast multiple-precision evaluation of elementary functions. J. ACM 23 (2), 242-251 (1976) · Zbl 0324.65018
[8] 8. Brent, R., Zimmermann, P.: Modern Computer Arithmetic. Cambridge University Press, Cambridge (2010) · Zbl 1230.68014
[9] 9. Cheng, J.-S., Gao, X.-S., Yap, C.-K.: Complete numerical isolation of real roots in zero-dimensional triangular systems. J. Symb. Comput. 44 , 768-785 (2009) · Zbl 1169.13017
[10] 10. Davenport, J.H.: Cylindrical algebraic decomposition. Technical Report 88-10, School of Mathematical Sciences, University of Bath, England (1988).
[11] 11. Dedieu, J., Yakoubsohn, J.: Computing the real roots of a polynomial by the exclusion algorithm. Numer. Algorithms 4 (1), 1-24 (1993) · Zbl 0774.65028
[12] 12. Diochnos, D.I., Emiris, I.Z., Tsigaridas, E.P.: On the asymptotic and practical complexity of solving bivariate systems over the reals. J. Symb. Comput. 44 (7), 818-835 (2009) · Zbl 1169.13306
[13] 13. Du, Z., Sharma, V., Yap, C.K.: Amortized bound for root isolation via Sturm sequences. In: Wang, D., Zhi, L. (eds.) International Workshop on Symbolic Numeric Computing (SNC), pp. 113-129. Birkhauser, Beihang University, Beijing (2005) · Zbl 1152.65426
[14] 14. Edelman, A., Kostlan, E.: How may zeros of a random polynomial are real? Bull. AMS 32 (1), 1-37 (1995) · Zbl 0820.34038
[15] 15. Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: A descartes algorithm for polynomials with bit-stream coefficients. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds.) CASC. LNCS, vol. 3718, pp. 138-149. Springer (2005) · Zbl 1169.65315
[16] 16. Emiris, I.Z., Galligo, A., Tsigaridas, E.P.: Random polynomials and expected complexity of bisection methods for real solving. In: Watt, S. (ed.) Proceedings of the 35th ACM International Symposium on Symbolic & Algebraic Computation (ISSAC), pages 235-242, Munich, Germany. ACM, New York (2010) · Zbl 1321.68308
[17] 17. Emiris, I.Z., Mourrain, B., Tsigaridas, E.P.: The DMM bound: multivariate (aggregate) separation bounds. In: Proceedings of the 35th ACM International Symposium on Symbolic & Algebraic Computation (ISSAC), pp. 243-250, Munich, Germany. ACM (2010) · Zbl 1321.68528
[18] 18. Eppstein, D., Paterson, M.S., Yao, F.F.: On nearest-neighbor graphs. Discret. Comput. Geom. 17 (3), 263-282 (1997) · Zbl 0874.60014
[19] 19. Escorcielo, P., Perrucci, D.: On the davenport-mahler bound (2016). arXiv preprint · Zbl 1371.05246
[20] 20. Giusti, M., Lecerf, G., Salvy, B., Yakoubsohn, J.-C.: On location and approximation of clusters of zeros of analytic functions. Found. Comput. Math. 5 (3), 257-311 (2005) · Zbl 1109.65046
[21] 21. Johnson, J., Krandick, W.: Polynomial real root isolation using approximate arithmetic. In: Proceedings of the Intertnational Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 225-232. ACM (1997) · Zbl 0917.65046
[22] 22. Johnson, J.R.: Algorithms for polynomial real root isolation. PhD thesis, The Ohio State University (1991)
[23] 23. Lu, Z., He, B., Luo, Y., Pan, L.: An algorithm of real root isolation for polynomial system. In: Wang, D., Zhi, L. (eds.) Proceedings of the 1st ACM International Work. Symbolic Numeric Computation (SNC), pp. 94-107 (2005)
[24] 24. Mantzaflaris, A., Mourrain, B., Tsigaridas, E.P.: On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers. Theor. Comput. Sci. 412 (22), 2312-2330 (2011) · Zbl 1243.12005
[25] 25. McNamee, J.M., Pan, V.Y.: Numerical Methods for Roots of Polynomials (II), chapter 15. Elsevier (2013)
[26] 26. Mehlhorn, K., Sagraloff, M.: A deterministic algorithm for isolating real roots of a real polynomial. J. Symb. Comput. 46 (1), 70-90 (2011) · Zbl 1207.65048
[27] 27. Mehlhorn, K., Sagraloff, M., Wang, P.: From approximate factorization to root isolation with application to cylindrical algebraic decomposition. J. Symb. Comput. 66 , 34-69 (2015) · Zbl 1357.68305
[28] 28. Mignotte, M.: Mathematics for Computer Algebra. Springer, New York (1992) · Zbl 0741.11002
[29] 29. Mignotte, M., Waldschmidt, M.: Linear forms in two logarithms and Schneider’s method. Math. Ann. 231 (3), 241-267 (1978) · Zbl 0349.10029
[30] 30. Pan, V.: Univariate polynomials: nearly optimal algorithms for numerical factorization and rootfinding. J. Symb. Comput. 33 (5), 701-733 (2002) · Zbl 1004.65061
[31] 31. Pan, V.Y., Tsigaridas, E.P.: On the boolean complexity of real root refinement. In: Kauers, M. (ed.) Proc. Int’l Symp. on Symb. and Algebraic Comp. (ISSAC), pp. 299-306, Boston, USA. ACM (2013) · Zbl 1360.65140
[32] 32. Rouillier, F., Zimmermann, Z.: Efficient isolation of polynomial’s real roots. J. Comput. Appl. Math. 162 (1), 33-50 (2004) · Zbl 1040.65041
[33] 33. Sagraloff, M.: On the complexity of real root isolation. abs/1011.0344v1 (2010)
[34] 34. Schönhage, A.: The fundamental theorem of algebra in terms of computational complexity. Manuscript. Univ. of Tübingen, Germany, 1982.
[35] 35. Strzeboński, A., Tsigaridas, E.P.: Univariate real root isolation in an extension field. In: Leykin, A. (ed.) Proc. 36th ACM Int’l Symp. on Symbolic & Algebraic Comp. (ISSAC), pp. 321-328, San Jose, CA, USA. ACM (2011) · Zbl 1323.68628
[36] 36. Strzeboński, A., Tsigaridas, E.P.: Univariate real root isolation in multiple extension fields. In: Proc. 37th ACM Int’l Symp. on Symbolic & Algebraic Comp. (ISSAC), pp. 343-350, Grenoble, France. ACM (2012) · Zbl 1323.68629
[37] 37. Tsigaridas, E.P., Emiris, I.Z.: On the complexity of real root isolation using continued fractions. Theor. Comput. Sci. 392 , 158-173 (2008) · Zbl 1134.68067
[38] 38. von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, New York (2013) · Zbl 1277.68002
[39] 39. Xia, B., Yang, L.: An algorithm for isolating the real solutions of semi-algebraic systems. J. Symb. Comput. 34 , 461-477 (2002) · Zbl 1027.68150
[40] 40. Xia, B., Zhang, T.: Real solution isolation using interval arithmetic. Comput. Math. Appl. 52 , 853-860 (2006) · Zbl 1131.65041
[41] 41. Yakoubsohn, J.: Approximating the zeros of analytic functions by the exclusion algorithm. Numer. Algorithms 6 (1), 63-88 (1994) · Zbl 0790.65038
[42] 42. Yakoubsohn, J.-C.: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions. J. Complex. 21 (5), 652-690 (2005) · Zbl 1084.65055
[43] 43. Yap, C.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York (2000) · Zbl 0999.68261
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.