TRACEMIN Fiedler A Parallel Algorithm for Computing the Fiedler Vector

Date

2010-06-25

Author

Manguoğlu, Murat
Saied, Faisal
Sameh, Ahmed

Metadata

Show full item record

Item Usage Stats

273
views

0
downloads

The eigenvector corresponding to the second smallest eigenvalue of the Laplacian of a graph, known as the Fiedler vector, has a number of applications in areas that include matrix reordering, graph partitioning, protein analysis, data mining, machine learning, and web search. The computation of the Fiedler vector has been regarded as an expensive process as it involves solving a large eigenvalue problem. We present a novel and efficient parallel algorithm for computing the Fiedler vector of large graphs based on the Trace Minimization algorithm. We compare the parallel performance of our method with a multilevel scheme, designed specifically for computing the Fiedler vector, which is implemented in routine MC73_FIEDLER of the Harwell Subroutine Library (HSL).

Subject Keywords

Generalized eigenvalue problem, Sparse matrices, Graphs

URI

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

Conference Name

9th International Conference on High Performance Computing for Computational Science, 2010

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Sparse linear sensor arrays: analysis of recent coarray based arrays and array design for nonlinear processing Epçaçan, Erdal; Çiloğlu, Tolga; Department of Electrical and Electronics Engineering (2021-9-09) In this thesis, sparse linear sensor arrays have been studied. The study of sparse arrays in this work can be considered under two main headings: Analysis and comparison of recently proposed coarray based arrays, and the adaptation of the nonlinear apodization method for linear arrays and its use in sparse linear array design. Recently proposed coarray-based sparse arrays are designed with closed form structures without the need for any optimization and have much higher degrees of freedom (DOF) than a unif...
Loop-based conic multivariate adaptive regression splines is a novel method for advanced construction of complex biological networks Ayyıldız Demirci, Ezgi; Purutçuoğlu Gazi, Vilda; Weber, Gerhard Wilhelm (2018-11-01) The Gaussian Graphical Model (GGM) and its Bayesian alternative, called, the Gaussian copula graphical model (GCGM) are two widely used approaches to construct the undirected networks of biological systems. They define the interactions between species by using the conditional dependencies of the multivariate normality assumption. However, when the system's dimension is high, the performance of the model becomes computationally demanding, and, particularly, the accuracy of GGM decreases when the observations...
Collaborative Direction of Arrival estimation by using Alternating Direction Method of Multipliers in distributed sensor array networks employing Sparse Bayesian Learning framework Nurbas, Ekin; Onat, Emrah; Tuncer, Temel Engin (2022-10-01) In this paper, we present a new method for Direction of Arrival (DoA) estimation in distributed sensor array networks by using Alternating Direction Method of Multipliers (ADMM) in Sparse Bayesian Learning (SBL) framework. Our proposed method, CDoAE, has certain advantages compared to previous distributed DoA estimation methods. It does not require any special array geometry and there is no need for inter -array frequency and phase matching. CDoAE uses the distributed ADMM to update the parameter set extrac...
Similarity matrix framework for data from union of subspaces Aldroubi, Akram; Sekmen, Ali; Koku, Ahmet Buğra; Cakmak, Ahmet Faruk (2018-09-01) This paper presents a framework for finding similarity matrices for the segmentation of data W = [w(1)...w(N)] subset of R-D drawn from a union U = boolean OR(M)(i=1) S-i, of independent subspaces {S-i}(i=1)(M), of dimensions {d(i)}(i=1)(M). It is shown that any factorization of W = BP, where columns of B form a basis for data W and they also come from U, can be used to produce a similarity matrix Xi w. In other words, Xi w(i, j) not equal 0, when the columns w(i) and w(j) of W come from the same subspace, ...
Excessive Memory Usage of the ELLPACK Sparse Matrix Storage Scheme throughout the Finite Element Computations Akinci, Gokay; YILMAZ, ASIM EGEMEN; Kuzuoğlu, Mustafa (2014-12-01) Sparse matrices are occasionally encountered during solution of various problems by means of numerical methods, particularly the finite element method ELLPACK sparse matrix storage scheme, one of the most widely used methods due to its implementation ease, is investigated in this study. The scheme uses excessive memory due to its definition. For the conventional finite element method, where the node elements are used, the excessive memory caused by redundant entries in the ELLPACK sparse matrix storage sche...

Citation Formats

M. Manguoğlu, F. Saied, and A. Sameh, “TRACEMIN Fiedler A Parallel Algorithm for Computing the Fiedler Vector,” Berkeley, CA, 2010, vol. 6449, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/79077.