Reevaluating Spectral Partitioning for Unsymmetric Matrices

Download

12625721.pdf

Date

2020-9

Author

Oktay, Eda

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

246
views

223
downloads

Parallel solutions to scientific problems having graph representation require efficienttasks and partitioning data. In this thesis, various parallel graph partitioning algorithms are studied. While these algorithms are applicable to both directed and undirected graphs, we focus on the directed case whose matrix representations are sparse and unsymmetric arising in linear system of equations representing various application domains such as computational fluid dynamics and thermal problems. Strategies inspected in this study are ParMETIS with the Multilevel Kernighan-Lin algorithm and the spectral partitioning algorithm with k-means clustering (SPEC) as well as the recursive spectral partitioning algorithm in CHACO. We have implemented SPEC in C programming language using PETSc and SLEPc libraries, whereas CHACO and ParMETIS are called from PETSc. Weighted partitioning is done under the consideration of the edge weights of the graph. SPEC is compared with the libraries only when the unweighted partitioning is made due to the limitations of the libraries for weighted partitioning. Hence, for weighted partitioning, only various eigensolver tolerances in SLEPc are studied in terms of the edge-cut and partitioning time. Another study is performed for the spectral partitioning algorithm based on eigensolver tolerance used with the k-means algorithm in MATLAB. The comparison is based on the quality of the partitioning (edge-cut and partition imbalance) and the number of iterations. The quality of partitioning is determined by the edge-cut and the load im balance, which could be based on the edge and vertex imbalance ratios of partitions depending on the application. Since the adjacency matrix of a graph is structurally symmetric, the eigenvalue problem can only be solved approximately when the matrix is unsymmetric. Thus, only approximate results are provided in this study. It is deduced that using SPEC performs better than the existing software libraries when the number of cut edges is compared in unweighted partitioning of unsymmetric matrices.

Subject Keywords

K-means clustering, Parallel graph partitioning, Domain decomposition, Spectral partitioning, Laplacian, PETSc, SLEPc, ParMETIS, CHACO

URI

https://hdl.handle.net/11511/69212

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Parallel linear solution of large structures on heterogeneous PC clusters Kurç, Özgür (2006-12-01) In this paper, a parallel solution framework for the linear static analysis of large structures on heterogeneous PC clusters is presented. The framework consists of two main steps; data preparation and parallel solution. The parallel solution is performed by a substructure based method with direct solvers. The aim of the data preparation step is to create the best possible substructures so that the condensation times of substructures are balanced. Examples which illustrate the applicability and the efficien...
Investigation of Stationarity for Graph Time Series Data Sets Güneyi, Eylem Tuğçe; Vural, Elif (2021-01-07) Graphs permit the analysis of the relationships in complex data sets effectively. Stationarity is a feature that facilitates the analysis and processing of random time signals. Since graphs have an irregular structure, the definition of classical stationarity does not apply to graphs. In this study, we study how stationarity is defined for graph random processes and examine the validity of the stationarity assumption with experiments on synthetic and real data sets.
A Theoretical Analysis of Multi-Modal Representation Learning with Regular Functions Vural, Elif (2021-01-07) Multi-modal data analysis methods often learn representations that align different modalities in a new common domain, while preserving the within-class compactness and within-modality geometry and enhancing the between-class separation. In this study, we present a theoretical performance analysis for multi-modal representation learning methods. We consider a quite general family of algorithms learning a nonlinear embedding of the data space into a new space via regular functions. We derive sufficient condit...
A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2018-01-01) We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation define...
A Comparative Study on Two Different Direct Parallel Solution Strategies for Large-Scale Problems Bahcecioglu, T.; Ozmen, S.; Kurç, Özgür (2009-04-08) This paper presents a comparative study on two different direct parallel solution strategies for the linear solution of large scale actual finite element models: global and domain-by-domain. The global solution strategy was examined by utilizing the parallel multi-frontal equation solver, MUMPS [1], together with a finite element program. In a similar manner a substructure based parallel solution framework [2] was utilized for investigating the domain-by-domain strategy. Various large-scale structural model...

Citation Formats

E. Oktay, “Reevaluating Spectral Partitioning for Unsymmetric Matrices,” M.S. - Master of Science, Middle East Technical University, 2020.