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?
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.
I am only able to answer the first part. It will depend on the size of the field. Horner's Scheme gives us $O(n^2)$ for calculating $Vy$ knowing just the $x_i$ and $y$ and without allocating space for the matrix explicitly. The Fourier method will give you the polynomial with coefficients given by $y$ at all $q-1$ points of the field in time $O(q\log q)$, although the order will be a bit strange. For large fields the Horner scheme wins out.
You are trying to compute the values of the polynomial with coefficient list $x.$ The magic words are "discrete fourier transform"
