8
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – dranxo
    Commented May 6, 2011 at 4:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented May 6, 2011 at 7:03
  • $\begingroup$ 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. $\endgroup$
    – dranxo
    Commented May 6, 2011 at 21:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .