# Fast computation of the zeros of a trigonometric polynomial

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[.$$

• 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)? – GertVdE Jan 28 '20 at 9:47
• What programming language are you using? – nicoguaro Jan 28 '20 at 16:59
• @GertVdE yes that seems to be way to go. I have collected some references in my reply below – Arrigo Jan 28 '20 at 19:09
• @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 – Arrigo Jan 28 '20 at 19:12
• In that case, have you checked "Approximation Theory and Approximation Practice" by Nick Trefethen? – nicoguaro Jan 28 '20 at 19:23

## 1 Answer

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.