Partitioning of unstructured problems for parallel processing
Computing Systems in EngineeringPublished 1 January 1991
Horst D. Simon
Citations723
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Numerical comparisons on large-scale two- and three-dimensional problems demonstrate the superiority of the new spectral bisection algorithm.
Abstract
Many large-scale computational problems are based on unstructured computational domains. Primary examples are unstructured grid calculations based on finite volume methods in computational fluid dynamics, or structural analysis problems based on finite element approximations. Here we will address the question of how to distribute such unstructured computational domains over a large number of processors in a MIMD machine with distributed memory. A graph theoretical framework for these problems will be established. Based on this framework three decomposition algorithms will be introduced. In particular a new decomposition algorithm will be discussed, which is based on the computation of an eigenvector of the Laplacian matrix associated with the graph. Numerical comparisons on large-scale two- and three-dimensional problems demonstrate the superiority of the new spectral bisection algorithm.
Keywords
Computer ScienceEngineering
Bell System Technical JournalAn Efficient Heuristic Procedure for Partitioning Graphs
5,218 Citations1970Brian W. Kernighan, Shang Min Lin
A heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems is presented.
Society for Industrial and Applied Mathematics eBooksThe Symmetric Eigenvalue Problem
3,212 Citations1998Beresford Ν. Parlett
27th Aerospace Sciences MeetingThe design and application of upwind schemes on unstructured meshes
2,203 Citations1989Timothy J. Barth, Dennis C. Jespersen
Cell-centered and mesh-vertex upwind finite-volume schemes are developed which utilize multi-dimensional monotone linear reconstruction procedures which differ from existing algorithms (even on structured meshes).
TechnometricsIntroduction to Multivariate Analysis
1,789 Citations1983Jack C. Lee, C. Chatfield +1 more
SIAM Journal on Matrix Analysis and ApplicationsPartitioning Sparse Matrices with Eigenvectors of Graphs
1,692 Citations1990Alex Pothen, Horst D. Simon +1 more
It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph, which can be used to compute good separators in grid graphs.
Introduction to Multivariate Analysis
1,136 Citations1980Christopher Chatfield, Alexander J. Collins
THE LAPLACIAN SPECTRUM OF GRAPHS y
1,118 Citations1991Bojan Mohar
Mspace (University of Manitoba)The Laplacian spectrum of graphs
654 Citations2001Michael Newman
This paper is essentially a survey of known results about the spectrum of the Laplacian matrix of graphs with special emphasis on the second smallest LaPLacian eigenvalue λ2 and its relation to numerous graph invariants, including connectivity, expanding properties, isoperimetric number, maximum cut, independence number, genus, diameter, mean distance, and bandwidth-type parameters of a graph.
Journal of Computer and System SciencesA framework for solving VLSI graph layout problems
438 Citations1984Sandeep Bhatt, Frank Thomson Leighton
A new divide-and-conquer framework for VLSI graph layout is introduced and Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay.
Concurrency Practice and ExperiencePerformance of dynamic load balancing algorithms for unstructured mesh calculations
346 Citations1991Roy Williams
Three parallel algorithms, Orthogonal Recursive Bisection (ORB), Eigenvector Recursive bisection (ERB) and a simple parallelization of Simulated Annealing (SA) have been implemented for load balancing a dynamic unstructured triangular mesh on 16 processors of an NCUBE machine.
NASA Technical Reports Server (NASA)Solving finite element equations on concurrent computers
116 Citations1987B. Nour‐Omid, A. Raefsky +1 more
This paper discusses the development of a concurrent algorithm for the solution of systems of equations arising in finite element applications based on a hybrid of direct elimination method and preconditioned conjugate iteration.
The Journal of SupercomputingA MIMD implementation of a parallel Euler solver for unstructured grids
89 Citations1992V. N. Venkatakrishnan, Horst D. Simon +1 more
A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on a MIMD (multiple instruction/multiple data stream) parallel computer and it is found that the spectral bisection strategy yields the best performance.
Mathematics of ComputationOn estimating the largest eigenvalue with the Lanczos algorithm
83 Citations1982Beresford Ν. Parlett, Horst D. Simon +1 more
A simple algorithm which computes the largest eigenvalue is developed which is especially economical if the order of the matrix is large and the accuracy requirements are low.
Linear Algebra and its ApplicationsGraph partitioning by Eigenvectors
80 Citations1988David L. Powers
NASA STI Repository (National Aeronautics and Space Administration)On unstructured grids and solvers
58 CitationsTimothy J. Barth
It is shown that grid generation and grid manipulation schemes rely on fast multidimensional searching, and flow solution techniques for the Euler equations, which can be derived from the integral form of the equations are discussed.
International Journal for Numerical Methods in EngineeringTransient finite element computations on 65536 processors: The connection machine
37 Citations1990Charbel Farhat, Nahil Sobh +1 more
The combination of the parallel data structure with the virtual processor mapping algorithm is shown to play a pivotal role in efficiently achieving massively parallel explicit computations on irregular and hybrid two- and three-dimensional finite element meshes.
Computers & StructuresOn the mapping of massively parallel processors onto finite element graphs
31 Citations1989Charbel Farhat
Two algorithms are presented, one for MIMD machines and another for SIMD computers and it is shown that over a trivial mapping and with a quite reasonable complexity, both algorithms can significantly reduce the cost/bandwidth of communication of a massively parallel processor.
Proceedings of the Fifth Distributed Memory Computing Conference, 1990.
26 Citations1990
This book contains the proceedings of the fifth distributed memory computing conference, where topics included are: Mathematical Methods; Full and Banded Matrix Algorithms; Electromagnetic Scattering Problems; Plasma Physics Applications.
Mapping unstructured grid problems to the connection machine
19 Citations1992Steven W. Hammond, Robert Schreiber
This work presents a highly parallel graph mapping technique that enables one to solve unstructured grid problems on massively parallel computers and significantly reduces the communication time on the Connection Machine, CM-2.
Computing Systems in EngineeringStructural analysis on massively parallel computers
17 Citations1991Courtenay Vaughan
An implementation is presented for JAC3D on two massively parallel hypercube computers and the implementation and evaluation of four algorithms to map problems onto the node processors of the hypercube in a load-balanced fashion are discussed.
Performance Results on the Intel Touchstone Gamma Prototype
12 Citations2005David H. Bailey, Eric Barszcz +3 more
This paper describes the Intel Touchstone Gamma Prototype, a distributed memory MIMD parallel computer based on the new Intel i860 floating point processor, which has a theoretical peak performance of over seven GFLOPS.