ENHANCING BLOCK CIMMINO FOR SPARSE LINEAR SYSTEMS WITH DENSE COLUMNS VIA SCHUR COMPLEMENT

Date

2023-01-01

Author

TORUN, FAHREDDİN ŞÜKRÜ
Manguoğlu, Murat
Aykanat, Cevdet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

102
views

0
downloads

Cite This

The block Cimmino is a parallel hybrid row-block projection iterative method successfully used for solving general sparse linear systems. However, the convergence of the method degrades when angles between subspaces spanned by the row-blocks are far from being orthogonal. The density of columns as well as the numerical values of their nonzeros are more likely to contribute to the nonorthogonality between row-blocks. We propose a novel scheme to handle such ``dense"" columns. The proposed scheme forms a reduced system by separating these columns and the respective rows from the original coefficient matrix and handling them via the Schur complement. Then the angles between subspaces spanned by the row-blocks of the reduced system are expected to be closer to orthogonal, and the reduced system is solved efficiently by the block conjugate gradient (CG) accelerated block Cimmino in fewer iterations. We also propose a novel metric for selecting ``dense"" columns considering the numerical values. The proposed metric establishes an upper bound on the sum of inner products between row-blocks. Then we propose an efficient algorithm for computing the proposed metric for the columns. Extensive numerical experiments for a wide range of linear systems confirm the effectiveness of the proposed scheme by achieving fewer iterations and faster parallel solution time compared to the classical CG accelerated block Cimmino algorithm.

Subject Keywords

hybrid methods, Krylov subspace methods, parallel block Cimmino, row projection methods, Schur complement

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85153853390&origin=inward
https://hdl.handle.net/11511/103409

Collections

Department of Computer Engineering, Article