Optimal Covering Algorithms in Methods of Search for Solving Polynomial Equations

ABSTRACT

Covering algorithms utilized in methods of search for finding zeros of complex polynomials are investigated from both a deterministic and a probabilistic point of view. q-coverings are found to be optimal, and numerical examples of this and other types of coverings are given.

REFERENCES

• 1: FRIEDLI, A. Optimale Suchverfahren zur Bestimmung von Polynomnullstellen. Diplomarbeit, Eidgenbssiche Technische Hochschule, Zurich, March 1970, unpublished.
• 2: Peter Henrici, Methods of Search for Solving Polynomial Equations, Journal of the ACM (JACM), v.17 n.2, p.273-283, April 1970 [doi>10.1145/321574.321581]
• 3: D. H. Lehmer, A Machine Method for Solving Polynomial Equations, Journal of the ACM (JACM), v.8 n.2, p.151-162, April 1961 [doi>10.1145/321062.321064]
• 4: LEHMER, D. H. Search procedures for polynomial equation solving. In Constructive Aspects of the Fundamental Theorem of Algebra, B. Dejon and P. Henrici, Eds., Wiley, London, 1969, pp. 193-208
• 5: STEWART, G. W. III. Some topics in numerical analysis. Rep. ORNL-4303, Oak Ridge Natlonal Lab., Oak Ridge, Tenn., Sept. 1968.
• 6: STEWART, G. W. III. On lehmer's method for finding the zeros of a polynomial. Math. Comp. 28 (1969), 829-835 (with microfiche).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Measurement, Performance, Theory, Verification