# The inverse of a sparse triangular matrix

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?

• 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}$$.
• I added 0.15 to the diagonal of $A$ before computing $L$, which solved negative values on a diagonal. Turns out Incomplete Cholesky preconditioner allows performing 2x less iterations, but an iteration takes 2x longer (because of solving $M^{-1}x$), so it was not worth implementing (Jacobi preconditioner is better). – Ivan Kuckir Feb 24 '20 at 23:49