Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems
Dumitrasc A, Leleux P, Popa C, Rüde U, Ruiz D (2021)
Publication Language: English
Publication Type: Journal article, Online publication
Publication year: 2021
Journal
Book Volume: SPECIAL SECTION Copper Mountain 2020
Pages Range: S516-S539
URI: https://epubs.siam.org/doi/abs/10.1137/20M1348261
DOI: 10.1137/20M1348261
Abstract
For the solution of large sparse unsymmetric systems, Duff et al. [SIAM J. Sci. Comput., 37 (2015), pp. A1248--A1269] proposed an approach based on the block Cimmino iterations [Numer. Math., 35 (1980), pp. 1--12], in which the solution is computed in a single iteration, so we call it a pseudodirect solver. In this approach, matrices are augmented with additional variables and constraints so that a partitioning of the matrix in blocks of rows defines mutually orthogonal subspaces. The augmented system can then be solved efficiently with a sum of projections onto these orthogonal subspaces. The purpose of this manuscript is to extend this method to the minimum norm solution of underdetermined systems and to the solution of least-squares problems. In the latter case, a partitioning of the matrix in blocks of columns rather than rows is used, and the system must be suitably augmented to define mutually orthogonal subspaces again to recover the least-squares solution of the original problem. This article proves the equivalence between the solution of the original and the augmented system. In order to complete the extension to overdetermined systems, we also propose an iterative block conjugate gradient acceleration [SIAM J. Sci. Comput., 16 (1995), pp. 1478--1511] for the solution of least-squares problems. The efficiency of both the iterative and the augmented pseudodirect approaches, as implemented in the ABCD-Solver, is illustrated on large rectangular matrices from the SuiteSparse Matrix Collection. -We have learnt with great sadness that our co-author, long-term collaborator, advisor, and good friend Constantin Popa passed away while we were revising this article. We would like to dedicate this work to his memory.
Authors with CRIS profile
Andrei Dumitrasc
Lehrstuhl für Informatik 10 (Systemsimulation)
Ulrich Rüde
Lehrstuhl für Informatik 10 (Systemsimulation)
Involved external institutions
Ovidius University of Constanta
Romania (RO)
Toulouse Computer Science Research Institute (IRIT) / Institut de Recherche en Informatique de Toulouse (IRIT)
France (FR)
Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS)
France (FR)
Romania (RO)
Toulouse Computer Science Research Institute (IRIT) / Institut de Recherche en Informatique de Toulouse (IRIT)
France (FR)
Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS)
France (FR)
How to cite
APA:
Dumitrasc, A., Leleux, P., Popa, C., Rüde, U., & Ruiz, D. (2021). Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems. SIAM Journal on Scientific Computing, SPECIAL SECTION Copper Mountain 2020, S516-S539. https://dx.doi.org/10.1137/20M1348261
MLA:
Dumitrasc, Andrei, et al. "Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems." SIAM Journal on Scientific Computing SPECIAL SECTION Copper Mountain 2020 (2021): S516-S539.
BibTeX: Download