- #1

- 299

- 1

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter NeoDevin
- Start date

- #1

- 299

- 1

- #2

- 5,864

- 1,170

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,864

- 1,170

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

- 293

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

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

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.

- #9

- 5,864

- 1,170

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.

Ideally, the libraries should be made visible to the compiler.

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

- 293

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

- 293

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

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 columns

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...

Share: