Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a large ($10^6$ by $10^6$) sparse ($0.4$% nonzero) hermitian matrix $H$ arising from the discretization of an elliptic PDE. I would like to approximate $H$ with a smaller matrix $H'$ in such a way that $H'$ and $H$ have nearly identical eigenvectors and eigenvalues for the lowest 5 or 6 eigenvalues.

This could be done if I knew the lowest eigenvectors of $H$ as I could simply restrict $H$ to the space spanned by these values. However I would like to be able to find an approximation before solving eigenvalue problem (in fact my eventual goal is to make solving the eigenvalue problem more efficient).

I know of the recent work on approximating SDD systems with graph sparsification as well as multilevel operator compression. What else is out there?

The application is a full-CI treatment of a multiparticle quantum system.

share|improve this question
add comment

1 Answer 1

Isn't this what the Lanczos algorithm was designed for? http://en.wikipedia.org/wiki/Lanczos_algorithm

share|improve this answer
    
Sorta, but that's not what I want here. I am trying to compress the operator without first computing an invariant subspace. It would be great if one could identify which entries of the matrix contribute most to the eigenvectors without explicitly forming the matrix (it's about 90GB in RAM). If you think this sounds crazy that makes two of us. Ideally my advisor would be the third but no luck there. –  dranxo May 6 '11 at 4:39
1  
You do not need to form the matrix to run Lanczos, you just need a "black-box" function that computes $Av$ given a vector $v$. If you cannot even do this efficiently, please specify how you can interact with the matrix, or which special structure it has. –  Federico Poloni May 6 '11 at 7:03
    
Yes, you only need to form $Av$ to do Lanczos. My matrix is exactly this $\mathbb{H}$: en.wikipedia.org/wiki/Configuration_interaction . I would like it to be smaller while still preserving the lowest energy states. A similar problem arises in finite element simulations. Consider coarsening the discretization in certain regions in order to work with a smaller stiffness matrix. Normally this is done using geometric intuition but in my problem the space is high dimensional so I would like to somehow automate the coarsening. –  dranxo May 6 '11 at 21:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.