The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/65984
Record Status Checked
Record Id 65984
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 consider obtaining a partitioning by using hypergraph partitioning that works directly on the matrix A to reduce the interconnections 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
Keywords iterative methods , Cuthill McKee , hypergraph partitioning , unsymmetric matrices , sparse matrices
Funding Information
Related Research Object(s): 12170020 , 22827188
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Preprints RAL-P-2013-010. 2013. RAL-P-2013-010.pdf 2013