Fast Vandermonde matrix multiplication over finite field - MathOverflow

Fast Vandermonde matrix multiplication over finite field

2011-08-08T09:36:12Z

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?

Answer by Igor Rivin for Fast Vandermonde matrix multiplication over finite field

2011-08-08T12:58:45Z

You are trying to compute the values of the polynomial with coefficient list $x.$ The magic words are "discrete fourier transform"

Answer by Watson Ladd for Fast Vandermonde matrix multiplication over finite field

2011-08-09T02:45:27Z

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.

Answer by Eric for Fast Vandermonde matrix multiplication over finite field

2011-08-10T06:01:59Z

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.