1
$\begingroup$

Suppose you have a trigonometric polynomial of the form \begin{equation*} x(t) = \sum_{k = 0}^N a_k \cos(2 \pi k f_0 t). \end{equation*} Using Clenshaw algorithm, one can evaluate this polynomial in $O(N)$, just as an ordinary polynomial via Horner's rule. Now:

  1. Is it possible to evaluate $x(t)$ in less than $O(N)$ in general? Also negative or partial results are appreciated.
  2. What if $x(t)$ has a particular form? For example, if $a_k = \frac{(-1)^k}{k}$, $x(t)$ is the truncated Fourier series of a sawtooth wave.
  3. In case of negative answer, is there at least some fast algorithm that approximates $x(t)$?

Thank you in advance.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ While trig polynomials are often useful to assess qualitative properties, they are rarely useful to actually evaluate the function. This goes to your point (2). It is almost always better to think about what you know about the coefficients $a_k$ and whether there is a representation better suited for numerical evaluation. $\endgroup$
    – Wolfgang Bangerth
    Sep 29, 2021 at 19:09
  • $\begingroup$ In the general case, I do not know anything else on the coefficients. If this is too hard, a result on the classical waveforms (sawtooth, square, triangle, ...) would also be interesting. Notice that $x(t)$ is the real part of $\tilde x(t) = \sum_{k = 0}^N a_k e^{2 \pi i k f_0 t}$, so in some sense my problem is a particular case of (ordinary) polynomial evaluation. $\endgroup$
    – avril_14th
    Sep 29, 2021 at 22:27
  • $\begingroup$ You only get that average FFT speed for multi-point evaluations of $N$ or more values. If the evaluation points do not form an arithmetic progression, one might get numerical instability. $\endgroup$
    – Lutz Lehmann
    Sep 30, 2021 at 11:39
  • 1
    $\begingroup$ You have to read all the coefficients, so it's at least O(N). $\endgroup$
    – user14717
    Dec 6, 2021 at 17:04
  • 1
    $\begingroup$ 2) is still confusing, especially since the list of $a_k$s is assumed finite in the setup. So if the list is finite, then you have to do pattern detection and then extrapolate assume that pattern continues no? $\endgroup$
    – user14717
    Dec 8, 2021 at 0:44

0

Reset to default

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.