## A general approach to isolating roots of a bitstream polynomial.(English)Zbl 1229.65077

Summary: We describe a new approach to isolate the roots (either real or complex) of a square-free polynomial $$F$$ with real coefficients. It is assumed that each coefficient of $$F$$ can be approximated to any specified error bound and refer to such coefficients as bitstream coefficients. The presented method is exact, complete and deterministic. Compared to previous approaches [A. Eigenwillig, Real root isolation for exact and approximate polynomials using Descartes’ rule of signs. PhD thesis. Universität des Saarlandes (2008); A. Eigenwillig et al., Lect. Notes Comput. Sci. 3718, 138–149 (2005; Zbl 1169.65315); K. Mehlhorn and the author, J. Symb. Comput. 46, No. 1, 70–90 (2011; Zbl 1207.65048)] we improve in two aspects. Firstly, our approach can be combined with any existing subdivision method for isolating the roots of a polynomial with rational coefficients. Secondly, the approximation demand on the coefficients and the bit complexity of our approach is considerably smaller. In particular, we can replace the worst-case quantity $$\sigma (F)$$ by the average-case quantity $$\prod_{i=1} ^n\root n\of{\sigma_i}$$, where $$\sigma_i$$ denotes the minimal distance of the $$i$$-th root $$\xi_i$$ of $$F$$ to any other root of $$F$$, $$\sigma (F) := \min_i\sigma_i$$, and $$n = \deg F$$. For polynomials with integer coefficients, our method matches the best bounds known for existing practical algorithms that perform exact operations on the input coefficients.

### MSC:

 65H04 Numerical computation of roots of polynomial equations 65Y20 Complexity and performance of numerical algorithms 26C10 Real polynomials: location of zeros

### Citations:

Zbl 1169.65315; Zbl 1207.65048

ISOLATE
Full Text:

### References:

  Akritas A., Strzebonski A.: A comparative study of two root isolation methods. Nonlinear Anal. Model. Control 10, 297–304 (2005) · Zbl 1147.65310  Akritas A.G.: The fastest exact algorithms for the isolation of the real roots of a polynomial equation. Computing 24(4), 299–313 (1980) · Zbl 0428.65028  Alesina A., Galuzzi M.: A new proof of Vicent’s theorem. L’Enseignement Mathematique 44, 219–256 (1998) · Zbl 0988.12001  Beberich, E., Emeliyanenko, P., Sagraloff, M.: An elimination method for solving bivariate polynomial systems: eliminating the usual drawbacks. In: ALENEX, pp. 35–47. SIAM, Philadelphia (2011)  Berberich E., Kerber M., Sagraloff M.: An efficient algorithm for the stratification and triangulation of an algebraic surface. Comput. Geom. Theory Appl. (CGTA) 43(3), 257–278 (2009) · Zbl 1203.65037  Collins G., Johnson J., Krandick W.: Interval arithmetic in cylindrical algebraic decomposition. JSC 34, 143–155 (2002) · Zbl 1007.68210  Collins G.E., Akritas A.G.: Polynomial real root isolation using Descartes’ rule of signs. In: Jenks, R.D. (eds) Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, pp. 272–275. ACM Press, New York (1976)  Du, Z., Sharma, V., Yap, C.: Amortized bounds for root isolation via Sturm sequences. In: SNC, pp. 113–130 (2007) · Zbl 1152.65426  Eigenwillig A.: On multiple roots in Descartes’ rule and their distance to roots of higher derivatives. J. Comput. Appl. Math. 200(1), 226–230 (2007) · Zbl 1117.26014  Eigenwillig, A.: Real root isolation for exact and approximate polynomials using Descartes’ rule of signs. PhD thesis, Universität des Saarlandes (2008)  Eigenwillig, A., Kerber, M., Wolpert, N.: Fast and exact geometric analysis of real algebraic plane curves. In: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pp. 151–158 (2007) · Zbl 1190.14062  Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: An exact descartes algorithm with approximate coefficients. In: CASC. LNCS, vol. 3718, pp. 138–149 (2005) · Zbl 1169.65315  Eigenwillig, A., Sharma, V., Yap, C.: Almost tight complexity bounds for the Descartes method. In: ISSAC, pp. 71–78 (2006) · Zbl 1356.65120  Gerhard J.: Modular algorithms in symbolic summation and symbolic integration. LNCS, pp. 3218. Springer, Berlin (2004) · Zbl 1131.68121  Gourdon, X.: Combinatoire, Algorithmique et Géométrie des Polynômes. Thèse, École polytechnique (1996)  Hemmer, M., Tsigaridas, E.P., Zafeirakopoulos, Z., Emiris, I.Z., Karavelas, M.I., Mourrain, B.: Experimental evaluation and cross benchmarking of univariate real solvers. In: SNC, pp. 45–54 (2009)  Johnson J.: Algorithms for polynomial real root isolation. In: Caviness, B., Johnson, J. (eds) Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and monographs in Symbolic Computation, pp. 269–299. Springer, Berlin (1998)  Johnson J.R., Krandick W.: Polynomial real root isolation using approximate arithmetic. In: Küchlin, W. (eds) ISSAC, pp. 225–232. ACM Press, New York (1997) · Zbl 0917.65046  Kerber, M.: Geometric Algorithms for Algebraic Curves and Surfaces. PhD thesis, Universität des Saarlandes (2009)  Krandick W., Mehlhorn K.: New bounds for the Descartes method. J. Symb. Comput. 41(1), 49–66 (2006) · Zbl 1158.12001  Lickteig T., Roy M.-F.: Sylvester-Habicht sequences and fast Cauchy index computation. J. Symb. Comput. 31, 315–341 (2001) · Zbl 0976.65043  Mehlhorn K., Ray S.: Faster algorithms for computing Hong’s bound on absolute positiveness. J. Symb. Comput. 45((6), 677–683 (2010) · Zbl 1206.11151  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  Mitchell, D.P.: Robust ray intersection with interval arithmetic. In: Graphics Interface’90, pp. 68–74 (1990)  Mourrain, B., Rouillier, F., Roy, M.-F.: The Bernstein basis and real root isolation. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, number 52 in MSRI Publications, pp. 459–478. Cambridge University Press, Cambridge (2005) · Zbl 1094.14051  Pan V.Y.: Sequential and parallel complexity of approximate evaluation of polynomial zeros. Comput. Math. Appl. 14(8), 591–622 (1987) · Zbl 0634.65036  Pan V.Y.: Solving a polynomial equation: some history and recent progress. SIAM Rev. 39(2), 187–220 (1997) · Zbl 0873.65050  Rouillier F., Zimmermann P.: Efficient isolation of [a] polynomial’s real roots. J. Comput. Appl. Math. 162, 33–50 (2004) · Zbl 1040.65041  Sagraloff, M., Yap, C.: A simple but exact and efficient algorithm for complex root isolation. In: International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 353–360 (2011) · Zbl 1323.65051  Schönhage, A.: The fundamental theorem of algebra in terms of computational complexity, 1982. Manuscript, Department of Mathematics, University of Tübingen. Updated (2004) · Zbl 0538.68035  Schönhage A.: Quasi-GCD computations. J. Complex. 1(1), 118–137 (1985) · Zbl 0586.68031  Sharma V.: Complexity of real root isolation using continued fractions. Theor. Comput. Sci. 409, 292–310 (2008) · Zbl 1158.68055  Smale S.: The fundamental theorem of algebra and complexity theory. Bull. (N.S.) AMS 4(1), 1–36 (1981) · Zbl 0456.12012  Smith B.T.: Error bounds for zeros of a polynomial based upon Gerschgorin’s theorems. J. ACM 17(4), 661–674 (1970) · Zbl 0215.27305  Tsigaridas E.P., Emiris I.Z.: On the complexity of real root isolation using continued fractions. Theor. Comput. Sci. 392(1–3), 158–173 (2008) · Zbl 1134.68067  Vincent A.J.H.: Sur la résolution des equations numériques. Journal de Mathématiques Pures et Appliquées 1, 341–372 (1836)  Yap C.K.: Fundamental Problems in Algorithmic Algebra. Oxford University Press, UK (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.