Personal tools
You are here: Home Publications On the Use of OpenMP for the Recursive Spectral Bi-Section Method
Document Actions

Priti Mehta (2003)

On the Use of OpenMP for the Recursive Spectral Bi-Section Method

Master thesis, Computer Science, University of Houston, 4800 Calhoun Road, Houston, TX 77204.

In this thesis we study the use of OpenMP for parallelization of a divide-and-conquer method, namely graph partitioning used Multilevel Recursive Spectral Bisection (MRSB). The graphs can be represented with sparse, symmetric, positive semidefinite Laplacian matrices. A good partition divides the data evenly among processors and minimizes communication between the processors. The essence of Recursive Spectral Bisection (RSB) is to determine the first non-trivial eigenvalue and its associated cigenvector of the Lapacian matrix. The multi-level feature added to RSB reduces the size of the graph for which a Laplacian matrix is formed through a sequnce of coarsening steps, with the partitioning of the original graph determined through a number of projection and refinement steps to attempt to resolve the effects of the coarsening. Execution results from the use of OpenMP on SGI Origin 2000 are reported for several graphs with a detailed analysis provided for one graph with about 100,000 nodes.

by admin last modified 2007-12-10 21:05
« September 2010 »
Su Mo Tu We Th Fr Sa
1234
567891011
12131415161718
19202122232425
2627282930
 

Powered by Plone

LACSI Collaborators include:

Rice University LANL UH UNM UIUC UNC UTK