Thread Subject: Memory efficient method for solving eigensystems?

Is there a memory-efficient method for computing the lowest eigenvalues and eigenvectors of a sparse matrix. I've been using the built-in eigs() function, which uses the ARPACK library, but I would like to know if there is something that uses less memory to run.

"Carlos Baiz" <nothing@nodomain.com> wrote in message <gqrib9$act$1@fred.mathworks.com>...
> Is there a memory-efficient method for computing the lowest eigenvalues and eigenvectors of a sparse matrix. I've been using the built-in eigs() function, which uses the ARPACK library, but I would like to know if there is something that uses less memory to run.

Hi Carlos.

Can you give an example of how you are calling eigs? Do your matrices have any nice properties that you could tell eigs about, like symmetry? Any use cases would be helpful.

Thanks.
Pat.

"Pat Quillen" <pquillen@mathworks.com> wrote in message <gqu4dl$4u0$1@fred.mathworks.com>...
> "Carlos Baiz" <nothing@nodomain.com> wrote in message <gqrib9$act$1@fred.mathworks.com>...
> > Is there a memory-efficient method for computing the lowest eigenvalues and eigenvectors of a sparse matrix. I've been using the built-in eigs() function, which uses the ARPACK library, but I would like to know if there is something that uses less memory to run.
>
> Hi Carlos.
>
> Can you give an example of how you are calling eigs? Do your matrices have any nice properties that you could tell eigs about, like symmetry? Any use cases would be helpful.
>
> Thanks.
> Pat.

Hi Pat,
The matrix is Hermitian and positive-definite (only real and positive eigenvalues). So far with 8GB of RAM I can get the 30 lowest evals/evects of a ~16000x16000 matrix but would like to be able to work with larger matrices if possible.
Thanks,
-Carlos

"Carlos Baiz" <nothing@nodomain.com> wrote in message <gqrib9$act$1@fred.mathworks.com>...
> Is there a memory-efficient method for computing the lowest eigenvalues and eigenvectors of a sparse matrix. I've been using the built-in eigs() function, which uses the ARPACK library, but I would like to know if there is something that uses less memory to run.

Something like this (Krylov iteration)

n=5;
P=rand(n);
d=rand(1,n)
A=sparse(P*diag(d)*inv(P));

tol=1e-6;
xold=0;
x=zeros(length(A),1);
x(1)=1;
while norm(x-xold)>tol
    xold=x;
    x = A\x;
    l=1/norm(x);
    x=l*x;
end
l
x

% Bruno

Here is the package that also might be useful.
http://www.cas.mcmaster.ca/~qiao/software/takagi/matlab/readme.html

Also remember that Lanzos's method works just fine for large eigenvalues, but usually do poorly at the other end of the spectrum (because of the lost of orthogonalization). It might be wise to look for the inverse of largest eigenvalues of inv(A) rather than smallest eigen values of A.

Bruno

> Hi Pat,
> The matrix is Hermitian and positive-definite (only real and positive eigenvalues). So far with 8GB of RAM I can get the 30 lowest evals/evects of a ~16000x16000 matrix but would like to be able to work with larger matrices if possible.
> Thanks,
> -Carlos

Carlos:

Supposing that A is the matrix, are you calling eigs as:
eigs(A, nev, 'sa')

or are you calling eigs as:
eigs(A, nev, 'sm')?

The former does not require shift-and-invert and is likely to converge more slowly, but use much less memory. The later uses shift-and-invert Lanczos, and requires factorization of the matrix A, therefore probably requiring much more memory. For the sake of an example,
A = delsq(numgrid('L',400)); % 118803 x 118803 Hermitian pos def matrix.
eigs(A, 10, 'sm')
requires about 8 times more memory (very crudely measured) than
eigs(A, 10, 'sa')
Of course, the 'sm' call converges a *lot* faster.

For the 'sa' form, you'll want to be patient and you'll want to get familiar with the various options that eigs has to offer.

Good luck.
Pat.

"Pat Quillen" <pquillen@mathworks.com> wrote in message <gr14gm$634$1@fred.mathworks.com>...
> > Hi Pat,
> > The matrix is Hermitian and positive-definite (only real and positive eigenvalues). So far with 8GB of RAM I can get the 30 lowest evals/evects of a ~16000x16000 matrix but would like to be able to work with larger matrices if possible.
> > Thanks,
> > -Carlos
>
> Carlos:
>
> Supposing that A is the matrix, are you calling eigs as:
> eigs(A, nev, 'sa')
>
> or are you calling eigs as:
> eigs(A, nev, 'sm')?
>
> The former does not require shift-and-invert and is likely to converge more slowly, but use much less memory. The later uses shift-and-invert Lanczos, and requires factorization of the matrix A, therefore probably requiring much more memory. For the sake of an example,
> A = delsq(numgrid('L',400)); % 118803 x 118803 Hermitian pos def matrix.
> eigs(A, 10, 'sm')
> requires about 8 times more memory (very crudely measured) than
> eigs(A, 10, 'sa')
> Of course, the 'sm' call converges a *lot* faster.
>
> For the 'sa' form, you'll want to be patient and you'll want to get familiar with the various options that eigs has to offer.
>
> Good luck.
> Pat.

Thanks! That was very helpful. It turns out my matrix is imaginary and 'sa' works only with real matrices so instead I use 'sr' and get 15 times smaller memory footprint. Thanks a lot.