Approximate inverse preconditioning with adaptive dropping

Jiří Kopal
Pondělí 10. března 2014, 14:20 hodin
Didaktický kabinet KMD (4. patro budovy H areálu TUL, Voroněžská 1329/13, Liberec 1, č. dv. 5027)
[Pozvánka v PDF]

Anotace

The contribution deals with an approximate inverse preconditioning for the conjugate gradient method. The main goal is to compute the decomposition that would be sparse and reliable at the same time. In particulare, the generalized Gram−Schmidt process with an adaptive dropping strategy is considered.

Assume the system of linear algebraic equations in the form Ax = b, where A is symmetric and positive definite. Symmetrically preconditioned system can be written in the form

Z^TAZy = Z^Tb,     x = Zy,

where Z is the factor of the approximation ZZ^T to A^-1, that plays the role of the preconditioner.

The generalized Gram−Schmidt process in exact arithmetic provides Z and U, so that

U^TU = (Z⁽⁰⁾)^TAZ⁽⁰⁾,     Z^TAZ = I,     and     ZU = Z⁽⁰⁾.

The columns of the matrix Z⁽⁰⁾ are initial vectors that are A-orthogonalized against previously computed vectors. Matrix U contains the orthogonalization coeffiients. It is clear that U is the Cholesky factor of

A = U^TU     for     Z⁽⁰⁾ = I.

In practice, the effects of finite precision arithmetic should be considered.

The theoretical results will be accompanied by carefully chosen experiments that demonstrate usefulness of the approach. We hope that the developed algorithm may extend scope of applicability of the considered type of approximate inverse preconditioners.