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

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, Nodal decompositions of graphs, On \(k\)-ary \(n\)-cubes: Theory and applications., Laplacian matrices of product graphs: applications in structural mechanics, Parallel adaptive solution of 3D boundary value problems by Hessian recovery, Consistency of spectral clustering, Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs, Extension and optimization of the FIND algorithm: Computing Green's and less-than Green's functions, An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification, Credible seed identification for large-scale structural network alignment, Sparse direct factorizations through unassembled hyper-matrices, Graph clustering, A multidimensional and multimembership clustering method for social networks and its application in customer relationship management, Spectral clustering and the high-dimensional stochastic blockmodel, Spectral bisection of graphs and connectedness, Co-clustering documents and words by minimizing the normalized cut objective function, Decentralized mining social network communities with agents, Connectivity and eigenvalues of graphs with given girth or clique number, The symbiotic relationship of combinatorics and matrix theory, Variational perspective on local graph clustering, On Laplacian spectra of parametric families of closely connected networks with application to cooperative control, A modularity-maximization-based approach for detecting multi-communities in social networks, A multilevel bilinear programming algorithm for the vertex separator problem, Experience in using SIMD and MIMD parallelism for computational fluid dynamics, Mesh partitioning algorithms for the parallel solution of partial differential equations, Laplace eigenvalues of graphs---a survey, Ordering trees and graphs with few cycles by algebraic connectivity, An efficient and accurate method to compute the Fiedler vector based on Householder deflation and inverse power iteration, Sparse regular random graphs: spectral density and eigenvectors, Computing semantic clusters by semantic mirroring and spectral graph partitioning, Parallel adaptation of general three-dimensional hybrid meshes, New challenges in dynamic load balancing, A MIMD implementation of a parallel Euler solver for unstructured grids, Improved group theoretic method using graph products for the analysis of symmetric-regular structures, Finding community structures in complex networks using mixed integer optimisation, Spectral clustering with physical intuition on spring-mass dynamics, Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient, Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks, Combinatorial optimization of special graphs for nodal ordering and graph partitioning, Eigenvectors of random matrices: A survey, Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces, Overlapping communities and roles in networks with node attributes: probabilistic graphical modeling, Bayesian formulation and variational inference, Partitioning graphs on message-passing machines by pairwise mincut, Spectral partitioning with multiple eigenvectors, Towards quantum computing based community detection, A spectral clustering-based framework for detecting community structures in complex networks, A parallel multi-\(p\) method, Data structures and load balancing for parallel adaptive \(hp\) finite-element methods, Parallel adaptive subspace correction schemes with applications to elasticity, Dynamic load balancing in computational mechanics, A fast constrained image segmentation algorithm, Numerical linear algebra algorithms and software, The impact of high-performance computing in the solution of linear systems: Trends and problems, Parallel load balancing for dynamic execution environments, Computation of incompressible flows with implicit finite element implementations on the Connection Machine, Laplacian matrices of graphs: A survey, Role of normalization in spectral clustering for stochastic blockmodels, Drawing graphs by eigenvectors: theory and practice, Some two-vertex resistances of nested triangle network, 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

Uses Software

Harwell-Boeing sparse matrix collection