# Sparse Vandermonde matrix factorization.

How to factor a Vandermonde matrix?

A Vandermonde matrix is a matrix

$$V=\begin{bmatrix}1&x_1&{x_1}^2&\cdots&{x_1}^k\\1&x_2&{x_2}^2&\cdots&{x_2}^k\\&&\vdots\\1&x_n&{x_n}^2&\cdots&{x_n}^k\end{bmatrix}$$

My own attempts so far reduce to placing values in a diagonal matrix $$D$$ and then cyclic group generator matrix $$C$$

$$V_0=I, V_{n} = DV_{n-1}+C^n$$

So that $$V_4 = D(D(D+C)+C^2)+C^3$$

It seems we can go other way around if we want to:

$$V_0=I, V_{n} = D^n+V_{n-1}C$$

This does not give me a Vandermonde however, but row nr $$n$$ needs multiplied $$C^n$$ from right to get the correct matrix.

I suspect there must be some easier way to do this.

Any answers or reference requests are welcome.

• What sort of factorization are you looking for? If you want an LU factorization it is derived in this paper – Carl Christian Apr 15 at 11:06
• Any sparse factorization would be OK. Yes product of sparse banded is fine. But I don't have any access. – mathreadler Apr 15 at 11:30
• Ah don't worry I found a quick Kronecker product hack that worked. – mathreadler Apr 15 at 12:17
• You will find the author's copy of the paper on the author's personal website. This a common practice. The conditioning of the Vandermonde matrices is poor. Consider an alternative if your are doing practical work. Writing a dense matrix as a product or sparse matrices should be carefully considered. It is likely that you lose the potential for level-3 BLAS operations. – Carl Christian Apr 15 at 16:58
• Yep I found the paper after a while. That is where I saw the rational functions in the factor elements. I don't want to do matrix to matrix operations like BLAS3. I am interested in cases where matrices would be too clumsy to even store into memory, let alone be manipulated efficiently. – mathreadler Apr 15 at 17:06