High quality preconditioning of a general symmetric positive definite matrix based on its \(U^T U + U^T R + R^T U\)-decomposition (Q2713570)

The author introduces a new class of algorithms for a decomposition of symmetric positive definite matrices. These algorithms belong to the group of incomplete Cholesky decompositions by values -- the fill-in is dependent on a drop tolerance parameter \(\tau \). New factorizations are proposed and investigated from the point of view of their use for the preconditioned conjugate gradient method (PCG) for solving linear systems \(Ax=b\). NEWLINENEWLINENEWLINEThe well known robust incomplete Cholesky factorization (RIC1) constructs the decomposition \(A=U_1^TU_1+R_1+R_1^T\) where \(U_1\) is an upper triangular matrix and \(R_1\) is a strictly lower triangular matrix of ``errors''. The algorithm RIC2 derived in the paper generates the decomposition \(A=U_2^TU_2 + U_2^TR_2 + R_2^TU_2\) where \(U_2\) is an upper triangular matrix and \(R_2\) is a strictly lower triangular matrix. The algorithm RIC2 itself could be more expensive than RIC1 but the PCG method with the preconditioner \(U_2^{-T} A U_2^{-1}\) needs less amount of iterations than that one with the preconditioner \(U_1^{-T} A U_1^{-1}\) generated by RIC1. NEWLINENEWLINENEWLINEThis result is a consequence of a thorough analysis of RIC2 factorization. This analysis gives the estimate for fill-in of the factor \(U_2\) as a function of drop tolerance parameter \(\tau \) and it describes the spectral properties of preconditioner \(U_2^{-T} A U_2^{-1}\). This knowledge enables us to make an estimate for total number of iterations for PCG with the preconditioner generated by the algorithm RIC2. Based on these theoretical results the algorithm RIC2S -- that is an improvement of RIC2 -- is proposed. The theoretical justification that the PCG method with the preconditioner constructed by the algorithm RIC2S is more efficient than that one with RIC2 -- especially for ill-conditioned matrices -- is done. NEWLINENEWLINENEWLINEThe behaviour of PCG with preconditioners generated by RIC1, RIC2, RIC2S and Cholesky decomposition is investigated on many numerical examples. The results show that RIC2S is the best choice when the PCG method is used for solving ill-conditoned systems.