7
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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, 2020 at 9:47
  • $\begingroup$ What programming language are you using? $\endgroup$
    – nicoguaro ♦
    Jan 28, 2020 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, 2020 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, 2020 at 19:12
  • 1
    $\begingroup$ In that case, have you checked "Approximation Theory and Approximation Practice" by Nick Trefethen? $\endgroup$
    – nicoguaro ♦
    Jan 28, 2020 at 19:23

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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