×

Domain decomposition for parallel row projection algorithms. (English) Zbl 0738.65022

It is shown that for nonsymmetric matrices arising from finite differences or finite elements applied to partial differential equations a domain decomposition approach gives row projection methods and allows parallelism in computing orthogonal projections \(P_ iv=A_ i(A^ T_ iA_ i)^{-1}A^ T_ iv\). (\(A\) is partitioned into block rows \(A^ T_ i\)). Criteria for suitable row partitioning are discussed. Suitable row partitioning allows parallelism in the computation, creates subproblems that can be solved efficiently and gives numerically well behaved subproblems. The domain decomposition approach provides row partitionings that satisfy all of the criteria. Four test problems involving second order elliptic partial differential equations are computed and the results tabulated.
Reviewer: V.Burjan (Praha)

MSC:

65F10 Iterative numerical methods for linear systems
65Y05 Parallel numerical computation
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations
65N06 Finite difference methods for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs

Software:

LSODA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Björk, A.; Elfving, T., Accelerated projection methods for computing pseudo-inverse solutions of systems of linear equations, BIT, 19, 145-163 (1979)
[2] Bramley, R., Row projection methods for linear systems, CSRD Report 881 (1989), University of Illinois: University of Illinois Urbana, IL · Zbl 0752.65024
[3] Bramley, R.; Sameh, A., A robust parallel solver for block tridiagonal systems, Proceedings International Conference on Supercomputing (1988)
[4] R. Bramley and A. Sameh, Row projection methods for large nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. (submitted).; R. Bramley and A. Sameh, Row projection methods for large nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. (submitted). · Zbl 0752.65024
[5] Brown, P.; Hindmarsh, A., Reduced storage matrix methods for stiff ODE systems, J. Appl. Math. Comput. (1987), (submitted)
[6] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23, 444-466 (1981) · Zbl 0469.65037
[7] Eggermont, P.; Herman, G.; Lent, A., Iterative algorithms for large partitioned linear systems with applications to image reconstruction, Linear Algebra Appl., 40, 37-67 (1981) · Zbl 0466.65021
[8] Elman, H., Iterative methods for large, sparse, nonsymmetric systems of linear equations, Research Report 229 (1982), Yale University: Yale University New Haven, CT
[9] Elman, H.; Golub, G., Iterative methods for cyclically reduced non-self-adjoint linear systems, UMIACS-TR-88-87 (1988), University of Maryland: University of Maryland College Park, MD, CS-TR-2145 · Zbl 0699.65021
[10] Hanke, M.; Niethammer, W., On the acceleration of Kaczmarz’s method for inconsistent linear systems (1988), Institut für Praktische Mathematik, Universität Karlsruhe: Institut für Praktische Mathematik, Universität Karlsruhe Germany
[11] Herman, G., Image Reconstruction for Projections (1980), Academic Press: Academic Press New York
[12] Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Internat. Acad. Polonaise Sci. Lett. (Cracouie), 355-357 (1939), Class Sci. Math. Natur.: Seira A. Sci. Math. · JFM 63.0524.02
[13] Kamath, C., Solution of nonsymmetric systems of equations on a multiprocessor, CSRD Report 591 (1986), University of Illinois: University of Illinois Urbana, IL
[14] Kamath, C.; Sameh, A., A projection method for solving nonsymmetric linear systems on multiprocessors, Parallel Comput., 9, 291-312 (1988/1989) · Zbl 0668.65028
[15] Sherman, A., An empirical investigation of methods for nonsymmetric linear systems, (Schultz, H., Elliptic Problem Solvers (1981), Academic Press: Academic Press New York), 429-434
[16] Stewart, G., On the perturbation of pseudo-inverses, projections and linear least squares problems, SIAM Rev., 19, 634-662 (1977) · Zbl 0379.65021
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.