Integer arithmetic algorithms for polynomial real zero determination

ABSTRACT

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.

REFERENCES

• 1: Collins, G. E., "Computing Time Analyses for Some Arithmetic and Algorithms," Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, R. G. Tobey, Editor, IBM Boston Programming Center, (June 1969), pp. 195- 231.
• 2: Collins, G. E., Algebraic Algorithms, (to be published by Prentice-Hall, 1970).
• 3: Lee Edward Heindel, Algorithms for exact polynomial root calculation, 1971
• 4: Hurwitz, A., "Uber den Satz von Budan-Fourier," Mathematische Annalen, Vol. 71, (1912), pp. 584-591.
• 5: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: Wilf, H. S., Mathematics for the Physical Sciences, John Wiley & Sons, (New York: 1962).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Multiple precision arithmetic

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory