Permuting sparse rectangular matrices into block-diagonal form

doi:10.1137/S1064827502401953

2004-01-01

Cevdet Aykanat

Ali Pınar

Ümit V. Çatalyürek

DOI：10.1137/S1064827502401953

原文链接

原文求助

摘要

En 中文

We investigate the problem of permuting a sparse rectangular matrix into block-diagonal form. Block-diagonal form of a matrix grants an inherent parallelism for solving the deriving problem, as recently investigated in the context of mathematical programming, LU factorization, and QR factorization. To represent the nonzero structure of a matrix, we propose bipartite graph and hypergraph models that reduce the permutation problem to those of graph partitioning by vertex separator and hypergraph partitioning, respectively. Our experiments on a wide range of matrices, using the state-of-the-art graph and hypergraph partitioning tools MeTiS and PaToH, revealed that the proposed methods yield very effective solutions both in terms of solution quality and runtime.

Keyword:

coarse-grain parallelism

sparse rectangular matrices

singly bordered block-diagonal form

doubly bordered block-diagonal form

graph partitioning by vertex separator

hypergraph partitioning

期刊

SIAM Journal on Scientific Computing

IF:

2.6

论文数:

5.1K

被引数:

1.8W

机构

暂无机构信息

引用论文

USE OF LUTEIN AND ZEAXANTHIN ALONE OR COMBINED WITH BRILLIANT BLUE TO IDENTIFY INTRAOCULAR STRUCTURES INTRAOPERATIVELY

Retina

IF0

2012-07-01

PREAI

Diogo Sousa-Martins; Maurício Maia; Milton Moraes; Acácio A. S. Lima-Filho; Eduardo B. Rodrigues; Jane Chen; Michel E. Farah; Leticia B. Santos; Rubens Belfort

Improving the run time and quality of nested dissection ordering

SIAM JOURNAL ON SCIENTIFIC COMPUTING

IF2.6

1998-01-01

PREAI

Hendrickson, B; Rothberg, E

Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

IF6

1999-07-01

377

PREAI