13
$\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?

Improve this question
$\endgroup$
8
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 0:43

1 Answer 1

Reset to default
12
$\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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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