Partitioning Sparse Matrices with Eigenvectors of Graphs

Alex Pothen, Horst D. Simon, K. N. Liou

Type: Article

Publication Date: 1990-07-01

Citations: 1683

DOI: https://doi.org/10.1137/0611030

View Publication

Locations

SIAM Journal on Matrix Analysis and Applications - View

Similar Works

Action	Title	Year	Authors
+	Parallel solutions for large-scale eigenvalue problems arising in graph analytics	2017	Alexandre Fender
+	Partitioning Sparse Graphs using the Second Eigenvector of their Graph Laplacian	2000	David De Wit
+	Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering	2022	Elise van der Pol Ian Gemp Yoram Bachrach Richard Everett
+	On the Quality of Spectral Separators	1998	Stephen Guattery Gary L. Miller
+	Matrix algorithms and graph partitioning	2010	M. E. J. Newman
+	Partitioning Networks by Eigenvectors	2004	Andrew Seary William D. Richards
+	A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning	2008	Daniel A. Spielman Shang‐Hua Teng
+	Spectral Algorithms for Ordering Sparse Matrices in Parallel	1989	Alex Pothen Horst D. Simon
+	On the complexity of partitioning sparse matrix representations	1984	J. Malmquist Edward L. Robertson
+ PDF Chat	A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning	2013	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems	2004	Daniel A. Spielman Shang‐Hua Teng
+	Algorithm Design Using Spectral Graph Theory	2013	Richard Peng
+	A general theorem for adjacency matrices of graph products and application in graph partitioning for parallel computing	2008	A. Kaveh Babak Alinejad
+ PDF Chat	Spectral sparsification of graphs	2013	Joshua Batson Daniel A. Spielman Nikhil Srivastava Shang‐Hua Teng
+	Solving Graph Laplacian Systems Through Recursive Partitioning and Two-Grid Preconditioning	2017	Colin Ponce Panayot S. Vassilevski
+ PDF Chat	Graph Partitioning and Eigenvalue Problems	2014	Tatsuro Kawamoto
+	The Laplacian Paradigm: Emerging Algorithms for Massive Graphs	2010	Shang‐Hua Teng
+	Graph Partitioning and Clustering	2021	K. Erciyes
+	Solving Large Top-K Graph Eigenproblems with a Memory and Compute-optimized FPGA Design	2021	Francesco Sgherzi Alberto Parravicini Marco Siracusa Marco D. Santambrogio
+	Solving Large Top-K Graph Eigenproblems with a Memory and Compute-optimized FPGA Design	2021	Francesco Sgherzi Alberto Parravicini Marco Siracusa Marco D. Santambrogio

Works That Cite This (380)

Action	Title	Year	Authors
+ PDF Chat	Spectral partitioning in equitable graphs	2017	Paolo Barucca
+	Ordering trees and graphs with few cycles by algebraic connectivity	2014	Nair Maria Maia de Abreu Cláudia Marcela Justel Óscar Rojo Vilmar Trevisan
+	Feature Detection in Hierarchical Structure Based on Tensor Factorization	2020	Zhe Li Dong Wang Ke Zhang
+	Eigenvectors of random matrices: A survey	2016	Sean O’Rourke Van Vu Ke Wang
+	Laplacian matrices of graphs: a survey	1994	Russell Merris
+	New techniques for parallel simulation of high-temperature superconductors	2002	Lori Freitag M. Jones Paul E. Plassmann
+	Direct Methods for Sparse Matrices	2017	Iain Duff A. M. Erisman J. K. Reid
+ PDF Chat	The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning	2017	Yannan Chen Liqun Qi Xiaoyan Zhang
+ PDF Chat	Community Structures of Networks	2008	William Y. C. Chen Andreas Dress Winking Q. Yu
+	An efficient communications strategy for finite element methods on the Connection Machine CM-5 system	1994	Zdeněk Johan Kapil K. Mathur S. Lennart Johnsson Thomas J.R. Hughes

Works Cited by This (17)

Action	Title	Year	Authors
+	Algebraic Graph Theory	1974	Norman Biggs
+ PDF Chat	Algebraic connectivity of graphs	1973	Miroslav Fiedler
+ PDF Chat	Eigenvalues and expanders	1986	Ilan Alon
+	Generalizations of Davidson’s Method for Computing Eigenvalues of Sparse Symmetric Matrices	1986	Ronald B. Morgan David Scott
+ PDF Chat	Graph Coloring Using Eigenvalue Decomposition	1984	Bengt Aspvall John R. Gilbert
+	Eigenvalues, diameter, and mean distance in graphs	1991	Bojan Mohar
+	On the bipartition of graphs	1984	Peter Buser
+	λ1, Isoperimetric inequalities for graphs, and superconcentrators	1985	Noga Alon Vitali Milman
+ PDF Chat	Eigenvalues of the Laplacian of a graph<sup>∗</sup>	1985	William N. Anderson T. D. Morley
+	Isoperimetric numbers of graphs	1989	Bojan Mohar