Can Special Properties of a Hamiltonian Matrix Speed Up LU Factorization?

[Adam Lewis]

Hi,
This isn't exactly homework, but I guess it goes here because it's a specific problem?

I'm working on some Fortran 90 code to simulate a quantum wire. Part of the calculation involves finding the determinant of the Hamiltonian. I'm currently doing this by calculating the Hamiltonian's LU factorization using a general LAPACK subroutine. This works but is slow.

The Hamiltonian has some special properties whose exploitation could speed things up considerably, but I'm a little new to computational linear algebra and am not sure exactly where to look. I'm just wondering if anyone can point me in the right direction towards speeding up this computation. The matrix has these properties:

1. It is Hermitian (of course)
2. It is very sparse.
3. In particular, it is very nearly tridiagonal except for four off diagonal elements. Here is a quick sketch:

|+ + 0 0 + 0 + 0 0 0|
|+ + + 0 0 0 0 0 0 0|
|0 + + + 0 0 0 0 0 0|
|0 0 + + + 0 0 0 0 0|
|+ 0 0 + + + 0 0 0 0|
|0 0 0 0 + + + 0 0 0|
|+ 0 0 0 0 + + + 0 0|
|0 0 0 0 0 0 + + + 0|
|0 0 0 0 0 0 0 + + +|

The Hamiltonian will in general be much larger than this, but I think this illustrates the point. The fact that it is not quite tridiagonal is frustrating, as computing the LU factorization of a matrix which is exactly tridiagonal is of course quite easy. Does anyone have any idea (or knowledge of places to look for ideas) of how to either quickly tridiagonalize the Hamiltonian or how to exploit its other qualities for a speed boost?

Thanks!

 

[KataKoniK]

Hi there,
As a computational physicist, I can definitely relate to your struggle with optimizing matrix calculations. It sounds like you're on the right track by looking into the special properties of your Hamiltonian matrix. Here are a few suggestions that may help speed up your computation:

1. Consider using a specialized sparse matrix solver instead of the general LAPACK subroutine. These solvers are designed specifically for sparse matrices and can often be much faster than general solvers. Some popular options include SuperLU, UMFPACK, and MUMPS.

2. If your Hamiltonian matrix is symmetric (which it appears to be), you can also take advantage of this property to speed up the calculation. Instead of computing the LU factorization, you can use a specialized symmetric matrix solver such as CHOLMOD or PARDISO.

3. Another approach you could try is to use a divide-and-conquer algorithm, which breaks the matrix into smaller submatrices and then combines the solutions to find the determinant. This can be more efficient for large matrices, but may not be as effective for smaller matrices.

I hope these suggestions give you some ideas for improving the speed of your computation. Good luck with your research!

 

[Mene]

I would suggest looking into specialized algorithms for computing the determinant of a Hermitian, sparse matrix. One option could be to use a sparse direct solver, such as the UMFPACK or SuperLU libraries, which are specifically designed for sparse matrix computations. These solvers use specialized techniques to exploit the sparsity of the matrix and can often be much faster than general-purpose LU factorization routines.

Another approach could be to use iterative methods, such as the Lanczos algorithm, which are designed to efficiently compute the determinant of a sparse, Hermitian matrix. These methods may be more suitable for large matrices, as they do not require the full matrix to be stored in memory.

Additionally, you could try to exploit the tridiagonal structure of the matrix by using specialized tridiagonalization algorithms, such as the Householder tridiagonalization method. This could potentially reduce the number of off-diagonal elements and make the LU factorization process faster.

In summary, there are several options to explore for speeding up the LU factorization of your Hamiltonian matrix. I would recommend researching and experimenting with different algorithms to find the most efficient approach for your specific problem.