Integer Arithmetic Algorithms for Polynomial Real Zero Determination
Lee E. Heindel · Journal of the ACM · 1971
This paper discusses a set of algorithms which given a univariate polynomial with integer coefficients (with possible multiple zeros) and a positive rational error bound, uses infinite-precision integer arithmetic and Sturm's theorem to compute intervals containing the real zeros of the polynomial and whose lengths are less than the given error bound.The algorithms also provide a simple means of determining the number of real zeros in any interval.Theoretical computing time bounds are developed for the algorithms and some empirical results are reported.
Cited by 87 works. doi:10.1145/321662.321667 Open-access PDF
Authors
References
- The Art of Computer Programming
- A Decision Method for Elementary Algebra and Geometry
- A Decision Method for Elementary Algebra and Geometry
- Mathematics for the Physical Sciences
- Mathematics for the Physical Sciences
- The calculation of multivariate polynomial resultants
- Algorithms for exact polynomial root calculation
- Computing time analyses for some arithmetic and algebraic algorithms
- �ber den Satz von Budan-Fourier