8
$\begingroup$

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

band matrix

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – G. Bach Dec 2 '15 at 21:10
  • $\begingroup$ @G.Bach Thanks, I'll have a look at the paper. Could you tell me the computational complexity of the method? $\endgroup$ – rnels12 Dec 2 '15 at 21:18
  • $\begingroup$ Sorry, don't know, googled for a minute or two but from the abstract it seemed like a promising start. $\endgroup$ – G. Bach Dec 2 '15 at 21:21
  • 2
    $\begingroup$ 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? $\endgroup$ – Pseudonym Dec 2 '15 at 22:14
  • 2
    $\begingroup$ 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! $\endgroup$ – Pseudonym Dec 3 '15 at 0:43
3
$\begingroup$

Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did).

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).

$\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.