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

Sagraloff, Michael

Math. Comput. Sci. 4, No. 4, 481-506 (2010).

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

Keywords:

real polynomial; root isolation; bitstream coefficients; root perturbation bounds; adaptive precision management

Citations:

Zbl 1169.65315; Zbl 1207.65048

Software:

ISOLATE

References:

[1]	Akritas A., Strzebonski A.: A comparative study of two root isolation methods. Nonlinear Anal. Model. Control 10, 297–304 (2005) · Zbl 1147.65310
[2]	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
[3]	Alesina A., Galuzzi M.: A new proof of Vicent’s theorem. L’Enseignement Mathematique 44, 219–256 (1998) · Zbl 0988.12001
[4]	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)
[5]	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
[6]	Collins G., Johnson J., Krandick W.: Interval arithmetic in cylindrical algebraic decomposition. JSC 34, 143–155 (2002) · Zbl 1007.68210
[7]	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)
[8]	Du, Z., Sharma, V., Yap, C.: Amortized bounds for root isolation via Sturm sequences. In: SNC, pp. 113–130 (2007) · Zbl 1152.65426
[9]	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
[10]	Eigenwillig, A.: Real root isolation for exact and approximate polynomials using Descartes’ rule of signs. PhD thesis, Universität des Saarlandes (2008)
[11]	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
[12]	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
[13]	Eigenwillig, A., Sharma, V., Yap, C.: Almost tight complexity bounds for the Descartes method. In: ISSAC, pp. 71–78 (2006) · Zbl 1356.65120
[14]	Gerhard J.: Modular algorithms in symbolic summation and symbolic integration. LNCS, pp. 3218. Springer, Berlin (2004) · Zbl 1131.68121
[15]	Gourdon, X.: Combinatoire, Algorithmique et Géométrie des Polynômes. Thèse, École polytechnique (1996)
[16]	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)
[17]	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)
[18]	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
[19]	Kerber, M.: Geometric Algorithms for Algebraic Curves and Surfaces. PhD thesis, Universität des Saarlandes (2009)
[20]	Krandick W., Mehlhorn K.: New bounds for the Descartes method. J. Symb. Comput. 41(1), 49–66 (2006) · Zbl 1158.12001
[21]	Lickteig T., Roy M.-F.: Sylvester-Habicht sequences and fast Cauchy index computation. J. Symb. Comput. 31, 315–341 (2001) · Zbl 0976.65043
[22]	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
[23]	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
[24]	Mitchell, D.P.: Robust ray intersection with interval arithmetic. In: Graphics Interface’90, pp. 68–74 (1990)
[25]	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
[26]	Pan V.Y.: Sequential and parallel complexity of approximate evaluation of polynomial zeros. Comput. Math. Appl. 14(8), 591–622 (1987) · Zbl 0634.65036
[27]	Pan V.Y.: Solving a polynomial equation: some history and recent progress. SIAM Rev. 39(2), 187–220 (1997) · Zbl 0873.65050
[28]	Rouillier F., Zimmermann P.: Efficient isolation of [a] polynomial’s real roots. J. Comput. Appl. Math. 162, 33–50 (2004) · Zbl 1040.65041
[29]	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
[30]	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
[31]	Schönhage A.: Quasi-GCD computations. J. Complex. 1(1), 118–137 (1985) · Zbl 0586.68031
[32]	Sharma V.: Complexity of real root isolation using continued fractions. Theor. Comput. Sci. 409, 292–310 (2008) · Zbl 1158.68055
[33]	Smale S.: The fundamental theorem of algebra and complexity theory. Bull. (N.S.) AMS 4(1), 1–36 (1981) · Zbl 0456.12012
[34]	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
[35]	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
[36]	Vincent A.J.H.: Sur la résolution des equations numériques. Journal de Mathématiques Pures et Appliquées 1, 341–372 (1836)
[37]	Yap C.K.: Fundamental Problems in Algorithmic Algebra. Oxford University Press, UK (2000) · Zbl 0999.68261