0
$\begingroup$

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?

Improve this question
$\endgroup$
0
$\begingroup$
  • 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.
Improve this answer
$\endgroup$
  • $\begingroup$ I implemented the Incomplete Cholesky Factorization from Wikipedia, and sometimes, it requires me to compute a square root of a negative number. Is the algorithm wrong, or the Incomplete cholesky factor might not exist? Or it might be complex for a real-valued matrix? $\endgroup$ – Ivan Kuckir Feb 21 '20 at 16:05
  • $\begingroup$ 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). $\endgroup$ – Ivan Kuckir Feb 24 '20 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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