Abstract
Many parallel iterative algorithms for solving symmetric, positive definite problems proceed by solving in each iteration, a number of independent systems on subspaces. The convergence of such methods is determined by the spectrum of the sums of orthogonal projections on those subspaces, while the convergence of a related sequential method is determined by the spectrum of the product of complementary projections. We study spectral properties of sums of orthogonal projections and in the case of two projections, characterize the spectrum of the sum completely in terms of the spectrum of the product.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. E. Bank and T. F. Dupont,Analysis of a two-level scheme for solving finite element equations, Tech. Report CNA-159, Center for Numerical Analysis, University of Texas at Austin, 1980.
P. E. Bjørstad,Multiplicative and Additive Schwarz Methods: Convergence in the 2 domain case, inDomain Decomposition Methods, T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds., Philadelphia, 1989, SIAM.
D. Braess,The contraction number of a multigrid method for solving the Poisson equation, Numerische Mathematik, 37 (1981), pp. 387–404.
T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds.,Domain Decomposition Methods for Partial Differential Equations II, Philadelphia, 1989, SIAM.
C. C. Douglas and J. Mandel,The domain reduction method: High way reduction in three dimensions and convergence with inexact solvers, inMultigrid Methods, J. Mandel, S. F. McCormick, J. J. E. Dendy, C. Farhat, G. Lonsdale, S. V. Parter, J. W. Ruge, and K. Stüben, eds., Philadelphia, in print, SIAM.
C. C. Douglas and W. L. Miranker,Constructive interference in parallel algorithms, SIAM J. Numer. Anal., 25 (1988), pp. 376–398.
C. C. Douglas and B. F. Smith,Using symmetries and antisymmetries to analyze a parallel multigrid algorithm: the elliptic boundary value problem case, tech. report, IBM, 1987. Submitted to SIAM J. Num. Anal.
M. Dryja,An additive Schwarz algorithm for two- and three-dimensional finite element elliptic problems, inDomain Decomposition Methods, T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds., Philadelphia, 1989, SIAM.
M. Dryja and O. B. Widlund,An additive variant of the Schwarz alternating method for the case of many subregions, Tech. Report 339, also Ultracomputer Note 131, Department of Computer Science, Courant Institute, 1987.
On the optimality of an additive iterative refinement method, inMultigrid Methods, J. Mandel, S. McCormick, J. J. E. Dendy, C. Farhat, G. Lonsdale, S. V. Parter, J. W. Ruge, and K. Stüben, eds., Philadelphia, 1989, SIAM.
id.,Some domain decomposition algorithms foe elliptic problems, Tech. Report 438; also Ultracomputer Note 155, Department of Computer Science, Courant Institute, 1989. To appear in the proceedings of the Conference on Iterative Methods for Large Linear Systems held in Austin, Texas, October 1988, to celebrate the Sixty-fifth Brithday of David M. Young, Jr., Academic Press, Orlando, Florida, 1989.
R. Glowinski, G. H. Golub, G. A. Meurant, and J. Périaux, eds.,Domain Decomposition Methods for Partial Differential Equations, Philadelphia, 1988, SIAM.
G. H. Golub and C. F. Van Loan,Matrix Computations, Johns Hopkins Univ. Press, 1989. Second Edition.
W. Hackbusch,A new approach to robust multi-grid solvers ICIAM '87, Philadelphia, 1988, SIAM, pp. 114–126.
P. L. Lions,On the Schwarz alternating method. I., inFirst International Symposium on Domain Decomposition Methods for Partial Differential Equations, R. Glowinski, G. H. Golub, G. A. Meurant, and J. Périaux, eds., Philadelphia, 1988, SIAM.
On the Schwarz alternating method. II., inDomain Decomposition Methods, T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds., Philadelphia, 1989, SIAM.
J. Mandel and S. McCormick,Iterative solution of elliptic equations with refinement: The model multi-level case, inDomain Decomposition Methods, T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds., Philadelphia, 1989, SIAM.
Iterative solution of elliptic equations with refinement: The two-level case, inDomain Decomposition Methods, T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds., Philadelphia, 1989, SIAM.
A. M. Matsokin and S. V. Nepomnyaschikh,A Schwarz alternating method in a subspace, Soviet Mathematics, 29 (10) (1985), pp. 78–84.
H. A. Schwarz,Gesammelte Mathematische Abhandlungen, vol. 2, Springer, Berlin, 1890, pp. 133–143. First published in Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich, volume 15, 1870, pp. 272–286.
Author information
Authors and Affiliations
Additional information
This work was supported in part by the Norwegian Research Council for Science and the Humanities under grant D.01.08.054 and by The Royal Norwegian Council for Scientific and Industrial Research under grant IT2.28.28484; also supported in part by the Air Force Office of Scientific Research under grant AFOSR-86-0126 and by the National Science Foundation under grant DMS-8704169.
Rights and permissions
About this article
Cite this article
Bjørstad, P.E., Mandel, J. On the spectra of sums of orthogonal projections with applications to parallel computing. BIT 31, 76–88 (1991). https://doi.org/10.1007/BF01952785
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01952785