Permuting Sparse Rectangular Matrices into Block-Diagonal Form (Q4652297)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2138715
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Permuting Sparse Rectangular Matrices into Block-Diagonal Form |
scientific article; zbMATH DE number 2138715 |
Statements
Permuting Sparse Rectangular Matrices into Block-Diagonal Form (English)
0 references
25 February 2005
0 references
sparse rectangular matrices
0 references
bordered block diagonal form
0 references
hypergraph partitioning
0 references
parallel computation
0 references
numerical experiments
0 references
linear programming
0 references
0.8994463
0 references
0.8962258
0 references
0.88374066
0 references
0 references
0.8745154
0 references
0.86522275
0 references
0 references
0.8619554
0 references
0.8597843
0 references
This paper is concerned with transforming a sparse rectangular matrix \(A\) into a doubly bordered block diagonal matrix \[ P A Q = \left[\begin{matrix} B_1 & & & C_1 \\ & \ddots & & \vdots \\ & & B_K & C_K \\ R_1 & \cdots & R_K & D \end{matrix} \right], \] by means of two permutation matrices \(P\) and \(Q\). The treatment also includes singly bordered variants, where either the blocks \(C_1,\dots, C_K,D\) or the blocks \(R_1, \dots,R_K,D\) are not present. Considering the bipartite graph associated with \(A\), it turns out that finding a permutation into a doubly bordered matrix amounts to graph partitioning by vertex separator (GPVS). Similarly, the singly bordered variant can be regarded as hypergraph partitioning. In the second part of the paper, the usefulness of several existing tools for graph partitioning by edge separator (an indirect means for solving GPVS) and hypergraph partitioning are studied. Numerical experiments for several matrices arising from linear programming suggest that PaToH, a multilevel hypergraph partitioning tool, yields an effective approach for both permutation problems.
0 references