Multilevel adaptive solutions to boundaryvalue problems
Author:
Achi Brandt
Journal:
Math. Comp. 31 (1977), 333390
MSC:
Primary 65N05
MathSciNet review:
0431719
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The boundaryvalue problem is discretized on several grids (or finiteelement spaces) of widely different mesh sizes. Interactions between these levels enable us (i) to solve the possibly nonlinear system of n discrete equations in operations (40n additions and shifts for Poisson problems); (ii) to conveniently adapt the discretization (the local mesh size, local order of approximation, etc.) to the evolving solution in a nearly optimal way, obtaining "order" approximations and low n, even when singularities are present. General theoretical analysis of the numerical process. Numerical experiments with linear and nonlinear, elliptic and mixedtype (transonic flow) problemsconfirm theoretical predictions. Similar techniques for initialvalue problems are briefly discussed.
 [1]
N. S. BAKHVALOV (BAHVALOV), "Convergence of a relaxation method with natural constraints on an elliptic operator," Ž. Vyčisl. Mat. i Mat. Fiz., v. 6, 1966, pp. 861885. (Russian) MR 35 #6378.
 [2]
A. BRANDT, "Multilevel adaptive technique (MLAT) for fast numerical solution to boundary value problems," Proc. 3rd Internat. Conf. on Numerical Methods in Fluid Mechanics (Paris, 1972), Lecture Notes in Physics, vol. 18, SpringerVerlag, Berlin and New York, 1973, pp. 8289.
 [3]
A. BRANDT, MultiLevel Adaptive Techniques, IBM Research Report RC6026, 1976.
 [4]
A. BRANDT, "Elliptic difference operators and smoothing rates." (In preparation.)
 [5]
R.
P. Fedorenko, A relaxation method of solution of elliptic
difference equations, Ž. Vyčisl. Mat. i Mat. Fiz.
1 (1961), 922–927 (Russian). MR 0137314
(25 #766)
 [6]
R.
P. Fedorenko, On the speed of convergence of an iteration
process, Ž. Vyčisl. Mat. i Mat. Fiz. 4
(1964), 559–564 (Russian). MR 0182163
(31 #6386)
 [7]
James
M. Hyman, Mesh refinement and local inversion of elliptic partial
differential equations, J. Computational Phys. 23
(1977), no. 2, 124–134. MR 0431722
(55 #4717)
 [8]
Antony
Jameson, Numerical solution of nonlinear partial differential
equations of mixed type, Sympos. (SYNSPADE), Univ. Maryland, College
Park, Md., 1975) Academic Press, New York, 1976, pp. 275–320.
MR
0468255 (57 #8093)
 [9]
E. M. MURMAN, "Analysis of embedded shock waves calculated by relaxation methods," Proc. AIAA Conf. on Computational Fluid Dynamics (Palm Springs, Calif., 1973), AIAA, 1973, pp. 2740.
 [10]
Carl
E. Pearson, On nonlinear ordinary differential equations of
boundary layer type., J. Math. and Phys. 47 (1968),
351–358. MR 0237107
(38 #5400)
 [11]
Y. SHIFTAN, MultiGrid Method for Solving Elliptic Difference Equations, M. Sc. Thesis, Weizmann Institute of Science, Rehovot, Israel, 1972. (Hebrew)
 [12]
J. C. SOUTH, JR. & A. BRANDT, Application of a MultiLevel Grid Method to Transonic Flow Calculations, ICASE Report 768, NASA Langley Research Center, Hampton, Virginia, 1976.
 [13]
R.
V. Southwell, Relaxation Methods in Engineering Science. A treatise
on approximate computation, Oxford Engineering Science Series, Oxford
University Press, New York, 1940. MR 0005425
(3,152d)
 [14]
R.
V. Southwell, Relaxation Methods in Theoretical Physics,
Oxford, at the Clarendon Press, 1946. MR 0018983
(8,355f)
 [15]
Eduard
Stiefel, Über einige Methoden der Relaxationsrechnung, Z.
Angew. Math. Physik 3 (1952), 1–33 (German). MR 0047409
(13,874c)
 [16]
F.
de la Vallee Poussin, An accelerated relaxation algorithm for
iterative solution of elliptic equations, SIAM J. Numer. Anal.
5 (1968), 340–351. MR 0233524
(38 #1845)
 [17]
Eugene
L. Wachspress, Iterative solution of elliptic systems, and
applications to the neutron diffusion equations of reactor physics,
PrenticeHall Inc., Englewood Cliffs, N.J., 1966. MR 0234649
(38 #2965)
 [18]
E. L. WACHSPRESS, "Variational acceleration of linear iteration," Proc. Army Workshop Watervliet Arsenal, Albany, New York, 1974.
 [19]
S.
V. Ahamed, Accelerated convergence of numerical solution of linear
and nonlinear vector field problems, Comput. J. 8
(1965), 73–76. MR 0181114
(31 #5343)
 [20]
I. BABUŠKA, W. RHEINBOLDT & C. MESZTENYI, SelfAdaptive Refinements in the Finite Element Method, Technical Report TR375, Computer Science Department, University of Maryland, 1975.
 [21]
P. O. FREDERICKSON, Fast Approximate Inversion of Large Sparse Linear Systems, Math. Report 775, Lakehead University, Ontario, Canada, 1975.
 [22]
M. LENTINI & V. PEREYRA, An Adaptive Finite Difference Solver for Nonlinear Two Point Boundary Problems with Mild Boundary Layers, Report STANCS75530, Computer Science Department, Stanford University, Stanford, California, 1975.
 [23]
R.
A. Nicolaides, On multiple grid and related techniques for solving
discrete elliptic systems, J. Computational Phys. 19
(1975), no. 4, 418–431. MR 0413541
(54 #1655)
 [24]
A.
Settari and K.
Aziz, A generalization of the additive correction methods for the
iterative solution of matrix equations, SIAM J. Numer. Anal.
10 (1973), 506–521. MR 0331816
(48 #10148)
 [25]
R. V. SOUTHWELL, "Stress calculation in frameworks by the method of systematic relaxation of constraints. I, II," Proc. Roy. Soc. London Ser. A, v. 151, 1935, pp. 5695.
 [26]
Achi
Brandt, Multilevel adaptive techniques (MLAT) for partial
differential equations: ideas and software, Mathematical software, III
(Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977),
Academic Press, New York, 1977, pp. 277–318. Publ. Math. Res.
Center, No. 39. MR 0474858
(57 #14489)
 [27]
C.
William Gear, Numerical initial value problems in ordinary
differential equations, PrenticeHall Inc., Englewood Cliffs, N.J.,
1971. MR
0315898 (47 #4447)
 [28]
W. HACKBUSH, Ein Iteratives Verfahren zur Schnellen Auflösung Elliptischer Randwertprobleme, Math. Inst., Universität zu Köln, Report 7612 (November 1976). A short English version: "A fast method for solving Poisson's equation in a general region," Numerische Behandlung von Differentialgleichungen (R. Bulirsch, R. D. Grigorieff & J. Schröder, Editors), Lecture Notes in Math., SpringerVerlag, Berlin and New York, 1977.
 [29]
R.
A. Nicolaides, On the 𝑙² convergence of
an algorithm for solving finite element equations, Math. Comp. 31 (1977), no. 140, 892–906. MR 0488722
(58 #8239), http://dx.doi.org/10.1090/S00255718197704887223
 [30]
Robert
D. Richtmyer and K.
W. Morton, Difference methods for initialvalue problems,
Second edition. Interscience Tracts in Pure and Applied Mathematics, No. 4,
Interscience Publishers John Wiley & Sons, Inc., New
YorkLondonSydney, 1967. MR 0220455
(36 #3515)
 [1]
 N. S. BAKHVALOV (BAHVALOV), "Convergence of a relaxation method with natural constraints on an elliptic operator," Ž. Vyčisl. Mat. i Mat. Fiz., v. 6, 1966, pp. 861885. (Russian) MR 35 #6378.
 [2]
 A. BRANDT, "Multilevel adaptive technique (MLAT) for fast numerical solution to boundary value problems," Proc. 3rd Internat. Conf. on Numerical Methods in Fluid Mechanics (Paris, 1972), Lecture Notes in Physics, vol. 18, SpringerVerlag, Berlin and New York, 1973, pp. 8289.
 [3]
 A. BRANDT, MultiLevel Adaptive Techniques, IBM Research Report RC6026, 1976.
 [4]
 A. BRANDT, "Elliptic difference operators and smoothing rates." (In preparation.)
 [5]
 R. P. FEDORENKO, "A relaxation method for solving elliptic difference equations," Ž. Vyčisl. Mat. i Mat. Fiz., v. 1, 1961, pp. 922927. (Russian) MR 25 #766. MR 0137314 (25:766)
 [6]
 R. P. FEDORENKO, "On the speed of convergence of an iteration process," Ž. Vyčisl. Mat. i Mat. Fiz., v. 4, 1964, pp. 559564. (Russian) MR 31 #6386. MR 0182163 (31:6386)
 [7]
 J. M. HYMAN, "Mesh refinement and local inversion of elliptic partial differential equations," J. Computational Phys., v. 23, 1977, pp. 124134. MR 0431722 (55:4717)
 [8]
 A. JAMESON, "Numerical solution of nonlinear partial differential equations of mixed type," Numerical Solution of Partial Differential Equations, III (SYNSPADE 1975) (Proc. Sympos., Univ. of Maryland, College Park, Md., 1975), Academic Press, New York. MR 0468255 (57:8093)
 [9]
 E. M. MURMAN, "Analysis of embedded shock waves calculated by relaxation methods," Proc. AIAA Conf. on Computational Fluid Dynamics (Palm Springs, Calif., 1973), AIAA, 1973, pp. 2740.
 [10]
 C. E. PEARSON, "On nonlinear ordinary differential equations of boundary layer type," J. Math. Phys., v. 47, 1968, pp. 351358. MR 38 #5400. MR 0237107 (38:5400)
 [11]
 Y. SHIFTAN, MultiGrid Method for Solving Elliptic Difference Equations, M. Sc. Thesis, Weizmann Institute of Science, Rehovot, Israel, 1972. (Hebrew)
 [12]
 J. C. SOUTH, JR. & A. BRANDT, Application of a MultiLevel Grid Method to Transonic Flow Calculations, ICASE Report 768, NASA Langley Research Center, Hampton, Virginia, 1976.
 [13]
 R. V. SOUTHWELL, Relaxation Methods in Engineering Science, Oxford Univ. Press, New York, 1940. MR 3, 152. MR 0005425 (3:152d)
 [14]
 R. V. SOUTHWELL, Relaxation Methods in Theoretical Physics, Clarendon Press, Oxford, 1946. MR 8, 355. MR 0018983 (8:355f)
 [15]
 E. L. STIEFEL, "Über einige Methoden der Relaxationsrechnung," Z. Angew. Math. Phys., v. 3, 1952, pp. 133. MR 13, 874; erratum, 13, p. 1140. MR 0047409 (13:874c)
 [16]
 F. de la VALLÉE POUSSIN, "An accelerated relaxation algorithm for iterative solution of elliptic equations," SIAM J. Numer. Anal., v. 5, 1968, pp. 340351. MR 38 #1845. MR 0233524 (38:1845)
 [17]
 E. L. WACHSPRESS, Iterative Solution of Elliptic Systems, and Applications to the Neutron Diffusion Equations of Reactor Physics, PrenticeHall, Englewood Cliffs, N. J., 1966. MR 38 #2965. MR 0234649 (38:2965)
 [18]
 E. L. WACHSPRESS, "Variational acceleration of linear iteration," Proc. Army Workshop Watervliet Arsenal, Albany, New York, 1974.
 [19]
 S. V. AHAMED, "Accelerated convergence of numerical solution of linear and nonlinear vector field problems," Comput. J., v. 8, 1965, pp. 7376. MR 31 #5343. MR 0181114 (31:5343)
 [20]
 I. BABUŠKA, W. RHEINBOLDT & C. MESZTENYI, SelfAdaptive Refinements in the Finite Element Method, Technical Report TR375, Computer Science Department, University of Maryland, 1975.
 [21]
 P. O. FREDERICKSON, Fast Approximate Inversion of Large Sparse Linear Systems, Math. Report 775, Lakehead University, Ontario, Canada, 1975.
 [22]
 M. LENTINI & V. PEREYRA, An Adaptive Finite Difference Solver for Nonlinear Two Point Boundary Problems with Mild Boundary Layers, Report STANCS75530, Computer Science Department, Stanford University, Stanford, California, 1975.
 [23]
 R. A. NICOLAIDES, "On multiple grid and related techniques for solving discrete elliptic systems," J. Computational Phys., v. 19, 1975, pp. 418431. MR 0413541 (54:1655)
 [24]
 A. SETTARI & K. AZIZ, "A generalization of the additive correction methods for the iterative solution of matrix equations," SIAM J. Numer. Anal., v. 10, 1973, pp. 506521. MR 48 #10148. MR 0331816 (48:10148)
 [25]
 R. V. SOUTHWELL, "Stress calculation in frameworks by the method of systematic relaxation of constraints. I, II," Proc. Roy. Soc. London Ser. A, v. 151, 1935, pp. 5695.
 [26]
 A. BRANDT, "Multilevel adaptive solutions to partial differential equationsideas and software," Proc. Sympos. on Math. Software (Math. Research Center, Univ. of Wisconsin, March 1977), Academic Press. (To appear.) MR 0474858 (57:14489)
 [27]
 C. WILLIAM GEAR, Numerical Initial Value Problems in Ordinary Differential Equations, PrenticeHall, Englewood Cliffs, N. J., 1971. MR 47 #4447. MR 0315898 (47:4447)
 [28]
 W. HACKBUSH, Ein Iteratives Verfahren zur Schnellen Auflösung Elliptischer Randwertprobleme, Math. Inst., Universität zu Köln, Report 7612 (November 1976). A short English version: "A fast method for solving Poisson's equation in a general region," Numerische Behandlung von Differentialgleichungen (R. Bulirsch, R. D. Grigorieff & J. Schröder, Editors), Lecture Notes in Math., SpringerVerlag, Berlin and New York, 1977.
 [29]
 R. A. NICOLAIDES, "On the convergence of an algorithm for solving finite element equations," Math. Comp. (To appear.) MR 0488722 (58:8239)
 [30]
 R. D. RICHTMYER & K. W. MORTON, Difference Methods for InitialValue Problems, 2nd ed., Interscience, New York, 1967. MR 36 #3515. MR 0220455 (36:3515)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65N05
Retrieve articles in all journals
with MSC:
65N05
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819770431719X
PII:
S 00255718(1977)0431719X
Article copyright:
© Copyright 1977 American Mathematical Society
