Achim Schweikard
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.
- 1 AKRITAS, A., COLLINS, G.E. Polynomial real root isolation using Descartes' rule of sign. In Proceedings of the ACM Symposium on Symbolic Algebraic Computation (SYMSAC) (Yorktown Heights, N.Y., 1976), 272-275. Google Scholar
- 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.Google Scholar
- 3 COLLINS, G. E., LOOS, R. Polynomial real root isolation by differentiation. In Proceedings of the ACM Symposium on Symbolic Algebraic Computation (SYMSAC) (Yorktown Heights, N.Y., 1976), 15-25. Google Scholar
- 4 COLLINS, G. E., LOOS, R. Real zeros of polynomials. In Computer Algebra, 2nd ed. B. Buchberger, G. E. Collins, R. Loos, Eds., Springer-Veclag, New York, 1982, pp. 83-94. Google Scholar
- 5 DAVENPORT, J. H., SIRET, Y., TOURNmR, E. Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic Press, London, 1988. Google Scholar
- 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.Google Scholar
- 7 EHRLICH, L. W. A modified Newton method for polynomials. Commun. ACM 10, 2 (Feb. 1967), 107 108. Google Scholar
- 8 JOHNSON, J.R. Algorithms for polynomial real root isolation. PhD dissertation, in preparation. The Ohio State Univ., 1991. Google Scholar
- 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.Google Scholar
- 10 PINKERT, J.R. An exact method for finding the roots of a complex polynomial. ACM Trans. Math. So{~w. 2, 4 (1976), 351-363. Google Scholar
- 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.Google Scholar
Index Terms
- Real zero isolation for trigonometric polynomials
Recommendations
The Asymptotic Zero Distribution of Orthogonal Polynomials with Varying Recurrence Coefficients
We study the zeros of orthogonal polynomials pn, N, n=0, 1, , that are generated by recurrence coefficients an, N and bn, N depending on a parameter N. Assuming that the recurrence coefficients converge whenever n, N tend to infinity in such a way that ...
A root isolation algorithm for sparse univariate polynomials
ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic ComputationWe consider a univariate polynomial f with real coefficients having a high degree N but a rather small number d + 1 of monomials, with d ≪ N. Such a sparse polynomial has a number of real root smaller or equal to d. Our target is to find for each real ...
Weighted trigonometric sums over a half-period
We derive formulas for evaluating weighted sums of trigonometric functions over evenly-spaced angles in the first quadrant. These results generalize those of a previous paper, where we considered trigonometric sums weighted by real, primitive, non-...
Comments