The inverse of a sparse triangular matrix

Question

I am solving a sparse system of linear equations $Ax=b$, where $A$ is symmetric positive definite.

My matrix is 3210 x 3210, with about 10 non-zero values per row. For a specific $A$, I will need to find the solution $x$ for hundreds of different right sides $b$.

Iterative Gauss-Seidel method takes over 60 seconds. Iterative Conjugate Gradient Method takes 320 ms. Using CGM with a "Jacobi preconditioner" (a diagonal of $A$) takes 190 ms.

I would like to use Incomplete Cholesky factor as a preconditioner. It is clear how to compute a preconditioner $M = L \cdot L^T$. However, CGM method requires the inverse $M^{-1}={L^T}^{-1}\cdot L^{-1}$. Is there an efficient method to compute an inverse of a sparse triangular $L$? Will the result be as sparse as L?

Answer 1

• You do not need to evaluate the inverse of $M$. However you need to compute $x \mapsto M^{-1} x$. Solving a linear system with $L L^T$ uses the forward substitution and does not require $L^{-1}$.
• With such a large number of right hand sides, you could also consider using a block CG method.
• The inverse of a triangular matrix will remain triangular. However the inverse of a sparse matrix is not guaranteed to be sparse.