Permuting Sparse Rectangular Matrices into Block-Diagonal Form

DOI10.1137/S1064827502401953zbMath1070.65027OpenAlexW1996309908WikidataQ60164465 ScholiaQ60164465MaRDI QIDQ4652297

Ali Pınar, Cevdet Aykanat, Ümit V. Çatalyürek

Publication date: 25 February 2005

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1064827502401953

zbMATH Keywords

linear programmingnumerical experimentsparallel computationhypergraph partitioningsparse rectangular matricesbordered block diagonal form

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical mathematical programming methods (65K05) Linear programming (90C05) Hypergraphs (05C65) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Parallel numerical computation (65Y05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Minimizing fleet operating costs for a container transportation company ⋮ Computing sparse and dense realizations of reaction kinetic systems ⋮ A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems ⋮ Parallel distributed-memory simplex for large-scale stochastic LP problems ⋮ A branch-and-price algorithm for capacitated hypergraph vertex separation ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ Split cuts from sparse disjunctions ⋮ Relational data factorization ⋮ Parallel multilevel algorithms for hypergraph partitioning ⋮ Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices ⋮ Structure Detection in Mixed-Integer Programs ⋮ The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures ⋮ On the (co)girth of a connected matroid ⋮ Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation ⋮ A survey of direct methods for sparse linear systems ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Towards a practical parallelisation of the simplex method ⋮ Adapting Iterative-Improvement Heuristics for Scheduling File-Sharing Tasks on Heterogeneous Platforms ⋮ Automatic Dantzig-Wolfe reformulation of mixed integer programs ⋮ A novel framework for detecting maximally banded matrices in binary data ⋮ Optimal block-tridiagonalization of matrices for coherent charge transport ⋮ Parallel subgradient algorithm with block dual decomposition for large-scale optimization ⋮ Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming

Uses Software

• LOQO
• METIS
• IMSL Numerical Libraries
• Chaco
• PaToH

This page was built for publication: Permuting Sparse Rectangular Matrices into Block-Diagonal Form