# Inverting a band matrix

I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following:

Here, the area under the blue stripes is the non-zero elements; everything else is zero

Is there an algorithm to invert this kind of matrix that is simple yet more efficient than Gaussian elimination and LU decomposition?

• Those matrices are called band matrices (and as far as I'm aware, they were the original motivation for finding the bandwidth of a graph), and possibly this paper might be a useful starting point. – G. Bach Dec 2 '15 at 21:10
• @G.Bach Thanks, I'll have a look at the paper. Could you tell me the computational complexity of the method? – rnels12 Dec 2 '15 at 21:18
• Sorry, don't know, googled for a minute or two but from the abstract it seemed like a promising start. – G. Bach Dec 2 '15 at 21:21
• Do you want to invert it, or do you want to solve the linear system? The answer is probably the latter, because the inverse of a band matrix is usually dense. Additional question: Is there any more structure to exploit? – Pseudonym Dec 2 '15 at 22:14
• OK. The reason why I ask is that in most cases, people who think they want to invert a matrix probably don't. Either way, it's a good question! – Pseudonym Dec 3 '15 at 0:43

Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-band-limited) matrix in general, so just filling out the entries of the inverse matrix would take $\Omega\left(n^2\right)$. So I'll assume you just want to solve a linear system $A x = b$.
Using the algorithm in this paper, a general band-limited matrix $A$ of size $n \times n$ with bandwidth $k$ can be decomposed into triangular $k$-bandwidth matrices $L$ and $U$ in $O \left( k^2 n \right)$ time. From there, $L U x = b$ can be solved quickly in $O(k n)$ time. So overall, the runtime will be $O\left(k^2 n\right)$. As a followup, if $k$ is constant, that means that the system can be solved in linear time (highly useful).