I am working through an algorithm found in this paper, which is used to multiply an $n \times n$ Vandermonde matrix by a $1 \times n$ vector.
To my understanding, trying to do this kind of multiplication normally should require $n^2$ multiplies. So for this algorithm to be worth anything, I would assume it to take less than that here.
The result of the 'preprocessing' stage of Algorithm 2.1 outputs a representation of the $n \times n$ transposed Vandermonde matrix as
$V^T = J \cdot D_{\phi} \cdot F \cdot A_{\phi}^{-1} \cdot F^{*} \cdot D_{\phi}^{-1} \cdot V(t)^{-1} \cdot D_{fg}$
Which involves making some calcualtions in the preprocessing to get those terms.
My belief was that there would be some way this representation could multiply by a $1 \times n$ vector more quickly than an $n \times n$ matrix, but I don't quite understand how this can be the case. It seems that trying to do less multiplications than that would somehow miss certain combinations and thus lose information. Since this product set of matrices multiplies together to get a $n \times n$ matrix instead of something smaller, how is it that this representation would be any more useful than the normal representation?
I'm not sure that your question is actually suited to Math.SE, but nonetheless:
It is not true that there are $n^2$ independent terms in the matrix in the informational sense. All terms are determined from just $n$ of them (because it's a Vandermonde matrix), and so this information can be used to speed up calculation.