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

[wdlang]

is it possible on a station?

how long?

 

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

 

[wdlang]

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.

there are surely reasons to diagonalize such a matrix

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

 

[Office_Shredder]

there are surely reasons to diagonalize such a matrix

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

 

[bpet]

there are surely reasons to diagonalize such a matrix

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

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

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

 

[wdlang]

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

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

but i also need the eigenvectors

 

[bpet]

but i also need the eigenvectors

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

 

[Office_Shredder]

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

 

[HallsofIvy]

there are surely reasons to diagonalize such a matrix

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

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

 

[Anthony]

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

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.

 

[diggy]

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

 

[element4]

is it possible on a station?

how long?

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

 

[wdlang]

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

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

 

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