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), 103134
MSC:
Primary 65N30; Secondary 65F10, 65W05
MathSciNet review:
842125
Fulltext 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 0205478
(34 #5305)
 [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
(88a:65123), http://dx.doi.org/10.1090/S00255718198608296130
 [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 0362944
(50 #15382)
 [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 0292316
(45 #1403)
 [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. 395426.
 [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. CS7830, 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 conjugategradient method for solving linear
systems, Proceedings of Symposia in Applied Mathematics. Vol. VI.
Numerical analysis, McGrawHill Book Company, Inc., New York, for the
American Mathematical Society, Providence, R. I., 1956,
pp. 83–102. MR 0084178
(18,824c)
 [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
(33 #1719)
 [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, AddisonWesley, 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 SpaceA Survey, Lecture Notes in Math., Vol. 394, SpringerVerlag, 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 0438732
(55 #11639)
 [19]
V. Thomée, Galerkin Finite Element Methods for Parabolic Problems, Lecture Notes in Math., Vol. 1054, SpringerVerlag, New York, 1984.
 [1]
 P. E. Bjørstad & O. B. Widlund, "Solving elliptic problems on regions partitioned into substructures," Elliptic Problem Solvers II (G. Birkhoff and A. Schoenstadt, eds.), Academic Press, New York, 1984, pp. 245256. 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 analogue of the first biharmonic boundary value problem," Numer. Math., v. 9, 1966, pp. 236249. MR 0205478 (34:5305)
 [4]
 J. H. Bramble, J. E. Pasciak & A. H. Schatz, "An iterative method for elliptic problems on regions partitioned into substructures," Math. Comp., v. 46, 1986, pp. 361369. MR 829613 (88a:65123)
 [5]
 B. L. Buzbee & F. W. Dorr, "The direct solution of the biharmonic equation on rectangular regions and the Poisson equation on irregular regions," SIAM J. Numer. Anal., v. 11, 1974, pp. 753763. MR 0362944 (50:15382)
 [6]
 B. L. Buzbee, F. W. Dorr, J. A. George & G. H. Golub, "The direct solution of the discrete Poisson equation on irregular regions," SIAM J. Numer. Anal., v. 8, 1971, pp. 722736. MR 0292316 (45:1403)
 [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. 395426.
 [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. CS7830, 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]
 M. R. Hestenes, The Conjugate Gradient Method for Solving Linear Systems, Proc. Sympos. Appl. Math., vol. 6, Amer. Math. Soc., McGrawHill, 1956, pp. 83102. MR 0084178 (18:824c)
 [13]
 S. G. Krein & Y. I. Petunin, "Scales of Banach spaces," Russian Math. Surveys, v. 21, 1966, pp. 85160. MR 0193499 (33:1719)
 [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, AddisonWesley, 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 SpaceA Survey, Lecture Notes in Math., Vol. 394, SpringerVerlag, New York, 1974.
 [18]
 P. 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., v. 19, 1977, pp. 490501. MR 0438732 (55:11639)
 [19]
 V. Thomée, Galerkin Finite Element Methods for Parabolic Problems, Lecture Notes in Math., Vol. 1054, SpringerVerlag, New York, 1984.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65N30,
65F10,
65W05
Retrieve articles in all journals
with MSC:
65N30,
65F10,
65W05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198608421253
PII:
S 00255718(1986)08421253
Article copyright:
© Copyright 1986
American Mathematical Society
