# Inversion algorithm for band matrices

Is there a clever way to invert a matrix with non-zero values only on the first diagonals :

As an example, a matrix like this (3 diagonals have real $v_{ij}$ values, others are zero) : $$\begin{bmatrix} v_{1,1} & v_{1,2} & 0 & 0& \cdots &\cdots & 0 \\ v_{2,1} & v_{2,2} & v_{2,3} & 0 & & & \vdots \\ 0 & v_{3,2} & v_{3,3} & v_{3,4} & \ddots & & \vdots \\ 0& 0 & v_{4,3} & v_{4,4}& \ddots & 0 &0 \\ \vdots & & \ddots & \ddots & \ddots & v_{n-2, n-1}& 0 \\ \vdots & & & 0 & v_{n-1, n-2} & v_{n-1,n-1}& v_{n-1, n} \\ 0 & \cdots & \cdots & \cdots & 0 & v_{n, n-1} & v_{n,n} \end{bmatrix}$$

I am looking for an algorithm that will be faster than the $O(n^3)$ Gauss algorithm, taking into account the specificity of the matrix.

EDIT :

To be more precise I am looking for an algorithm that solves a linear system which matrix has more than 3 diagonals (the matrix above is just an example).

• Sep 21, 2016 at 15:51
• Yes, this is a standard topic in numerical linear algebra. It's discussed in Golub and Van Loan, for example. Sep 22, 2016 at 15:36
• @littleO : Thanks for your comment, I have worked out an algorithm with the help of your citation Oct 6, 2016 at 12:52
• Thanks also @JeanMarie for editing the title, it helped me for my searches on the web :) Oct 6, 2016 at 12:56

Thomas's algorithm can be used to solve systems of equations with matrices of this form in $O(n)$ time. You can use it repeatedly with right hand sides given by the columns of the identity matrix to get $A^{-1}$ is $O(n^{2})$ time.
However, you probably don't actually need or want $A^{-1}$. In most situations you need to compute $A^{-1}v$ for various vectors $v$. This can be accomplished more quickly by using Thomas's algorithm to solve $Ax=v$ as needed.