Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 13, 2010 #1
    is it possible on a station?

    how long?
     
  2. jcsd
  3. Sep 14, 2010 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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.
     
  4. Sep 14, 2010 #3
    there are surely reasons to diagonalize such a matrix

    even for sparse matrices, sometimes we need to fully diagonalize it.
     
  5. Sep 14, 2010 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  6. Sep 15, 2010 #5
    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));
     
     
  7. Sep 15, 2010 #6
    but i also need the eigenvectors
     
  8. Sep 15, 2010 #7
    sorry, my computer doesn't have 320GB of ram.
     
  9. Sep 15, 2010 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I can diagonalize the identity matrix and get all the eigenvectors for you
     
  10. Sep 16, 2010 #9

    HallsofIvy

    User Avatar
    Science Advisor

    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.)
     
  11. Sep 16, 2010 #10
    That's not really true. It's straight forward to prove that as a subset of [tex] \mathbf{R}^{n^2}[/tex], the matrices in [tex]\mathrm{Mat}_n(\mathbf{R})[/tex] that are not diagonalisable form a set of Lebesgue measure zero. So in this sense, most matrices can be diagonalised.
     
  12. Sep 17, 2010 #11
    bah -- deleting comment -- I don't have a good answer.
     
    Last edited: Sep 17, 2010
  13. Sep 18, 2010 #12
    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)").
     
  14. Sep 18, 2010 #13
    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
     
  15. Sep 18, 2010 #14
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook