Fast Vandermonde matrix multiplication over finite field - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T22:00:46Z http://mathoverflow.net/feeds/question/72341 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72341/fast-vandermonde-matrix-multiplication-over-finite-field Fast Vandermonde matrix multiplication over finite field tckwok 2011-08-08T09:36:12Z 2011-08-10T06:01:59Z <p>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$.</p> <p>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$.</p> <p>Can you also provide some references for the above algorithms?</p> http://mathoverflow.net/questions/72341/fast-vandermonde-matrix-multiplication-over-finite-field/72351#72351 Answer by Igor Rivin for Fast Vandermonde matrix multiplication over finite field Igor Rivin 2011-08-08T12:58:45Z 2011-08-08T12:58:45Z <p>You are trying to compute the values of the polynomial with coefficient list $x.$ The magic words are "discrete fourier transform"</p> http://mathoverflow.net/questions/72341/fast-vandermonde-matrix-multiplication-over-finite-field/72425#72425 Answer by Watson Ladd for Fast Vandermonde matrix multiplication over finite field Watson Ladd 2011-08-09T02:45:27Z 2011-08-09T02:45:27Z <p>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.</p> http://mathoverflow.net/questions/72341/fast-vandermonde-matrix-multiplication-over-finite-field/72556#72556 Answer by Eric for Fast Vandermonde matrix multiplication over finite field Eric 2011-08-10T06:01:59Z 2011-08-10T06:01:59Z <p>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 <em>Structured Matrices and Polynomials</em>. </p>