Methods for solving sparse linear systems of equations, especially of the type arising from discretized elliptic and parabolic partial differential equations, will be studied. The solution of such systems is often the most costly computation in scientific codes. Three general areas will be emphasized. Iterative solution of sparse linear systems of equations, including parallel techniques and nonsymmetric systems: "Multicolor" variants of incomplete factorization preconditioners display slower convergence than standard preconditioners on serial architectures, but theoretical and computational studies with model problems show them to be superior on parallel machines. These methods will be tested on problems arising in scientific application codes, where it is not certain that they will be robust. Alternatives, such as block ordering methods which have less efficient parallel implementations but display faster convergence on two-dimensional problems, will be examined. In addition, new analytic and experimental results suggest that iterative methods for nonsymmetric linear systems based on partial elimination and "line" preconditioners are very effective for solving the convection-diffusion equation. Further studies of these techniques will be made, including implementation on parallel architectures. Numerical methods for three-dimensional problems: Linear systems arising from three-dimensional elliptic problems cannot be solved at reasonable cost at the present time. Successful development of parallel and/or faster converging methods will expand the domain of solvable problems, but special attention must be paid to the specific issues associated with three-dimensionality. Two ideas will be examined: three-dimensional multicolor schemes, and "plane" preconditioners (which would generalize line methods). The latter idea build upon effective parallel two- dimensional solvers. Parallel implementation of finite element methods: Finite element methods comprise a widely used solution technique for elliptic problems that present special difficulties for parallel computing, including the presence of irregular grids and three- dimensional problems. High order finite element methods appear to offer some advantages for parallel solution of two-dimensional problems on uniform grids. Starting from this preliminary observation, the parallel solution of finite element models on irregular grids and in three dimensions will be studied. Two methodologies that will be considered are the combination of local direct solution with global iterative solution methods, and parallel solution using hierarchical basis functions.
