Keywords: approximate inverse, preconditioning, incomplete decomposition, Gram-Schmidt orthogonalization.

This paper deals with the approximate inverse preconditioning for the conjugate gradient method. In particular, it focuses on the preconditioners of the AINV type based on the generalized Gram-Schmidt process. A system of linear equations with a symmetric and positive definite matrix from a real-world problem is considered. In order to solve it by conjugate gradients, it has to be preconditioned. A symmetrically preconditioned system can be obtained by multiplying it from both sides by inverse factors of the system matrix. In order to obtain a practical procedure, the factor should be computed incompletely.

The approximate inverse preconditioners based on the generalized Gram-Schmidt algorithm can be monitored by the loss of orthogonality between the column vectors involved in the related decomposition. The goal is to obtain the preconditioner which is well-theoretically founded, safe in applications, efficient in both its construction and application within conjugate gradients.

The basic computational procedure orthogonalizes the initial basis in the A-norm. When the initial vectors basis is formed from unit vectors, the exact version of the generalized Gram-Schmidt process provides matrices Z and U, so that U is the Cholesky factor of A and Z is its inverse. Our theoretical derivation is strongly based on the bounds derived for the finite precision arithmetic in [1]. Nevertheless, there is a problem to determine dropping strategy. A basic dropping strategy was considered in [2]. This strategy considered magnitudes of matrix entries absolutely or with respect to some intermediate quantities.

Construction of an incomplete decomposition supported by theoretical background is the subject of this paper. The analysis in [1] motivates the development of new rules to drop entries in an incomplete generalized Gram-Schmidt algorithm such that the computed factors have similar properties as obtained from the standard finite precision algorithm. Moreover, we focus on pivotal strategies that can significantly improve numerical properties of the preconditioner. The theoretical results and considerations are accompanied by carefully chosen experiments which demonstrate the usefulness of the chosen approach. We hope that the resulting algorithms may extend scope of applicability of the considered type of approximate inverse preconditioners in both sequential and parallel computations.

1

M.Rozlozník, M.Tuma, A.Smoktunowicz, J.Kopal, "Rounding error analysis of orthogonalization with a non-standard inner product", BIT Numer Math, 52:1035-1058, 2012.

2

M.Benzi, C.D.Meyer, M.Tuma, "A sparse approximate inverse preconditioner for the conjugate gradient method", SIAM J. Sci. Comput., 17:1135-1149,1996.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £40 +P&P)