New spectral graph partitioning algorithms /
Fill-in occurs when direct methods such as Gaussian crofilm Inc. elimination are used to solve systems of linear equations. Fill-in occurs when entries of a sparse matrix change from zero to non-zero. This incurs overhead in the form (if additional memory required to store the non-zero values as wel...
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1998.
|
| Subjects: | |
| Online Access: | http://proxy.library.tamu.edu/login?url=http://proquest.umi.com/pqdweb?did=733050231&sid=1&Fmt=2&clientId=2945&RQT=309&VName=PQD |
| Summary: | Fill-in occurs when direct methods such as Gaussian crofilm Inc. elimination are used to solve systems of linear equations. Fill-in occurs when entries of a sparse matrix change from zero to non-zero. This incurs overhead in the form (if additional memory required to store the non-zero values as well as additional computation. Every sparse matrix has an associated graph. A distinct node t' is associated with each row of the matrix. Nodes vi and vj are connected by an edge if, and only if, the sparse matrix has a non-zero value in position (ơ j). Partitioning this graph into two roughly equal size components such that the number of edges cut is small can be used by Nested Dissection, a heuristic algorithm which finds fill-Dissection, a heuristic algorithm which finds fill-graph partitioning algorithmic include Kernighan-Lin, coordinate bi-section, and multilevel spectral bisection. Spectral algorithms partition a graph based on the Fiedler vector, which is the second smallest eigenvector of a matrix associated with a graph called the "graph Laplacian.'' Finding this eigenvector represents the majority of the time required by spectral partitioning techniques. This research explored ways to use the structure of the graph to accelerate the computation of the Fiedler vector. The Davidson algorithm, which is a subspace method allowing the use of preconditioning to speedup convergence, was used as tile eigensolver. The Davidson algorithm was modified in three ways. First, the series of coarse graphs was used as a framework for a multilevel preconditioned. Second, a favorable initial subspace for the Davidson algorithm was obtained bar rennin: the Davidson algorithm on the next coarser graph. Third, the series of coarse graphs were used to permute the input matrix to increase the concentration of the non-zero entries along the diagonal. This increased temporal and spatial locality of reference while computing the Fiedler vector. |
|---|---|
| Item Description: | Vita. "Major Subject: Computer Science". |
| Physical Description: | xii, 111 leaves : illustrations ; 28 cm. |
| Bibliography: | Includes bibliographical references (leaves 105-110). |