| This dissertation was primarily concerned with the solution of large sparse systems of linear equations. Such systems occur frequently in scientific computing, and it was our objective to solve these systems as efficiently as possible. Objectives of the dissertation are to improve the efficiency of iterative methods by exploiting the vector and concurrent capabilities of the new architecture machines.;In this dissertation we present an adaptive fill-in strategy for the construction of sparse approximate inverse preconditionings for a conjugate-residual-type iterative solver for these systems. The preconditioning presented is based on minimizing the Frobenius norm of the difference between the identity and the preconditioned matrix. We will show that the calculation of the approximate inverse based on this strategy yields a naturally column-oriented parallelism.;An analysis provides positive definiteness and condition number estimates for the preconditioned system under certain circumstances. We show that for the 1-norm, restricting the size of the difference matrix below 1 may require dense approximate inverses, but that this requirement does not hold for the 2-norm. Similarly, we show that reducing the Frobenius norm below 1 does not generally require that much fill-in. Numerical criteria are considered for determining which columns of the sparse approximate inverse require additional fill-in.;A sparse-graph algorithm is presented for locating fill-in within each column of the approximate inverse preconditioning. The numerical criteria and the fill-in algorithm are applied to each column as they are being computed independently.;We present results using a minimum-residual-type algorithm to illustrate the potential of the method. The results demonstrate that, because it is fully parallel, the algorithm has a high degree of efficiency. The results also demonstrate that, as expected, if a very stringent requirement is placed on the 1-norm (... |
