1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ See (math.hkbu.edu.hk/ICM/LecturesAndSeminars/08OctMaterials/1/…) $\endgroup$
    – Jean Marie
    Sep 21, 2016 at 15:51
  • 1
    $\begingroup$ Yes, this is a standard topic in numerical linear algebra. It's discussed in Golub and Van Loan, for example. $\endgroup$
    – littleO
    Sep 22, 2016 at 15:36
  • $\begingroup$ @littleO : Thanks for your comment, I have worked out an algorithm with the help of your citation $\endgroup$
    – Sylvain B.
    Oct 6, 2016 at 12:52
  • $\begingroup$ Thanks also @JeanMarie for editing the title, it helped me for my searches on the web :) $\endgroup$
    – Sylvain B.
    Oct 6, 2016 at 12:56

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Tanks for you answer. Yes, I do not need the invert of the matrix, so I have use LU decomposition to solve the problem. $\endgroup$
    – Sylvain B.
    Oct 6, 2016 at 12:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .