Multi-level adaptive solutions to boundary-value problems

Author:
Achi Brandt

Journal:
Math. Comp. **31** (1977), 333-390

MSC:
Primary 65N05

DOI:
https://doi.org/10.1090/S0025-5718-1977-0431719-X

MathSciNet review:
0431719

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The boundary-value problem is discretized on several grids (or finite-element 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 (40*n* 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 mixed-type (transonic flow) problems-confirm theoretical predictions. Similar techniques for initial-value 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. 861-885. (Russian) MR**35**#6378.**[2]**A. BRANDT, "Multi-level adaptive technique (MLAT) for fast numerical solution to boundary value problems,"*Proc.*3*rd Internat. Conf. on Numerical Methods in Fluid Mechanics*(Paris, 1972), Lecture Notes in Physics, vol. 18, Springer-Verlag, Berlin and New York, 1973, pp. 82-89.**[3]**A. BRANDT,*Multi-Level 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**137314****[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**182163****[7]**James M. Hyman,*Mesh refinement and local inversion of elliptic partial differential equations*, J. Comput. Phys.**23**(1977), no. 2, 124–134. MR**431722**, https://doi.org/10.1016/0021-9991(77)90116-4**[8]**Antony Jameson,*Numerical solution of nonlinear partial differential equations of mixed type*, Numerical solution of partial differential equations, III (Proc. Third Sympos. (SYNSPADE), Univ. Maryland, College Park, Md., 1975) Academic Press, New York, 1976, pp. 275–320. MR**0468255****[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. 27-40.**[10]**Carl E. Pearson,*On non-linear ordinary differential equations of boundary layer type*, J. Math. and Phys.**47**(1968), 351–358. MR**237107****[11]**Y. SHIFTAN,*Multi-Grid 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 Multi-Level Grid Method to Transonic Flow Calculations*, ICASE Report 76-8, 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****[14]**R. V. Southwell,*Relaxation Methods in Theoretical Physics*, Oxford, at the Clarendon Press, 1946. MR**0018983****[15]**Eduard Stiefel,*Über einige Methoden der Relaxationsrechnung*, Z. Angew. Math. Phys.**3**(1952), 1–33 (German). MR**47409**, https://doi.org/10.1007/bf02080981**[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**233524**, https://doi.org/10.1137/0705029**[17]**Eugene L. Wachspress,*Iterative solution of elliptic systems, and applications to the neutron diffusion equations of reactor physics*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR**0234649****[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 non-linear vector field problems*, Comput. J.**8**(1965), 73–76. MR**181114**, https://doi.org/10.1093/comjnl/8.1.73**[20]**I. BABUŠKA, W. RHEINBOLDT & C. MESZTENYI,*Self-Adaptive Refinements in the Finite Element Method*, Technical Report TR-375, Computer Science Department, University of Maryland, 1975.**[21]**P. O. FREDERICKSON,*Fast Approximate Inversion of Large Sparse Linear Systems*, Math. Report 7-75, 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 STAN-CS-75-530, Computer Science Department, Stanford University, Stanford, California, 1975.**[23]**R. A. Nicolaides,*On multiple grid and related techniques for solving discrete elliptic systems*, J. Comput. Phys.**19**(1975), no. 4, 418–431. MR**413541**, https://doi.org/10.1016/0021-9991(75)90072-8**[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**331816**, https://doi.org/10.1137/0710046**[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. 56-95.**[26]**Achi Brandt,*Multi-level 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****[27]**C. William Gear,*Numerical initial value problems in ordinary differential equations*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR**0315898****[28]**W. HACKBUSH,*Ein Iteratives Verfahren zur Schnellen Auflösung Elliptischer Randwertprobleme*, Math. Inst., Universität zu Köln, Report 76-12 (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., Springer-Verlag, 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**488722**, https://doi.org/10.1090/S0025-5718-1977-0488722-3**[30]**Robert D. Richtmyer and K. W. Morton,*Difference methods for initial-value problems*, Second edition. Interscience Tracts in Pure and Applied Mathematics, No. 4, Interscience Publishers John Wiley & Sons, Inc., New York-London-Sydney, 1967. MR**0220455**

Retrieve articles in *Mathematics of Computation*
with MSC:
65N05

Retrieve articles in all journals with MSC: 65N05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1977-0431719-X

Article copyright:
© Copyright 1977
American Mathematical Society