Let $V_{i,j}=x_i^j$ where $x_i\in\mathbb F_q$ for $1\le i\le n,1\le j\le n$ be a Vandermonde matrix over finite field $\mathbb F_q$.
I wish to know the currently known fastest algorithms for computation of
1) $Vx$ where $x\in\mathbb F_q^{n\times1}$;
2) $V^Tx$ where $V^T$ is the transpose of $V$;
3) $V^{-1}x$;
4) $(V^T)^{-1}x$.
Can you also provide some references for the above algorithms?
Best Answer
All problems can be solved in $O(M(n)\log(n))$ base field operations, where $M(n)$ is the time it takes to multiply polynomials in degree $n$ (so using FFT, this is quasi-linear). This is in Chapter 3 of Pan's Structured Matrices and Polynomials.