EFFICIENT APPROXIMATE SOLUTION OF SPARSE LINEAR-SYSTEMS

We consider the problem of approximate solution (x) over tilde of of a linear system Ax = b over the reals, such that \\A (x) over tilde - b \\ less than or equal to epsilon\\b\\, for a given epsilon, 0 < epsilo n < 1. This is one of the most fundamental of all computational proble ms. Let kappa(A) = \\A\\ \\A(-1)\\ be the condition number of the n x n input matrix A. Sparse, Diagonally Dominant (DD) linear systems appe ar very frequently in the solution of linear systems associated with P DEs and stochastic systems, and generally have polynomial condition nu mber. While there is a vast literature on methods for approximate solu tion of sparse DD linear systems, most of the results are empirical, a nd to date there are no known proven linear bounds on the complexity o f this problem. Using iterative algorithms, and building on the work o f Vaidya [1] and Gremban et al. [2-4] we provide the best known sequen tial work bounds for the solution of a number of major classes of DD s parse linear systems. Let pi = log(kappa(A)/epsilon). The sparsity gra ph of A is a graph whose nodes are the indices and whose edges represe nt pairs of indices of A with nonzero entries. The following results h old for a DD matrix A with nonzero off-diagonal entries of bounded mag nitude: (1) if A has a sparsity graph which is a regular d-dimensional grid for constant d, then our work is O(n pi(2)), (2) if A is a stoch astic matrix with fixed s(n)-separable graph as its sparsity graph, th en our work is O((n + s(n)(2))pi). The following results hold for a DD matrix A with entries of unbounded magnitude: (3) if A is sparse (i.e ., O(n) nonzeros), our work is less than O(n(n + log n))(1.5), (4) if A has a sparsity graph in a family of graphs with constant size forbid den graph miners (e.g., planar graphs), then our work is bounded by O( n(pi + log n)(1+o(1))) in the case log n = o(log pi) and O(n(pi + log n))(1+o)(1) in the case log pi = o(log n). We use approximate precondi tioned iterations to compute a sequence of iterative improvements to t he preconditioned linear system. For class (1) of matrices land class (2) with s(n) =. O(root n)), we construct in n) work preconditioners, which reduce the condition number of the resulting preconditioned line ar system condition number to O(1); and our resulting total work bound s to approximately solve the linear systems are O(n), if n = O(1). For class (4), we are within a small increasing factor of these bounds. ( C) 1998 Elsevier Science Ltd. All rights reserved.