Real zero isolation for trigonometric polynomials

ABSTRACT

An exact and practical method for determining the number, location, and multiplicity of all real zeros of the trigonometric polynomials is described. All computations can be performed without loss of accuracy. lThe method is based on zero isolation techniques for algebraic polynomials. An efficient method for the calculation of the coefficients of a corresponding algebraic polynomial is stated. The complexity of trigonometric zero isolation depending on the degree and the coefficient size of the given trigonometric polynomial is analyzed. In an experimental evaluation, the performance of the method is compared to the performance of recently developed numeric techniques for the approximate determination of all roots of trigonometric polynomials. The case of exponential or hyperbolic polynomials is treated in an appendix.

REFERENCES

• 1: George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
• 2: ANGELOVA, E. D., SEMERDZHIEV,K. I. Methods for the simultaneous approximate derivation of the roots of algebraic, trigonometric and exponential equations. U.S.S.R. Comput. Maths. Math. Phys. 22, i (Mar. 1982), 226-232.
• 3: George E. Collins , Rüdiger Loos, Polynomial real root isolation by differentiation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.15-25, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806319]
• 4: George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 5: J. H. Davenport , Y. Siret , E. Tournier, Computer algebra: systems and algorithms for algebraic computation, Academic Press Ltd., London, UK, 1988
• 6: DENAVIT, J., HARTENBERG, R.S. A kinematic notation for lower pair mechanisms based on matrices. J. Appl. Mech. 77, 2 (June 1955), 215 221.
• 7: L. W. Ehrlich, A modified Newton method for polynomials, Communications of the ACM, v.10 n.2, p.107-108, Feb. 1967 [doi>10.1145/363067.363115]
• 8: Jeremy R. Johnson, Algorithms for polynomial real root isolation, Ohio State University, Columbus, OH, 1992
• 9: MAKPELOB, H. B., CEMEPD)KNEB, K. I.. O ~ByX auanoFax MeTo/la 3pJINXa ~IJnt O}IHOBpe- MeHHOF0 Haxo)x~/eHNYl Bcex HyJIe~ TpNrOHOMeTpNtteCKNX N 3KCnOHeHu~a~bHblx nOjINYIOMOB. )IoKnartblBonrapcKoff aKa~IeUNN HayK. Comptes rendus de l'Acaddmie bulgare des Sciences. 36, 7 (1983), 879-882.
• 10: James R. Pinkert, An Exact Method for Finding the Roots of a Complex Polynomial, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.351-363, Dec. 1976 [doi>10.1145/355705.355710]
• 11: SCHWEIK~D, A. Polynomial time collision detection for manipulator paths specified by joint motions. IEEE Trans. Robotics Autom. 7, 6 (Dec. 1991), 865-870.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
periodic functions