New bounds for the Descartes method. (English) Zbl 1158.12001
Summary: We give a new bound for the number of recursive subdivisions in the Descartes method for polynomial real root isolation. Our proof uses Ostrowski’s theory of normal power series from 1950 which has so far been overlooked in the literature [A. M. Ostrowski, Ann. Math. (2) 52, 702–707 (1950; Zbl 0039.01202)]. We combine Ostrowski’s results with a theorem of Davenport from 1985 [J. H. Davenport, Computer algebra for cylindrical algebraic decomposition, R. Inst. Technol., Dept. Numer. Anal. Comput. Sci., Stockholm, 1985, see also J. R. Johnson, in: Caviness, Bob F. (ed.) et al., Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, 1993. Wien: Springer. Texts and Monographs in Symbolic Computation, 269–299 (1998; Zbl 0906.03033)] to obtain our bound. We also characterize normality of cubic polynomials by explicit conditions on their roots and derive a generalization of one of Ostrowski’s theorems.
MSC:
| 12D10 | Polynomials in real and complex fields: location of zeros (algebraic theorems) |
| 26C10 | Real polynomials: location of zeros |
Keywords:
Polynomial real root isolation; Descartes rule of signs; modified Uspenskii method; recursion tree analysis; normal polynomials; root separation bounds; history of mathematics; Möbius transformations; coefficient sign variations; cylindrical algebraic decompositionSoftware:
ISOLATEReferences:
| [1] | Albert, A. A., An inductive proof of Descartes’ rule of signs, The American Mathematical Monthly, 50, 3, 178-180 (1943) · Zbl 0060.05004 |
| [2] | Alesina, A.; Galuzzi, M., A new proof of Vincent’s theorem, L’Enseignement Mathématique, 44, 219-256 (1998) · Zbl 0988.12001 |
| [3] | Alesina, A.; Galuzzi, M., Addendum to the paper “A new proof of Vincent’s theorem”, L’Enseignement Mathématique, 45, 379-380 (1999) |
| [4] | Anderson, J. W., Hyperbolic Geometry (1999), Springer-Verlag: Springer-Verlag London · Zbl 0934.51012 |
| [5] | Bartolozzi, M.; Franci, R., La regola dei segni dall’ enunciato di R. Descartes (1637) alla dimostrazione di C.F. Gauss (1828), Archive for History of Exact Sciences, 45, 4, 335-374 (1993) · Zbl 0785.01005 |
| [6] | Carathéodory, C., Theory of Functions of a Complex Variable, second English edition, vol. 1 (1964), Chelsea Publishing Company: Chelsea Publishing Company New York |
| [7] | Collins, G. E., The computing time of the Euclidean algorithm, SIAM Journal on Computing, 3, 1, 1-10 (1974) · Zbl 0288.68019 |
| [8] | Quantifier Elimination and Cylindrical Algebraic Decomposition, (Caviness, B. F.; Johnson, J. R. (1998), Springer-Verlag), 85-121, Reprinted (with corrections by the author) in: · Zbl 0900.03055 |
| [9] | Collins, G. E.; Akritas, A. G., Polynomial real root isolation using Descartes’ rule of signs, (Jenks, R. D., Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation (1976), ACM Press), 272-275 |
| [10] | Quantifier Elimination and Cylindrical Algebraic Decomposition, (Caviness, B. F.; Johnson, J. R. (1998), Springer-Verlag), 174-200, Reprinted in: · Zbl 0900.03052 |
| [11] | Collins, G. E.; Johnson, J. R., Quantifier elimination and the sign variation method for real root isolation, (International Symposium on Symbolic and Algebraic Computation (1989), ACM Press), 264-271 |
| [12] | Collins, G. E.; Johnson, J. R.; Krandick, W., Interval arithmetic in cylindrical algebraic decomposition, Journal of Symbolic Computation, 34, 2, 143-155 (2002) |
| [13] | Collins, G. E.; Loos, R., Real zeros of polynomials, (Buchberger, B.; Collins, G. E.; Loos, R., Computer Algebra: Symbolic and Algebraic Computation (1982), Springer-Verlag), 83-94 · Zbl 0533.68038 |
| [14] | Conkwright, N. B., Introduction to the Theory of Equations (1941), Ginn and Co · Zbl 0025.00703 |
| [15] | Davenport, J.H., 1985. Computer algebra for cylindrical algebraic decomposition. Tech. Rep., The Royal Institute of Technology, Department of Numerical Analysis and Computing Science, S-100 44, Stockholm, Sweden. Reprinted as: Technical Report 88-10, School of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom; Davenport, J.H., 1985. Computer algebra for cylindrical algebraic decomposition. Tech. Rep., The Royal Institute of Technology, Department of Numerical Analysis and Computing Science, S-100 44, Stockholm, Sweden. Reprinted as: Technical Report 88-10, School of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom |
| [16] | Decker, T.; Krandick, W., Parallel real root isolation using the Descartes method, (Banerjee, P.; Prasanna, V. K.; Sinha, B. P., High Performance Computing — HiPC’99. High Performance Computing — HiPC’99, Lecture Notes in Computer Science, vol. 1745 (1999), Springer-Verlag), 261-268 |
| [17] | Decker, T.; Krandick, W., Isoefficiency and the parallel Descartes method, (Alefeld, G.; Rohn, J.; Rump, S.; Yamamoto, T., Symbolic Algebraic Methods and Verification Methods. Symbolic Algebraic Methods and Verification Methods, Springer Mathematics (2001), Springer-Verlag), 55-67 · Zbl 1015.68238 |
| [18] | Descartes, R., The Geometry (1954), Dover Publications: Dover Publications New York, Translated from the French and Latin by D.E. Smith and M.L. Latham. With a facsimile of the first edition, 1637 · Zbl 0057.24107 |
| [19] | (Carl Friedrich Gauss: Werke, vol. 3 (1866), Königliche Gesellschaft der Wissenschaften: Königliche Gesellschaft der Wissenschaften Dieterich, Göttingen), 65-70, Reprinted in: |
| [20] | Henrici, P., Applied and Computational Complex Analysis, vol. 1 (1974), John Wiley & Sons · Zbl 0313.30001 |
| [21] | IEEE, 1985. ANSI/IEEE Std 754-1985. An American National Standard: IEEE Standard for Binary Floating-Point Arithmetic. The Institute of Electrical and Electronics Engineers, Inc., 345 East 47th Street, New York, NY 10017, USA. Reprinted as: ANSI/IEEE Standard 754-1985 for binary floating-point arithmetic. ACM SIGPLAN Notices, 22 (2), 9-25, 1987; IEEE, 1985. ANSI/IEEE Std 754-1985. An American National Standard: IEEE Standard for Binary Floating-Point Arithmetic. The Institute of Electrical and Electronics Engineers, Inc., 345 East 47th Street, New York, NY 10017, USA. Reprinted as: ANSI/IEEE Standard 754-1985 for binary floating-point arithmetic. ACM SIGPLAN Notices, 22 (2), 9-25, 1987 |
| [22] | Johnson, J. R., Algorithms for polynomial real root isolation, (Caviness, B. F.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer-Verlag), 269-299 · Zbl 0900.12001 |
| [23] | Johnson, J. R.; Krandick, W., Polynomial real root isolation using approximate arithmetic, (Küchlin, W. W., International Symposium on Symbolic and Algebraic Computation (1997), ACM Press), 225-232 · Zbl 0917.65046 |
| [24] | Krandick, W., Isolierung reeller Nullstellen von Polynomen, (Herzberger, J., Wissenschaftliches Rechnen (1995), Akademie Verlag: Akademie Verlag Berlin), 105-154 |
| [25] | (Mirsky, L.; Schoenberg, I. J.; Schwarz, W.; Wefelscheid, H., Edmund Landau: Collected Works, vol. 2 (1986), Essen: Essen Thales Verlag), 180-190, Reprinted in: · Zbl 0653.01019 |
| [26] | Lane, J. M.; Riesenfeld, R. F., Bounds on a polynomial, BIT, 21, 1, 112-117 (1981) · Zbl 0472.65041 |
| [27] | Mahler, K., An inequality for the discriminant of a polynomial, The Michigan Mathematical Journal, 11, 3, 257-262 (1964) · Zbl 0135.01702 |
| [28] | Marden, M., Ostrowski, A.M.: Note on Vincent’s theorem, Mathematical Reviews, 12, 6, 408-409 (1951) |
| [29] | Mignotte, M., An inequality about factors of polynomials, Mathematics of Computation, 28, 128, 1153-1157 (1974) · Zbl 0299.12101 |
| [30] | Mignotte, M., Some useful bounds, (Buchberger, B.; Collins, G. E.; Loos, R., Computer Algebra: Symbolic and Algebraic Computation (1982), Springer-Verlag), 259-263 · Zbl 0498.12019 |
| [31] | Alexander Ostrowski: Collected Mathematical Papers, vol. 3 (1984), Birkhäuser Verlag, pp. 414-424 · JFM 65.0222.04 |
| [32] | Alexander Ostrowski: Collected Mathematical Papers, vol. 1 (1983), Birkhäuser Verlag, pp. 728-733 · Zbl 0039.01202 |
| [33] | Alexander Ostrowski: Collected Mathematical Papers, vol. 1 (1983), Birkhäuser Verlag, pp. 785-789 · Zbl 0116.04002 |
| [34] | Richardson, D. G.; Krandick, W., Compiler-enforced memory semantics in the SACLIB computer algebra library, (International Workshop on Computer Algebra in Scientific Computing. International Workshop on Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, vol. 3718 (2005), Springer-Verlag), 330-343 · Zbl 1169.68364 |
| [35] | Rouillier, F., Zimmermann, P., 2001. Efficient isolation of a polynomial real roots. Rapport de recherche 4113, Institut National de Recherche en Informatique et en Automatique; Rouillier, F., Zimmermann, P., 2001. Efficient isolation of a polynomial real roots. Rapport de recherche 4113, Institut National de Recherche en Informatique et en Automatique · Zbl 1040.65041 |
| [36] | Rouillier, F.; Zimmermann, P., Efficient isolation of a polynomial’s real roots, Journal of Computational and Applied Mathematics, 162, 33-50 (2004) · Zbl 1040.65041 |
| [37] | Uspensky, J. V., Theory of Equations (1948), McGraw-Hill Book Company, Inc · Zbl 0005.11104 |
| [38] | van der Waerden, B. L., Modern Algebra, vol. I (1949), Frederick Ungar Publishing Co.: Frederick Ungar Publishing Co. New York · Zbl 0033.10102 |
| [39] | Vincent, M[onsieur], Sur la résolution des équations numériques, Journal de mathématiques pures et appliquées, 1, 341-372 (1836) |
| [40] | Wang, X., A simple proof of Descartes’s rule of signs, The American Mathematical Monthly, 111, 6, 525-526 (2004) · Zbl 1080.26507 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
