A Multi-Level Method for Sparse Linear Systems

Yair Shapira

Los Alamos National Laboratory
Mail Stop B-256
Los Alamos, NM 87545


A multi-level method for the solution of sparse linear systems is introduced. The method is defined in terms of the coefficient matrix alone; no underlying PDE or mesh are assumed. An upper bound for the condition number is available for a class of SPD problems. In particular, for certain discretizations of diffusion boundary value problems this bound grows only polynomially with the number of levels used, no matter wether the discontinuities in the diffusion coefficient align or do not align with the coarse grids. Numerical results in line with the analysis are presented for a diffusion problem with discontinuous coefficients.