Theoretical Background

OBJECTIVE

Numerical solution of large sparse linear systems

Ax=b.



SOLUTION APPROACH

Preconditioned iterative solver (Krylov subspace method, e.g. GMRES)



PRECONDITIONER

Incomplete LU decomposition methods



RULE OF THUMB

Iterative solvers perform quite well if , where (strict for certain iterative solvers like GMRES)



PARTIAL INCOMPLETE LU DECOMPOSITION

k steps of an incomplete LU decomposition

where , are unit diagonal, reduced matrix (``approximate Schur complement''). The leading part of is diagonal.



LEVEL-BASED ILUS

has a specific nonzero pattern.



THRESHOLD-ORIENTED ILUS

, drop tolerance.



GROWTH OF THE INVERSE TRIANGULAR FACTORS

and may become very large pivoting recommended.

What kind of pivoting is appropriate?



INVERSE ERROR

For preconditioning we have to apply
-->

Denote by

the entries being dropped from and .

Lemma[B.,Saad '04]. Error bounds for the inverse error .

  1. Standard case, e.g. [Meijerink & Van der Vorst '77, Munksgaard '80, Saad '94]
  2. There exists an ILU (``Tismenetsky approach'') such that

  1. Standard case
  2. Tismenetsky case



CONSEQUENCES



PRECONDITIONED ITERATIVE SOLVERS

Solve instead of , where



DRAWBACK

Preconditioned system requires or to be small.



THRESHOLD-ORIENTED ILUS

, drop tolerance



INVERSE-BASED APPROACH

Prescribe a bound and apply diagonal pivoting such that and .



FACTOR OR SKIP STRATEGY

Rows/columns that exceed the prescribed bound are pushed to the end



m.bollhoefer@tu-bs.de

Last modified: October 11, 2011