A parallel graph partitioning algorithm for a message-passing multiprocessor

DOI10.1007/BF01388998zbMath0657.68073OpenAlexW2786884778MaRDI QIDQ1111029

John R. Gilbert, Earl Zmijewski

Publication date: 1987

Published in: International Journal of Parallel Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01388998

zbMATH Keywords

hypercubeparallel algorithmsparse Cholesky factorizationgraph partitioningcomplexity analysisKernighan-Lin algorithmreordering sparse matrices

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)

Related Items

Approximation techniques for hypergraph partitioning problems, A parallel graph partitioning algorithm for a message-passing multiprocessor, A fast algorithm for sparse matrix computations related to inversion, Extension and optimization of the FIND algorithm: Computing Green's and less-than Green's functions, Task scheduling for parallel sparse Cholesky factorization, Online partitioning method for decentralized control of linear switching large-scale systems, A multilevel bilinear programming algorithm for the vertex separator problem, A survey of direct methods for sparse linear systems, Partitioning graphs on message-passing machines by pairwise mincut

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel pivoting algorithms for sparse symmetric matrices
• Computational models and task scheduling for parallel sparse Cholesky factorization
• The analysis of a nested dissection algorithm
• A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor
• A parallel graph partitioning algorithm for a message-passing multiprocessor
• Communication results for parallel sparse Cholesky factorization on a hypercube
• Sparse Cholesky Factorization on a Local-Memory Multiprocessor
• Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
• QR Factorization for Linear Least-Squares Problems on a Hypercube Multiprocessor
• Generalized Nested Dissection
• Applications of a Planar Separator Theorem
• An Efficient Heuristic Procedure for Partitioning Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A comparasion of three resequencing algorithms for the reduction of matrix profile and wavefront
• An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems