Computing the zeros of a Fourier series or a Chebyshev series or general orthogonal polynomial series with parity symmetries

In recent years, good algorithms have been developed for finding the zeros of trigonometric polynomials and of ordinary polynomials when written in the form of a truncated Chebyshev polynomial or Legendre polynomial series. In each case, the roots can be found from the eigenvalues of a generalized Frobenius companion matrix whose elements are trivial functions of the Fourier coefficients or Chebyshev coefficients. However, the QR method for computing the companion matrix eigenvalues has a cost that grows proportionally to N3N3 where NN is the polynomial degree. (By exploiting the special structure of the companion matrices, the cost can be reduced to O(N2)O(N2), but only for large NN.) Here, we show that if the polynomial has definite parity, such as a trigonometric polynomial composed only of cosines or a polynomial that is a sum only of Chebyshev polynomials of odd degree, one can exploit these symmetries to halve the size of the problem. This reduces costs in the companion matrix method by a factor ranging between four and eight. For trigonometric polynomials, we give transformations that dramatically reduce costs even if the roots are found by an algorithm other than the companion matrix procedure. We further give reductions for trigonometric polynomials with double parity symmetries which save a factor of sixteen to a factor of sixty-four in the companion matrix algorithm. Special functions such as spherical harmonics, Mathieu functions, prolate spheroidal wavefunctions and Hough functions, all represented by truncated Fourier series with double parity, are a rich source of applications.