How can I efficiently calculate the inverse of this symmetric near-tridiagonal matrix?

Question

I'm interested in calculating the inverse of the following matrix in order to solve a system of linear equations.

$$T=\begin{pmatrix} b & a & 0 & 0 & \cdots & a\\ a & b & a & 0 & \cdots & 0\\ 0 & a & b & a & \cdots & 0\\ 0 & 0 & a & b & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & a & b & a & 0\\ 0 & 0 & 0 & a & b & a\\ a & 0 & 0 & 0 & a & b \end{pmatrix}$$

This matrix is almost tridiagonal, except for entries in the top-right and bottom-left corners. I have seen how to calculate the inverse of tridiagonal matrix, but how would those corner-entries affect the inverse?

By the way, this matrix shows up in the Crank-Nicolson method applied to parabolic PDE's (diffusion equation particularly) with periodic boundary conditions.

Answer 1

I assume, that you want to solve $Ax = b$, and you are not iterested in the inverse $A^{-1}$ (which is dense).

You may perform the LQ factorization of $A$ (or QR of $A'$) using Givens rotations. In this case $n$ rotations are required. Then resulting $L$ matrix is lower triangular with two subdiagonals except the last row of $L$, which is dense and must be stored separately. The matrix $Q$ cannot be formed explicitly, since is dense. Required decomposition can be performed in $O(n^2)$ operations.

Answer 2

This can be solved efficiently by using the Thomas algorithm. The Wikipedia page does a pretty good job on explaining it. For your case of periodic boundary, you may need to spend a little bit more time to look for a better explanation.