# Diagonalizing a block tridiagonal Toepliz Hermitean matrix

I have to diagonalize, within a Fortran-written code, a block tridiagonal Toeplitz Hermitian matrix, e.g.

$$\left[ \begin{array}{ccccc} \ddots & \hat{A} & & & \\ \hat{A}^\dagger & \hat{B} & \hat{A} & & \\ & \hat{A}^\dagger & \hat{B} & \hat{A} & \\ & & \hat{A}^\dagger & \hat{B} & \hat{A} \\ & & & \hat{A}^\dagger & \ddots \end{array} \right]$$

where $B$ is a Hermitian matrix. For the moment, I am just using standard Lapack routine ZHEEV for Hermitian matrices.

Do you have any suggestion on how to take advantage of one or more of the properties of this matrix to get a faster computation?

There are morally equivalent routines that seek the same results via different algorithms: ZHEEVD (divide and conquer) and ZHEEVR (multiply relatively robust representations). Perhaps one of them can outperform ZHEEV? (it uses QR iteration).

You might also want to try ZHBEV (hermitian eigensolver that exploits bandedness). I would think that bandedness would mainly speedup the frontend, band-to-tridiagonal reduction, so it might not be all that faster in the end.

I think another experiment worth running, is to apply ZHBTRD (reduce band hermitian matrix to real tridiagonal form) to your matrix. If the tridiagonal form is also Toeplitz**, you can compute its eigenvalues analytically (see the wikipedia page on tridiagonal matrices).

If you don't need the whole spectrum, you might be better off using Krylov techniques (reduction to tridiagonal form may still be useful in this setting as a frontend to speedup the matvec action).

** Unfortunately I don't have sufficient experience with Toeplitz systems to say for certain, whether or not Toeplitz-ness is preserved by tridiagonalization.