Advanced Incomplete Factorization Methods for Solution of Diffusion - Convection Equations

Prof. Valery Il'in

Computing Center, Siberian Division RAS, Novosibirsk (Russia)

The modern numerical methods for solving the linear algebra systems $Au = f$ with high order sparse matrices $A$, which arise in grid approximations of multidimensional boundary value problems, are based mainly on accelerated iterative processes with easily invertible preconditioning matrices presented in the form of approximate (incomplete) factorization of the original matrix $A$, see [1], [2] for example. We consider some recent algorithmic approaches, theoretical foundations, experimental data and open questions on applicaton of incomplete factorization for soluton of diffusion - convection PDE of elliptic and parabolic type. In general, the matrix $A=D-L-U$ with block diagonal or diagonal matrix $D$, low- and upper-triangular matrices $L$, $U$ can be approximated by the factorized matrix $B=(G-\bar{L})G^{-1}(G-\bar{U})$, where $G$ is block-diagonal matrix defined by some approximations of Shur complement matrices of $A$. We describe two sets of explicit and implicit methods with closure, in the sense, that in limit $B$ is the exact factorization of $A$. Several modifications of algorithms will be discussed: various iterative parameters which provide generalizations of well known methods, an application of extended row sum criteria $By_{k}=Ay_{k}$, with different ``probe" vectors $y_{k}$, $k=1,2,...,$, the symmetrized alternating direction methods with nonsymmetric preconditioners, adapted ``flow-directed" algorithms, some versions of algebraic domain decomposition and hierarhical multigrid approaches. In particular, the improved convergence rate of iterations is demonstrated for flow dominated diffusion - convection equations, if optimal mesh-ordering is used in definition of algorithm. Both theoretical estimates and computational results are included.