-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What sort of factorization are you looking for? If you want an LU factorization it is derived in this paper $\endgroup$ – Carl Christian Apr 15 at 11:06
  • $\begingroup$ Any sparse factorization would be OK. Yes product of sparse banded is fine. But I don't have any access. $\endgroup$ – mathreadler Apr 15 at 11:30
  • $\begingroup$ Ah don't worry I found a quick Kronecker product hack that worked. $\endgroup$ – mathreadler Apr 15 at 12:17
  • $\begingroup$ 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. $\endgroup$ – Carl Christian Apr 15 at 16:58
  • $\begingroup$ 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. $\endgroup$ – mathreadler Apr 15 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.