Skip to main content

SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS.

Publication ,  Journal Article
Opsahl, T; Reif, J
Published in: NASA Conference Publication
December 1, 1987

The implementation of Pan and Reif's Parallel Nested Dissection algorithm on mesh-connected parallel computers is described. This is the first known algorithm that allows very large, sparse linear systems of equations to be solved efficiently in polylog time using a small number of processors. We describe how the processor bound of PND can be matched to the number of processors available on a given parallel computer by slowing down the algorithm by constant factors. Also, for the important class of problems where G(A) is a grid graph, we detail a unique memory mapping that reduces the inter-processor communication requirements of PND to those that can be executed on mesh-connected parallel machines. The paper concludes with a description of an implementation on the Goodyear Aerospace Massively Parallel Processor (MPP), located at NASA Goddard Space Flight Center, for which we give a detailed discussion of data mappings and performance issues.

Duke Scholars

Published In

NASA Conference Publication

ISSN

0191-7811

Publication Date

December 1, 1987

Start / End Page

249 / 256
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Opsahl, T., & Reif, J. (1987). SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS. NASA Conference Publication, 249–256.
Opsahl, T., and J. Reif. “SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS.NASA Conference Publication, December 1, 1987, 249–56.
Opsahl T, Reif J. SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS. NASA Conference Publication. 1987 Dec 1;249–56.
Opsahl, T., and J. Reif. “SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS.NASA Conference Publication, Dec. 1987, pp. 249–56.
Opsahl T, Reif J. SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS. NASA Conference Publication. 1987 Dec 1;249–256.

Published In

NASA Conference Publication

ISSN

0191-7811

Publication Date

December 1, 1987

Start / End Page

249 / 256