Efficient Approximate Solution of Sparse Linear Systems

We consider the problem of approximate solution ex of a linear system Ax = b over the reals, such that kAex, bk kbk; for a given; 0 < < 1: This is one of the most fundamental of all computational problems. Let (A) = kAkkA,1 k be the condition number of the n n input matrix A. Sparse, diagonally dominant (DD) linear systems appear very frequently in the solution of linear systems associated with PDEs and stochastic systems, and generally have polynomial condition number. While there is a vast literature on methods for approximate solution of sparse DD linear systems, most of the results are empirical, and to date there are no known proven linear bounds on the complexity of this problem. Using iterative algorithms, and building on the work of Vaidya [V 91] and Gremban et al [GMZ 94, GMZ 95, G 96], we provide the best known sequential work bounds for the solution of a number of major classes of DD sparse linear systems. Let = log ( (A) =). The sparsity graph of A is a graph whose nodes are the indices and whose edges represent pairs of indices of A with non-zero entries. The following results hold for a DD matrix A with non-zero o-diagonal entries of bounded magnitude: (1) if A has a sparsity graph which isaregular d,dimensional grid for constant d; then our wor