# Speeding up LU Factorization

1. Nov 30, 2009

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!