MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I do not have a ready answer, but I think you can interpolate it with a some work from Bini and Pan, Polynomials and Matrix Computations, Section 2.6 and 4.6. – Federico Poloni Aug 8 '11 at 11:09
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.