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
      0 references
      0 references
      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 references
      0 references
      0 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references