# Any body ever fully diagonalize a 200,000 hermitian matrix?

1. Sep 13, 2010

### wdlang

is it possible on a station?

how long?

2. Sep 14, 2010

### HallsofIvy

I doubt that there would be any reason to diagonalize such a matrix. About 10 to 20 years ago, the United States Coast and Geodetic Survey went through a large linear algebra calculation "justifying" the boundaries of "townships" and "sections" on its map (areas surveyed by different teams at different times typically didn't match up exactly). That required several hundred thousand equations in as many unknowns but it was not ever stored as a single matrix (Since positions of points would only affect the positions of point nearby, it would, necessarily, be a "sparse" matrix (almost all entries 0) and there are ways of working with such matrices that do not require storing all of the zero entries). Also, since their object was to "solve" the equations (actually a "least squares" approximation) I believe they used iterative approximation methods rather than diagonalizing.

3. Sep 14, 2010

### wdlang

there are surely reasons to diagonalize such a matrix

even for sparse matrices, sometimes we need to fully diagonalize it.

4. Sep 14, 2010

### Office_Shredder

Staff Emeritus
Like what? First you need a matrix of that size, then you need a reason to diagonalize it. Most matrices don't need to be diagonalized.

I do know there's a text-document matrix of a ton of wikipedia articles. It contains about 200,000 documents and 200,000 words (including names of every person etc., not just english words). The objective is to use it for clustering, so presumably they wanted to do singular value decomposition or something

5. Sep 15, 2010

### bpet

Just for fun, the Gauss-Laguerre quadrature nodes of order 200k (~15 min on newish PC):
Code (Text):

n=2e5;
x=eig(spdiags([-(n-1):0; 2*(n:-1:1)-1; -n:-1]',-1:1,n,n));

6. Sep 15, 2010

### wdlang

but i also need the eigenvectors

7. Sep 15, 2010

### bpet

sorry, my computer doesn't have 320GB of ram.

8. Sep 15, 2010

### Office_Shredder

Staff Emeritus
I can diagonalize the identity matrix and get all the eigenvectors for you

9. Sep 16, 2010

### HallsofIvy

Can you give an example? Anything that can be done by diagonalizing a matrix can also be done by iterative methods and for very large matrices iterative methods will be much faster.

(And, of course, most matrices can't be diagonalized.)

10. Sep 16, 2010

### Anthony

That's not really true. It's straight forward to prove that as a subset of $$\mathbf{R}^{n^2}$$, the matrices in $$\mathrm{Mat}_n(\mathbf{R})$$ that are not diagonalisable form a set of Lebesgue measure zero. So in this sense, most matrices can be diagonalised.

11. Sep 17, 2010

### diggy

bah -- deleting comment -- I don't have a good answer.

Last edited: Sep 17, 2010
12. Sep 18, 2010

### element4

For a generic diagonalizable 200.000x200.000 matrix, a naive implementation is quit impossible ('how long' isn't an issues, since your RAM will give up very quickly).

Depending on what you need to do with the eigenvectors and eigenvalues, and the form of your Hermitian matrix, it is usually possible to optimize the calculation very much! This, of course, usually involves specialized and sophisticated algorithms (=much more work than just writing "diagonalize(H)").

13. Sep 18, 2010

### wdlang

i can do diagonalization of 10000*10000 matrix on my laptop (2.5 RAM)

possibly i will try to do it on a station with parallel algorithm using scalapck

14. Sep 18, 2010

### petergreat

Are you trying to diagonalize an ordinary matrix or a sparse matrix? Do you know any numerical routines which are optimized for diagonalizing huge sparse matrices? I tried NAG library and Mathematica, but neither seems to have this functionality.