Accession Number : ADA308547

Title :   Scalable Parallel Algorithms.

Descriptive Note : Final rept.,

Corporate Author : MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE

Personal Author(s) : Kumar, Vipin

PDF Url : ADA308547

Report Date : 11 MAR 1996

Pagination or Media Count : 9

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.

Descriptors :   *ALGORITHMS, *PROBLEM SOLVING, *PARALLEL ORIENTATION, SIMULATION, METHODOLOGY, FORMULATIONS, GRAPHS, EFFICIENCY, PARALLEL PROCESSING, BOUNDARIES, PARTICLES, QUALITY, SCALING FACTOR, HIGH DENSITY, SUPERCOMPUTERS, EQUATIONS, HIERARCHIES, MULTIPOLARITY, N BODY PROBLEM, ASTROPHYSICS, LINEAR DIFFERENTIAL EQUATIONS.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE