3
$\begingroup$

Is there an efficient way to diagonalize a block tridiagonal $N\times N$ matrix of the following form:

\begin{matrix} A_0 & B & 0 & 0 & \ldots \\ B & A_1 & B & 0 & \ldots \\ 0 & B & A_2 & B & \ldots \\ \vdots & \vdots & \vdots & \vdots & \ddots&B \\ &&&&B&A_{K-1} \end{matrix}

where $A_i$ and $B$ are $L \times L$ matrices with $N = K\cdot L$ ? I need an algorithm that scales way better than the standard $\mathcal{O}(N^3)$ scaling, since I am usually interested in $N\approx 10.000$ and $K \approx L \approx 100$ and need to diagonalize a lot of them. I need both the eigenvalues AND the eigenvectors, if possible to full precision.

Further information, if useful: The matrix I am considering is hermitian, the matrices $B$ are just the unit matrix and the matrices $A_i$ are pentagonal. Furthermore I would in principle be interested in the same matrix with an additional $B$ matrix in the upper right and lower left corner, but I'd be grateful for any help. I've also read this paper:

https://arxiv.org/abs/1306.0217

but while it in principle provides an algorithm for my problem, I was not able to implement it efficiently in python and the authors did not publish their code. I would appreciate any answer to my problem very much! Thx!!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Are you sure that you need explicit eigenvalues? Often it is sufficient (or even advantageous) to work with the characteristic polynomial (cp) instead, especially if you want to calculate, e.g., the sum or product of a function of the eigenvalues, see arxiv.org/abs/2103.10776 for an example. The cp of your matrix can be calculated using the block transfer matrix method of Molinari, see arxiv.org/abs/0712.0681. $\endgroup$
    – Fred Hucht
    Commented Aug 1, 2022 at 20:01
  • $\begingroup$ Yes, I fear that my problem does indeed require to compute the eigenvectors and eigenvalues. $\endgroup$
    – Ritteraxt
    Commented Aug 2, 2022 at 9:08
  • $\begingroup$ Ok, then it might be helpful to get more information about the $A_i$. $\endgroup$
    – Fred Hucht
    Commented Aug 2, 2022 at 11:02
  • $\begingroup$ Thanks for your interest! I described the exact form of the matrix including a minimal reproducible example in here: stackoverflow.com/questions/73195156/… $\endgroup$
    – Ritteraxt
    Commented Aug 2, 2022 at 11:54
  • $\begingroup$ @Ritteraxt In your suggested paper, we need to find $\lambda$ which satisfies ${\rm det}P_{K}(\lambda)=0$, right? But how did you do that? Did you find the closed form of $\lambda$? I am reading Section 3-1. $\endgroup$
    – Sakurai.JJ
    Commented Jul 17 at 6:56

0

Reset to default

You must log in to answer this question.