Scalable Parallel Algorithms.
Abstract
The objective of this research is to develop efficient parallel algorithms for solving large sparse linear systems of equations: In particular, it looks at direct solvers for solving sparse linear systems, hierarchical algorithms for n-body simulations, and fast and high quality graph partitioners. As a part of this research, we have developed and implemented a massively parallel formulation of sparse Cholesky factorization. This implementation delivers up to 20 GFLOPS on a 1024 processor Cray T3D even for medium sized problems. This is the highest performance obtained on any supercomputer (vector or parallel) for sparse Cholesky factorization. We have also developed a fast and high quality graph partitioning algorithm that is roughly two orders of magnitude faster than widely used spectral methods, and produces better quality partitions. We have developed massively parallel formulations of particle simulation techniques such as Fast Multipole and Barnes- Hut methods. We have applied this formulation to astrophysical simulations and for computing the core matrix-vector product in dense boundary element solvers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 11, 1996
- Accession Number
- ADA308547
Entities
People
- Vipin Kumar
Organizations
- University of Minnesota