EUVIMEDEUVIMED entdecken
Crossref

Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement

F. Sukru Torun, Murat Manguoglu, Cevdet Aykanat

SIAM Journal on Scientific Computing · 30.04.2023 · 45 (2) · C49-C72

DOI: 10.1137/21m1453475 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Scientific Computing, online erschienen am 07.04.2023. Verfasst von F. Sukru Torun und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: BAGEP Award of the Science Academy, National Center for High Performance Computing of Turkey.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • BAGEP Award of the Science Academy
  • National Center for High Performance Computing of Turkey

Zitieren

APA

Torun, F. S., Manguoglu, M., & Aykanat, C. (2023). Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement. SIAM Journal on Scientific Computing, 45(2), C49-C72. https://doi.org/10.1137/21m1453475

Vancouver

Torun FS, Manguoglu M, Aykanat C. Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement. SIAM Journal on Scientific Computing. 2023;45(2):C49-C72. doi:10.1137/21m1453475

BibTeX
@article{Torun2023,
  author = {Torun, F. Sukru and Manguoglu, Murat and Aykanat, Cevdet},
  title = {Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement},
  journal = {SIAM Journal on Scientific Computing},
  year = {2023},
  volume = {45},
  number = {2},
  pages = {C49--C72},
  doi = {10.1137/21m1453475}
}
Kostenlos starten →