The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/12170020
Record Status Checked
Record Id 12170020
Title Partitioning strategies for the block Cimmino algorithm
Abstract In the context of the block Cimmino algorithm, we study preprocessing strategies to obtain block partitionings that can be applied to general linear systems of equations Ax = b. We study strategies that transform the matrix AAT into a matrix with a block tridiagonal structure. This provides a partitioning of the linear system for row projection methods because block Cimmino is essentially equivalent to block Jacobi on the normal equations and the resulting partition will yield a two-block partition of the original matrix. Therefore the resulting block partitioning should improve the rate of convergence of block row projection methods such as block Cimmino. We discuss a way of obtaining a partitioning using a dropping strategy that gives more blocks at the cost of relaxing the two-block partitioning. We then use a hypergraph partitioning that works directly on the matrix A to reduce directly the connections between blocks. We give numerical results showing the performance of these techniques both in their effect on the convergence of the block Cimmino algorithm and in their ability to exploit parallelism.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Keywords unsymmetric matrices, , iterative methods, , hypergraph partitioning , sparse matrices, , Cuthill McKee,
Funding Information
Related Research Object(s): 65984 , 22827188
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Preprint RAL Preprints RAL-P-2014-005 2014. RAL-P-2014-005.pdf 2014