- #1

- 299

- 1

## Main Question or Discussion Point

Does anyone here know of any fast algorithms to diagonize large, symmetric matrices, that are mostly zeros? (by large I mean 300x300 up to several million by several million)

- Thread starter NeoDevin
- Start date

- #1

- 299

- 1

Does anyone here know of any fast algorithms to diagonize large, symmetric matrices, that are mostly zeros? (by large I mean 300x300 up to several million by several million)

- #2

- 5,647

- 908

For more general matrix types, you might look at LAPACK/BLAS or the Intel MKL.

Where do these matrices arise?

There might be some additional symmetry that can be exploited.

- #3

- 299

- 1

- #4

- 5,647

- 908

Possibly useful or interesting

http://www.cise.ufl.edu/research/sparse/matrices/

http://www.cise.ufl.edu/research/sparse/matrices/

- #5

AlephZero

Science Advisor

Homework Helper

- 6,994

- 291

It could be that literally "diagonalizing the matrix" isn't the best way to go, if the original matrix is very sparse. An iterative solution method may be faster than a direct method.

300x300 is a trivial sized problem whatever method you use. Several million variables may be feasible or may not, depending on the problem and the amount of computing power you have available.

- #6

- 299

- 1

- #7

- 1,356

- 2

Try the QR/QL methods to see if they fit your needs, there are faster ones to handle symmetric versions but my mind's drawing a blank. if you need int he millions you might want to look for a parallelziing version of what ever algorithm you use.

www.nr.com

- #8

- 299

- 1

I'm looking at them now. I'm trying to get them to work for me with C++, but not having any luck. I'm using Dev C++ on windows xp. If you have any advice on how to get it working, that would be very helpful.For more general matrix types, you might look at LAPACK/BLAS or the Intel MKL.

- #9

- 5,647

- 908

Ideally, the libraries should be made visible to the compiler.I'm looking at them now. I'm trying to get them to work for me with C++, but not having any luck. I'm using Dev C++ on windows xp. If you have any advice on how to get it working, that would be very helpful.

I could never get things to work so smoothly (when I tried them a while back).

I have been working in C with gcc in cygwin.

What worked for me was to locate the .c sources for LAPACK and include the relevant ones [based on my application] on the gcc command line along with my main program... adding by trial-and-error what is needed to successfully compile and link into an executable.

Using a hack [I once found via google], I was also able to use an older version of the Intel MKL with cygwin's gcc.

I'm not sure if any of these schemes work with Dev C++.

You might try: http://www.google.com/search?q=devcpp+lapack

- #10

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

http://en.wikipedia.org/wiki/Eigenvalue_algorithm

I'm sure there exists an algorithm designed specifically for finding the smallest eigenvalue of a sparse symmetric matrix, but I didn't see one with a quick web search.

- #11

AlephZero

Science Advisor

Homework Helper

- 6,994

- 291

Diagonalizing will give you all the eigenvalues. That is not a practical option for problems matrices bigger than about 500x500. For anything bigger than that, it will run very slowly (run time proportional to matrix size cubed) and/or the numerical conditioning will be too poor to get any answers at all.

That rules out QR/QL type methods (except on a 300x300 size problem) because they always calculate all the eigenvalues.

The best general-purpose algorithm for calculating a few eigenpairs of a large matrix is the Lanczos method. That needs a matrix factorization and equation solving algorithm for your sparse matrices.

A simpler alternative, if you just want the lowest eigenpair and the low eigenvalues are well separated, is the Inverse Power Iteration method.

Unless you want to learn a lot about linear algebra computations and have a couple of years to spare, don't try to code your own versions of a sparse solver or the Lanczos method from scratch.

http://www.netlib.org/linalg/spooles/spooles.2.2.html is a reputable place to start.

To give you an idea of what is feasible, I once calculated the lowest 3000 eigenpairs of a 300,000 x 300,000 sparse system successfully - though it took about 3 months to get the problem formulated properly, and the run time on a 4-processor Silicon Graphics box was about 3 days.

At the other end of the size range, run time for a 300x300 size problem would be of the order of < 1 sec.

- #12

- 299

- 1

I'm going to look at the algorithms suggested now.

- #13

- 1,356

- 2

have you tried C-lapack/Atlas (atlas i the platform independent version of blas, mkl the intel version). It might take you 3 hours to compile atlas i think to suit your HD needs.

- #14

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

If they don't, finding an associated eigenvector is an easy problem: it's just a nullvector of (A - vI).

I'm going to look at the algorithms suggested now.

Last edited:

- #15

AlephZero

Science Advisor

Homework Helper

- 6,994

- 291

Well, that's easy mathematics, but it's expensive computation if you have to factorise A-vI from scratch and A has several million rows and columnsIf they don't, finding an associated eigenvector is an easy problem: it's just a nullvector of (A - vI).

But the good news is, every eigenvalue method that I know of has an efficient way of calculating the corresponding vectors, so it's not a problem.

In fact some methods calculcate the vectors first, then find the values as a final step (e.g. using a Rayleigh quotient [tex]v = \frac{x^TAx}{x^Tx}[/tex])

- #16

- 299

- 1

All the instructions I can find are for Unix/Linux users...

Thanks in advance.

Devin

- #17

- 36

- 0

http://sourceforge.net/projects/lpp/ ?

- #18

- 299

- 1

PS. the algorithm is dnlaso.f from http://www.netlib.org/laso/

It works when I compile it on one, but not on the other...

- Last Post

- Replies
- 22

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 18K

- Last Post

- Replies
- 2

- Views
- 6K

- Last Post

- Replies
- 25

- Views
- 10K

- Last Post

- Replies
- 11

- Views
- 750

- Last Post

- Replies
- 3

- Views
- 2K