Avaliação rápida (aproximada) do polinômio de Chebyshev

Existe uma maneira preferida de como implementar uma avaliação rápida (aproximada) do polinômio de interpolação de Chebyshev em grade uniforme (considerando os valores de função nos nós de Chebyshev)? Meu problema é que a interpolação se torna lenta quando o grau do polinômio interpolador aumenta.

As seguintes idéias vieram à minha mente:

• Tente adaptar técnicas não uniformes de FFT (NFFT)
• Use a FFT para calcular as derivações nos nós Chebyshev, potencialmente depois de ir primeiro para uma grade mais fina (Chebyshev). Em seguida, use uma interpolação cúbica por partes para avaliação (aproximada).
• Use alguma fórmula que use apenas valores de função (e potencialmente derivados) em nós Chebyshev "próximos" (isso está relacionado a uma técnica NFFT específica).

Você já pensou em usar a interpolação baricêntrica ? Uma descrição detalhada de como fazê-lo eficientemente para os nós Chebyshev é fornecida na Seção 5 deste documento.

$n$$m$$\mathcal O(nm)$

Atualizar

Outra alternativa, se você tiver os coeficientes de Chebyshev do seu polinômio interpolatório, é usar o algoritmo de Clenshaw . Se você tiver apenas os valores da função nos nós Chebyshev, mas precisar avaliar o polinômio várias vezes, poderá calcular os coeficientes com uma FFT.

O algoritmo de Clenshaw é um pouco mais rápido que a interpolação baricêntrica, pois requer apenas adições e multiplicações, e também vetoriza bastante.