×

Extensions of the augmented block Cimmino method to the solution of full rank rectangular systems. (English) Zbl 1470.05101

Summary: For the solution of large sparse unsymmetric systems, I. S. Duff et al. [ibid. 37, No. 3, A1248–A1269 (2015; Zbl 1318.65016)] proposed an approach based on the block Cimmino iterations [T. Elfving, Numer. Math. 35, 1–12 (1980; Zbl 0416.65031)], 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 [M. Arioli et al., SIAM J. Sci. Comput. 16, No. 6, 1478–1511 (1995; Zbl 0839.65037)] 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
65F05 Direct numerical methods for linear systems and matrix inversion
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices

Software:

MUMPS; PaToH
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15-41. · Zbl 0992.65018
[2] M. Arioli, I. Duff, and D. Ruiz, Stopping criteria for iterative solvers, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 138-144. · Zbl 0749.65023
[3] M. Arioli, I. S. Duff, D. Ruiz, and M. Sadkane, Block Lanczos techniques for accelerating the block cimmino method, SIAM J. Sci. Comput., 16 (1995), pp. 1478-1511. · Zbl 0839.65037
[4] A. Björck, Iterative refinement of linear least squares solutions I, BIT, 7 (1967), pp. 257-278. · Zbl 0159.20404
[5] A. Buttari, Fine-grained multithreading for the multifrontal qr factorization of sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. C323-C345. · Zbl 1362.65031
[6] S. L. Campbell and C. D. Meyer, Generalized Inverses of Linear Transformations, SIAM, Philadelphia, 2009. · Zbl 1158.15301
[7] Ü. Çatalyürek and C. Aykanat, Patoh (partitioning tool for hypergraphs), in Encyclopedia of Parallel Computing, Springer, New York, 2011, pp. 1479-1487.
[8] L. Drummond, I. S. Duff, R. Guivarch, D. Ruiz, and M. Zenadi, Partitioning strategies for the block cimmino algorithm, J. Engrg. Math., 93 (2015), pp. 21-39. · Zbl 1360.65100
[9] I. S. Duff, R. Guivarch, D. Ruiz, and M. Zenadi, The augmented block Cimmino distributed method, SIAM J. Sci. and Comput., 37 (2015), pp. A1248-A1269. · Zbl 1318.65016
[10] I. S. Duff and J. K. Reid, The multifrontal solution of unsymmetric sets of linear equations, SIAM J. Sci. Stat. Comput., 5 (1984), pp. 633-641. · Zbl 0557.65017
[11] T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35 (1980), pp. 1-12. · Zbl 0416.65031
[12] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2012.
[13] X. S. Li, Superlu: Sparse direct solver and preconditioner, in Proceedings of the 13th DOE ACTS Collection Workshop, 2004.
[14] W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6 (1964), pp. 405-409. · Zbl 0133.08603
[15] C. Popa, Projection Algorithms-Classical Results and Developments: Applications to Image Reconstruction, LAP Lambert Academic Publishing, 2012.
[16] D. Ruiz, A Scaling Algorithm to Equilibrate Both Rows and Columns Norms in Matrices, Technical report, CM-P00040415, 2001.
[17] F. S. Torun, M. Manguoglu, and C. Aykanat, A novel partitioning method for accelerating the block Cimmino algorithm, SIAM J. Sci. Comput., 40 (2018), pp. C827-C850. · Zbl 1404.65018
[18] M. Zenadi, The Solution of Large Sparse Linear Systems on Parallel Computers Using a Hybrid Implementation of the Block Cimmino Method, Ph.D. thesis, Institut National Polytechnique de Toulouse (INP Toulouse), 2013.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.