The construction of preconditioners for elliptic problems by substructuring. I

Authors:
J. H. Bramble, J. E. Pasciak and A. H. Schatz

Journal:
Math. Comp. **47** (1986), 103-134

MSC:
Primary 65N30; Secondary 65F10, 65W05

DOI:
https://doi.org/10.1090/S0025-5718-1986-0842125-3

MathSciNet review:
842125

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the problem of solving the algebraic system of equations which arise from the discretization of symmetric elliptic boundary value problems via finite element methods. A new class of preconditioners for these discrete systems is developed based on substructuring (also known as domain decomposition). The resulting preconditioned algorithms are well suited to emerging parallel computing architectures. The proposed methods are applicable to problems on general domains involving differential operators with rather general coefficients. A basic theory for the analysis of the condition number of the preconditioned system (which determines the iterative convergence rate of the algorithm) is given. Techniques for applying the theory and algorithms to problems with irregular geometry are discussed and the results of extensive numerical experiments are reported.

**[1]**Petter E. Bjørstad and Olof B. Widlund,*Solving elliptic problems on regions partitioned into substructures*, Elliptic problem solvers, II (Monterey, Calif., 1983) Academic Press, Orlando, FL, 1984, pp. 245–255. MR**764237****[2]**P. E. Bjørstad & O. B. Widlund, "Iterative methods for the solution of elliptic problems on regions partitioned into substructures." (Preprint.)**[3]**J. H. Bramble,*A second order finite difference analog of the first biharmonic boundary value problem*, Numer. Math.**9**(1966), 236–249. MR**205478**, https://doi.org/10.1007/BF02162087**[4]**J. H. Bramble, J. E. Pasciak, and A. H. Schatz,*An iterative method for elliptic problems on regions partitioned into substructures*, Math. Comp.**46**(1986), no. 174, 361–369. MR**829613**, https://doi.org/10.1090/S0025-5718-1986-0829613-0**[5]**B. L. Buzbee and Fred W. Dorr,*The direct solution of the biharmonic equation on rectangular regions and the Poisson equation on irregular regions*, SIAM J. Numer. Anal.**11**(1974), 753–763. MR**362944**, https://doi.org/10.1137/0711061**[6]**B. L. Buzbee, F. W. Dorr, J. A. George, and G. H. Golub,*The direct solution of the discrete Poisson equation on irregular regions*, SIAM J. Numer. Anal.**8**(1971), 722–736. MR**292316**, https://doi.org/10.1137/0708066**[7]**Q. V. Dihn, R. Glowinski & J. Périaux, "Solving elliptic problems by domain decomposition methods,"*Elliptic Problem Solvers II*(G. Birkhoff and A. Schoenstadt, eds.), Academic Press, New York, 1984, pp. 395-426.**[8]**S. C. Eisenstat, M. C. Gursky, M. H. Schultz & A. H. Sherman,*Yale Sparse Matrix Package, I. The Symmetric Codes*, Dept. of Computer Science Report No. 112, Yale University.**[9]**A. George & J. W. H. Llu,*User Guide for SPARSPAK*, Dept. of Computer Science Report No. CS-78-30, Waterloo University.**[10]**G. H. Golub & D. Meyers, "The use of preconditioning over irregular regions,"*Proc. Sixth Internat. Conf. on Computing Methods in Science and Engineering*. (Preprint.)**[11]**P. Grisvard,*Elliptic Problems in Non Smooth Domains*, Pitman, Boston, 1985.**[12]**Magnus R. Hestenes,*The conjugate-gradient method for solving linear systems*, Proceedings of Symposia in Applied Mathematics. Vol. VI. Numerical analysis, McGraw-Hill Book Company, Inc., New York, for the American Mathematical Society, Providence, R. I., 1956, pp. 83–102. MR**0084178****[13]**S. G. Kreĭn and Ju. I. Petunin,*Scales of Banach spaces*, Uspehi Mat. Nauk**21**(1966), no. 2 (128), 89–168 (Russian). MR**0193499****[14]**J. L. Lions & E. Magenes,*Problèmes aux Limites non Homogènes et Applications*, Dunod, Paris, 1968.**[15]**D. G. Luenberger,*Introduction to Linear and Nonlinear Programming*, Addison-Wesley, Reading, Mass., 1973.**[16]**J. Nečas,*Les Méthodes Directes en Théorie des Équations Elliptiques*, Academia, Prague, 1967.**[17]**W. M. Patterson, 3RD,*Iterative Methods for the Solution of a Linear Operator Equation in Hubert Space--A Survey*, Lecture Notes in Math., Vol. 394, Springer-Verlag, New York, 1974.**[18]**Paul N. Swarztrauber,*The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson’s equation on a rectangle*, SIAM Rev.**19**(1977), no. 3, 490–501. MR**438732**, https://doi.org/10.1137/1019071**[19]**V. Thomée,*Galerkin Finite Element Methods for Parabolic Problems*, Lecture Notes in Math., Vol. 1054, Springer-Verlag, New York, 1984.

Retrieve articles in *Mathematics of Computation*
with MSC:
65N30,
65F10,
65W05

Retrieve articles in all journals with MSC: 65N30, 65F10, 65W05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1986-0842125-3

Article copyright:
© Copyright 1986
American Mathematical Society