Domain Decomposition and Multi-Level Type
Techniques for General Sparse Linear Systems

Yousef Saad
Department of Computer Science and Engineering
University of Minnesota
4-192 EE/CS Building, 200 Union Street S.E.
Minneapolis, MN 55455, USA

Maria Sosonkina
Department of Computer Science
University of Minnesota at Duluth
320 Heller Hall, 10 University Drive
Duluth, MN 55812-2496, USA

Jun Zhang
Department of Computer Science and Engineering
University of Minnesota
4-192 EE/CS Building, 200 Union Street S.E.
Minneapolis, MN 55455, USA

Abstract

Domain-decomposition and multi-level techniques are often formulated for linear systems that arise from the solution of elliptic-type Partial Differential Equations. In this paper, generalizations of these techniques for irregularly structured sparse linear systems are considered. An interesting common approach used to derive successful preconditioners is to resort to Schur complements. In particular, we discuss a multi-level domain decomposition-type algorithm for iterative solution of large sparse linear systems based on independent subsets of nodes. We also discuss a Schur complement technique that utilizes incomplete LU factorizations of local matrices.

Key words: Schur complete techniques, Incomplete LU factorization, Schwarz iterations, multi-level ILU preconditioners, multi-elimination, Krylov subspace methods.

This research was supported by NSF (CCR-9618827) and Minnesota Supercomputer Institute. This paper has been published in Domain Decomposition Methods 10, , Volume 218 of Contemporary Mathematics, J. Mandel, C. Farhat, X.-C. Cai, editors, AMS, Providence, 1998, pp. 174--190. It has also been published as: Technical Report UMSI 97/244, Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN 55455, 1997.