Analysis and design of scalable parallel algorithms for scientific computing

This dissertation presents a methodology for understanding the performance and scalability of algorithms on parallel computers and the scalability analysis of a variety of numerical algorithms. We demonstrate the analytical power of this technique and show how it can guide the development of better parallel algorithms. We present some new highly scalable parallel algorithms for sparse matrix computations that were widely considered to be poorly suitable for large scale parallel computers. We present some laws governing the performance and scalability properties that apply to all parallel systems. We show that our results generalize or extend a range of earlier research results concerning the performance of parallel systems. Our scalability analysis of algorithms such as fast Fourier transform (FFT), dense matrix multiplication, sparse matrix-vector multiplication, and the preconditioned conjugate gradient (PCG) provides many interesting insights into their behavior on parallel computers. We have developed a highly parallel sparse Cholesky factorization algorithm that substantially improves the state of the art in parallel direct solution of sparse linear systems--both in terms of scalability and overall performance. This algorithm incurs less communication overhead and is more scalable than any previously known parallel formulation of sparse matrix factorization. An implementation of this algorithm on the T3D delivers up to 20 GFlops on 1024 processors for medium-size structural engineering and linear programming problems. To the best of our knowledge, this is the highest performance ever obtained for sparse Cholesky factorization on any supercomputer. In addition to Cholesky factorization, we present efficient parallel algorithms for two other phases of direct solution to a sparse SPD system of equations-symbolic factorization and for forward and backward substitution to solve the triangular systems resulting from sparse matrix factorization. Although our current implementations work for Cholesky factorization, the algorithm can be adapted for solving sparse linear least squares problems by QR factorization and for Gaussian elimination of matrices that do not require pivoting, thus paving the way for scalable parallel solution to an even wider class of problems.