I am wondering what is the fastest way to compute the zeroes of the trigonometric polynomial

$$ T(x) = \sum_{i=1}^La_i\sin\big(2\pi(a_i x) - \phi_i \big), \\ a_i \in \mathbb{N}, \\ \phi_i \in \left[-\pi,\pi\right[, \\ x \in \left[-\frac{1}{2},+\frac{1}{2}\right[. $$

  • 1
    $\begingroup$ Did you try converting the sum to a Chebyshev series and then using the colleague matrix approach (i.e. calculating the eigenvalues of a special companion matrix)? $\endgroup$ – GertVdE Jan 28 '20 at 9:47
  • $\begingroup$ What programming language are you using? $\endgroup$ – nicoguaro Jan 28 '20 at 16:59
  • 2
    $\begingroup$ @GertVdE yes that seems to be way to go. I have collected some references in my reply below $\endgroup$ – Arrigo Jan 28 '20 at 19:09
  • $\begingroup$ @nicoguaro mainly MATLAB and Julia. I know that Chebfun can compute the zeroes easily, however I'm more interested in the algorithm than in the software implementation right now $\endgroup$ – Arrigo Jan 28 '20 at 19:12
  • 1
    $\begingroup$ In that case, have you checked "Approximation Theory and Approximation Practice" by Nick Trefethen? $\endgroup$ – nicoguaro Jan 28 '20 at 19:23

It all boils down to building a certain matrix from the polynomial coefficients and computing its eigenvalues. John Boyd did a lot of work in this area, these are some relevant papers:

Boyd, John P. "A Fourier companion matrix (multiplication matrix) with real-valued elements: Finding the roots of a trigonometric polynomial by matrix eigensolving." Numerical Mathematics: Theory, Methods and Applications 6.4 (2013): 586-599.

Boyd, John P. "Computing the zeros of a Fourier series or a Chebyshev series or general orthogonal polynomial series with parity symmetries." Computers & Mathematics with Applications 54.3 (2007): 336-349.

Boyd, John P. "A comparison of companion matrix methods to find roots of a trigonometric polynomial." Journal of Computational Physics 246 (2013): 96-112.

Boyd, John P. "Finding the zeros of a univariate equation: proxy rootfinders, Chebyshev interpolation, and the companion matrix." SIAM review 55.2 (2013): 375-396.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.