Vandermonde Matrix

A type of matrix which arises in the Least Squares Fitting of Polynomials and the reconstruction of a Distribution from the distribution's Moments. The solution of an $n\times n$ Vandermonde matrix equation requires ${\mathcal O}(n^2)$ operations. A Vandermonde matrix of order $n$ is of the form

$$\left[{\matrix{ 1 & x_1 & {x_1}^2 & \cdots & {x_1}^{n-1}\cr... ...dots\cr 1 & x_n & {x_n}^2 & \cdots & {x_n}^{n-1}\cr}}\right].$$

See also Toeplitz Matrix, Tridiagonal Matrix, Vandermonde Determinant

References

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Vandermonde Matrices and Toeplitz Matrices.'' §2.8 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 82-89, 1992.