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?

Polynomials and Matrix Computations, Section 2.6 and 4.6. – Federico Poloni Aug 8 '11 at 11:09