Partitioning Sparse Matrices with Eigenvectors of Graphs

DOI10.1137/0611030zbMath0711.65034OpenAlexW2114030927MaRDI QIDQ3495536

Horst D. Simon, Alex Pothen, Kang-Pu Liou

Publication date: 1990

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e8f58cb70b0ec8a3a14a7e0447df54dd8ff41d30

zbMATH Keywords

eigenvalues sparse matrix lower bounds graph partitioning Laplacian matrix vertex separators graph spectra ordering algorithms parallel ordering partitioning sparse matrices

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (only showing first 100 items - show all)

Domain separation by means of sign changing eigenfunctions ofp-laplacians ⋮ Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Minimum supports of eigenfunctions of graphs: a survey ⋮ MODELING THE CO-OCCURRENCE PRINCIPLES OF THE CONSONANT INVENTORIES: A COMPLEX NETWORK APPROACH ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ Unnamed Item ⋮ EVALUATION OF AUTOMATIC DOMAIN PARTITIONING ALGORITHMS FOR PARALLEL FINITE ELEMENT ANALYSIS ⋮ On the maximal error of spectral approximation of graph bisection ⋮ Topology and graph products; eigenproblems in optimal structural analysis ⋮ COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗ ⋮ Improvements on Spectral Bisection ⋮ Rotation gene set testing for longitudinal expression data ⋮ A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph ⋮ Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners ⋮ A spectral approach to bandwidth and separator problems in graphs ⋮ The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning ⋮ Community detection with structural and attribute similarities ⋮ EAMCD: an efficient algorithm based on minimum coupling distance for community identification in complex networks ⋮ Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm ⋮ Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm ⋮ Hodge Laplacians on Graphs ⋮ The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures ⋮ Spectral trisection of finite element models ⋮ A GENETIC ALGORITHM FOR DETECTING COMMUNITIES IN LARGE-SCALE COMPLEX NETWORKS ⋮ A divisive spectral method for network community detection ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ Sparse random graphs: Eigenvalues and eigenvectors ⋮ Graph Partitioning via Adaptive Spectral Techniques ⋮ A new algorithm for domain decomposition of finite element models ⋮ Eigensolution of Laplacian matrices for graph partitioning and domain decomposition ⋮ Parallelization strategies for an implicit Newton-based reactive flow solver ⋮ Finite element mesh decomposition using complementary Laplacian matrix ⋮ Geometric Separators for Finite-Element Meshes ⋮ A survey of direct methods for sparse linear systems ⋮ Unnamed Item ⋮ On the Laplacian Eigenvalues of G_n,p ⋮ Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products ⋮ Eigenvectors of random graphs: Nodal Domains ⋮ Force-based incremental algorithm for mining community structure in dynamic network ⋮ Eigenvalues of the adjacency and Laplacian matrices for modified regular structural models ⋮ Local and global approaches of affinity propagation clustering for large scale data ⋮ PageRank Beyond the Web ⋮ Identification of network modules by optimization of ratio association ⋮ A unified method for eigendecomposition of graph products ⋮ TRACEMIN-Fiedler: A Parallel Algorithm for Computing the Fiedler Vector ⋮ A classification for community discovery methods in complex networks ⋮ A SPECTRAL METHOD FOR AGGREGATING VARIABLES IN LINEAR DYNAMICAL SYSTEMS WITH APPLICATION TO CELLULAR AUTOMATA RENORMALIZATION ⋮ Advanced Coarsening Schemes for Graph Partitioning ⋮ On some properties of the Laplacian matrix revealed by the RCM algorithm ⋮ Unnamed Item ⋮ Particle competition for complex network community detection ⋮ Algebraic connectivity of k-connected graphs ⋮ Partitioning networks into clusters and residuals with average association ⋮ Mortar Element Method for Flow Problems in Primitive Variables Form ⋮ Unnamed Item ⋮ The effectiveness of cyclic blockwise distribution ⋮ A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph ⋮ Top eigenpair statistics for weighted sparse graphs ⋮ Web document clustering using hyperlink structures ⋮ Parallel physical optimization algorithms for allocating data to multicomputer nodes ⋮ Complex systems: features, similarity and connectivity ⋮ Connectedness of users-items networks and recommender systems ⋮ Graph coarsening: from scientific computing to machine learning ⋮ Graph Laplacians, nodal domains, and hyperplane arrangements ⋮ A unified framework of multi-objective cost functions for partitioning unstructured finite element meshes ⋮ State-defect constraint pairing graph coarsening method for Karush-Kuhn-Tucker matrices arising in orthogonal collocation methods for optimal control ⋮ Load balancing for the parallel adaptive solution of partial differential equations ⋮ Approximation techniques for hypergraph partitioning problems ⋮ On the resistance diameter of the Cartesian and lexicographic product of paths ⋮ Tri-diagonal and penta-diagonal block matrices for efficient eigensolutions of problems in structural mechanics ⋮ Reducing the effect of global communication in \(\text{GMRES} (m)\) and CG on parallel distributed memory computers ⋮ A projection technique for partitioning the nodes of a graph ⋮ Geometrically nonlinear analysis of circulant structures using an efficient eigensolution method ⋮ Local community detection in dynamic graphs using personalized centrality ⋮ An efficient communications strategy for finite element methods on the Connection Machine CM-5 system ⋮ Scalability of finite element applications on distributed-memory parallel computers ⋮ Implementation of implicit finite element methods for incompressible flows on the CM-5 ⋮ Parallel adaptive mesh refinement and redistribution on distributed memory computers ⋮ Massively parallel finite element computations of three-dimensional, time-dependent, incompressible flows in materials processing systems ⋮ Ductile failure analyses on massively parallel computers ⋮ Recursive spectral algorithms for automatic domain partitioning in parallel finite element analysis ⋮ Using domain decomposition to find graph bisectors ⋮ Two improved algorithms for envelope and wavefront reduction ⋮ Large-scale contact/impact simulation and sensitivity analysis on distributed-memory computers ⋮ A parallel solver for the \(hp\)-version of finite element methods ⋮ A retrofit based methodology for the fast generation and optimization of large-scale mesh partitions: Beyond the minimum interface size criterion ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Minimum-perimeter domain assignment ⋮ New spectral lower bounds on the bisection width of graphs ⋮ A parallel \(hp\)-adaptive discontinuous Galerkin method for hyperbolic conservation laws ⋮ Scalable algorithms for the solution of Navier's equations of elasticity ⋮ Combining simulated annealing with local search heuristics ⋮ Parallel structures and dynamic load balancing for adaptive finite element computation ⋮ Complex networks: structure and dynamics ⋮ On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint ⋮ Iterative methods for the computation of a few eigenvalues of a large symmetric matrix ⋮ Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs ⋮ A domain-decomposition message-passing approach to transient viscous incompressible flow using explicit time integration ⋮ A novel partitioning method for block-structured adaptive meshes ⋮ A fast algorithm for sparse matrix computations related to inversion

Uses Software

Harwell-Boeing sparse matrix collection

This page was built for publication: Partitioning Sparse Matrices with Eigenvectors of Graphs