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?



Fast Vandermonde matrix multiplication over finite field
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*. 


