7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 8, 2011 at 11:09

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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