2
$\begingroup$

This is a more practical question. In Pari/GP I have difficulties to use mateigen for some real matrices because of extreme long computation time and frequently "missing eigenspace" due to too low float precision. Say, the (real) matrix M is $48x48$ (a modified Vandermonde matrix), float precision of $1200$ decimal digits, then mateigen quits after some minutes, calling for more initial accuracy for the float computations.

However, using charpoly, polsturm (to check whether I've indeed 48 real eigenvalues) and then polroots I can get the eigenvalues with that parameters (they come out to be real, which is what I've expected). Now I thought I can proceed with some application of the much simpler method of matrix-solve or the like, for instance solve $ (M-\lambda I)*X = \text{} $ (or something very near) to compute the eigenvectors too. I don't have it just at hand but I vaguely recall that something in this line was possible. How can I proceed here? (Quick&dirty were sufficient at the moment, I can take a deeper look at this tomorrow)

[edit] In the comment to Pedro's answer I mentioned a procedure which I just found in my own old scripts. Unfortunately it seems to be the same way numerically insufficient as the original mateigen-procedure of Pari/GP with that problem constellation. The method works as follows:

  1. Construct a list matrix L containing of the first rows of the consecutive powers of M $ \text{for }k=1,dim, L[k,]=M^k[1,] $
  2. Construct a vandermondematrix V containing the powers of the eigenvalues $\lambda_k$
    $ \text{for }r=1,dim, \text{for }c=1,dim V[r,c]=\lambda_c^r $
  3. Then the matrix of eigenvectors is $W = L^{-1}*V $

In the current configuration with accuracy of 1200 digits I can solve this correctly for instance for $dim \le 16$ or the like.
But for $dim=48$ the error is inacceptable and may require to increase the accuracy the same way as the Pari/GP-inherent routine - so this does not help for my case now. The biggest dimension solvable with the standard mateigen-procedure with accuracy=1200 was $dim=32$ so far, maybe the accuracy requirement increases quadratically with the dimension. For $dim=48$ accuracy=1600 was not yet enough. The condition of the matrix (ratio of biggest to smallest eigenvalue) is $ \approx {1.0 e16 \over 1.0 e-13 }$ for $dim=32$ and $ \approx {1.0 e26 \over 1.0 e-19 }$ for $dim=48$ (it increases with the size of the testmatrix M)

So if there were another possibly relatively simple method I would be happy to try it.

1 Answers 1

2

If you only need a few eigenvectors (e.g. first few smallest or first few largest), I presume inverse iteration might be of service. Just make sure that the LU decomposition routine you would use for implementing inverse iteration is the kind that replaces zero pivots with tiny (near machine epsilon) quantities.

On the other hand, as I recall there are now special methods for eigendecomposing Vandermonde matrices which exploit the inherent structure; you might want to look into them.

  • 0
    (accept) I'll *"accept"* this answer to close the case. My hope was to get a hint to a si$m$ple q&d-method, which howeve$r$ works/helps i$n$ my problem. After I could not overcome the numeric$a$l difficulties a$n$d had to put the problem at side for later review. I think such a q&d-method is not available and I've now time to scan the huge number of available literature and encyclopedia-entries myself (which are even accessible online). So that question needs no more attention here.2011-05-04