# Inverse of a symmetric block tridiagonal matrix

I am aware of existent discussion on the inverse of a block tridiagonal matrix on this website (for example, How to invert a block tridiagonal matrix?) and I have been googling articles about this topic, but I feel I may be interested in a slightly different setting and I cannot tell whether the references I looked so far discuss that, so I'm posting here.

Similar to the link above, I am interested in the last block along the diagonal, the block in $$A^{-1}$$ corresponding to $$D_n$$ in $$A$$. However, the size of the blocks may vary. I do not assume each $$D_i$$ must be of same size and I assume each $$D_i$$ is $$n_i \times n_i$$.

$$A = \begin{bmatrix} D_1 & A_2^{\top} & & \\ A_2 & D_2 & A_3^{\top} & & & \\ & \ddots & \ddots & \ddots \\ & & A_{n-1} & D_{n-1} & A_n^{\top} \\ & & & A_n & D_n \\ \end{bmatrix}$$

One reference I looked at is https://epubs.siam.org/doi/pdf/10.1137/0613045 and Theorem 3.4 in it gives a general formula when $$A$$ is proper (i.e. the matrices $$A_i$$ are nonsingular). However, I am unsure if my setting fits the paper, as it says "block is of order n" (pg.8), and I wonder if the "order" here means $$\Theta(n)$$. If it actually means equal-size diagonal block, then I wonder if anyone could point some other reference to me for different-size block setting. Thank you!

## 1 Answer

For convenience, let $$T_k = \begin{bmatrix} D_1 & A_2^{\top} & & \\ A_2 & D_2 & A_3^{\top} & & & \\ & \ddots & \ddots & \ddots \\ & & A_{k-1} & D_{k-1} & A_k^{\top} \\ & & & A_k & D_k \\ \end{bmatrix}$$ for $$k = 1,2,\ldots,m$$, where I've let $$m$$ be the total number of diagonal blocks in the original matrix. This is to avoid confusion since the diagonal blocks are of size $$n_1 \times n_1, \ldots, n_m \times n_m$$. Our goal is to compute $$T_m^{-1}$$ as efficiently as possible.

Trivially, $$T_1 = D_1$$, so $$T_1^{-1} = D_1^{-1}$$, which can be computed in $$O(n_1^3)$$ operations.

Now, suppose we've already computed $$T_{k-1}^{-1}$$ and we wish to compute $$T_k^{-1}$$. We can partition $$T_k = \begin{bmatrix}T_{k-1} & Z_k^T \\ Z_k & D_k \end{bmatrix}$$ where $$Z_k = \begin{bmatrix}0 & A_k\end{bmatrix}$$. To invert $$T_k$$, we can apply the block matrix inverse formula to get $$T_k^{-1} = \begin{bmatrix}T_{k-1}^{-1} + T_{k-1}^{-1}Z_k^TS_kZ_kT_{k-1}^{-1} & -T_{k-1}^{-1}Z_k^TS_k \\ -S_kZ_kT_{k-1}^{-1}& S_k \end{bmatrix} \quad \text{where} \quad S_k = (D_k-Z_kT_{k-1}^{-1}Z_k^T)^{-1}.$$

With $$T_{k-1}^{-1}$$ already computed, we require the following steps:

1. Multiply $$Z_k$$ by $$T_{k-1}^{-1}$$ by $$Z_k^T$$ to get $$Z_kT_{k-1}^{-1}Z_k^T$$ -- $$O(n_{k-1}^2n_k + n_{k-1}n_k^2)$$ operations
2. Subtract $$Z_kT_{k-1}^{-1}Z_k^T$$ from $$D_k$$ to get $$D_k - Z_kT_{k-1}^{-1}Z_k^T$$ -- $$O(n_k^2)$$ operations
3. Invert $$D_k - Z_kT_{k-1}^{-1}Z_k^T$$ to get $$S_k$$ -- $$O(n_k^3)$$
4. Multiply $$S_k$$ by $$Z_k$$ to get $$S_kZ_k$$ -- $$O(n_{k-1}n_k^2)$$ operations
5. Multiply $$Z_k^T$$ by $$S_k$$ to get $$Z_k^TS_k$$ -- $$O(n_{k-1}n_k^2)$$ operations
6. Multiply $$-S_kZ_k$$ by $$T_{k-1}^{-1}$$ to get $$-S_kZ_kT_{k-1}^{-1}$$ -- $$O(n_k^2(n_1+\cdots+n_{k-1}))$$ operations
7. Multiply $$T_{k-1}^{-1}$$ by $$-Z_k^TS_k$$ to get $$-T_{k-1}^{-1}Z_k^TS_k$$ -- $$O(n_k^2(n_1+\cdots+n_{k-1}))$$ operations
8. Multiply $$Z_k^T$$ by $$S_kZ_kT_{k-1}^{-1}$$ to get $$Z_k^TS_kZ_kT_{k-1}^{-1}$$ -- $$O(n_k^2(n_1+\cdots+n_{k-1}))$$ operations
9. Multiply $$T_{k-1}^{-1}$$ by $$Z_k^TS_kZ_kT_{k-1}^{-1}$$ to get $$T_{k-1}^{-1}Z_k^TS_kZ_kT_{k-1}^{-1}$$ -- $$O(n_k^2(n_1+\cdots+n_{k-1}))$$ operations
10. Add $$T_{k-1}^{-1}$$ and $$T_{k-1}^{-1}Z_k^TS_kZ_kT_{k-1}^{-1}$$ to get $$T_{k-1}^{-1}+T_{k-1}^{-1}Z_k^TS_kZ_kT_{k-1}^{-1}$$ -- $$O((n_1+\cdots+n_{k-1})^2)$$ operations

Note that many of the above steps take advantage of the fact that $$Z_k = \begin{bmatrix}0 & A_k\end{bmatrix}$$ and $$S_kZ_k = \begin{bmatrix}0 & S_kA_k\end{bmatrix}$$ are $$n_k \times (n_1+\cdots+n_{k-1})$$ matrices which have all zeros except for a block of size $$n_k \times n_{k-1}$$.

If all the blocks are the same size $$n_1 = \cdots = n_m = n$$, then the total cost of computing $$T_k^{-1}$$ from $$T_{k-1}^{-1}$$, $$A_k$$, and $$D_k$$ is $$O((k-1)n^3+(k-1)^2n^2)$$. Thus, the total cost of computing $$T_m^{-1}$$ recursively is $$O(m^2n^3+m^3n^2)$$ as opposed to $$O(m^3n^3)$$ by just direct inversion. If the blocks are not all the same size, it's a bit harder to analyze how much faster the above method is compared to direct inversion. However, I suspect the above method is still faster in many cases.

• Thanks a lot for the detailed answer! Two questions - first, is it actually $S_k = (D_k - Z_k T_{k-1}^{-1} Z_k^{\top})^{-1}$? Second, I imagine this formula for $S_k$ applies when $k > 2$? Because when $k = 2$ the matrix is not tridiagonal yet and the block matrix inverse formula could be applied directly. Thank you! – Yang Dec 10 '19 at 20:04
• Thanks for catching my typo on the formula for $S_k$. For $k = 2$, the formula still applies, but $T_{k-1} = T_1 = D_1$, $Z_k = Z_2 = A_2$, i.e. the block of zeros in $Z_k$ has dimensions $n_1 \times 0$. – JimmyK4542 Dec 11 '19 at 3:25