1
$\begingroup$

There is a triagonal block matrix $M$ of form:

$$ M = \begin{bmatrix} A & B^T & 0 & 0 & \cdots & 0 & 0 \\ B & A & B^T & 0 & \cdots & 0 & 0 \\ 0 & B & A & B^T & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & B & A \end{bmatrix} $$ where $A, B$ are real-valued square matrices of the same size.

Also, $A$ is positive definite and symmetric. Later makes $M$ symmetric as well.

My interest is in closed-form solution for elements of $M^{-1}$.

From "Explicit inverses of some tridiagonal matrices" C.M. da Fonseca, J. Petronilho, I am aware of the closed-form solution for tridiagonal toeplitz matrix of form:

$$ T = \begin{bmatrix} a & b & 0 & 0 & \cdots & 0 & 0 \\ c & a & b & 0 & \cdots & 0 & 0 \\ 0 & c & a & b & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & c & a \end{bmatrix} $$ where $a, b, c$ - scalars.

$$ (T^{-1})_{ij} = \begin{cases} (-1)^{i+j}\frac{b^{j-i}}{\left(\sqrt{bc}\right)^{j-i+1}}\frac{U_{i-1}(d)U_{n-j}(d)}{U_{n}(d)} \quad \text{if} \quad i \le j \\ (-1)^{i+j}\frac{c^{i-j}}{\left(\sqrt{bc}\right)^{i-j+1}}\frac{U_{j-1}(d)U_{n-i}(d)}{U_{n}(d)} \quad \text{if} \quad i \gt j \end{cases} $$ where $d = \frac{a}{2\sqrt{bc}}$, $U_{k}(x)$ - Chebyshev polynomials of the second kind.

Don't see a way to extend it to block matrices though. Does anybody know how it can be done? or any alternative way?

$\endgroup$
0
$\begingroup$

After some extended search, found an article "Numerically Stable Algorithms for Inversion of Block Tridiagonal and Banded Matrices" that gives direct algorithm for even more general problem.

$$ M = \begin{bmatrix} A_1 & -B_1 & 0 & 0 & \cdots & 0\\ -B_1^T & A_2 & -B_2 & 0 & \cdots & 0\\ 0 & -B_2^T & A_3 & -B_3 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & A_N \end{bmatrix} $$ where all $A_i$ are symmetric, all $B_i$ are non-singular.

Then, symmetry of $M$, as a whole, is exploited to get decomposition $(M^{-1})_{ij}=U_iV_j^T,\quad j \ge i$.

Note, when inverse of a symmetric matrix exists (and we assume it does) it should be symmetric as well.

$U$ and $V$ are given recursively:

$$ U_1 = I, \quad U_2=B_1^{-1}A_1\\ U_{i+1}=B_i^{-1}(A_iU_i-B^T_{i-1}U_{i-1}),\quad i=2,...,N-1\\ V_N^T=(A_NU_N-B_{N-1}^TU_{N-1}^T)^{-1}, \quad V_{N-1}^T=V_N^TA_NB_{N-1}^{-1}\\ V_i^T=(V_{i+1}^TA_{i+1}-V_{i+2}^TB_{i+1}^T)B_i^{-1}, \quad i=N-2,...,1 $$

Under constraints, that all $A_i$ are equal, all $B_i$ are equal, and $B=B^T$ (which I missed when posting original question!) equations become even simpler:

$$ U_1 = I, \quad U_2 = B^{-1}A \\ U_{i+1} = B^{-1}AU_i - U_{i-1},\quad i=2,...,N-1\\ V_N^T=(AU_N-BU_{N-1}^T)^{-1}, \quad V_{N-1}^T=V_N^TAB^{-1}\\ V_i^T=V_{i+1}^TAB^{-1}-V_{i+2}^T, \quad i=N-2,...,1 $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.