Multi-level adaptive solutions to boundary-value problems

Mathematics of Computation - Tập 31 Số 138 - Trang 333-390
Achi Brandt

Tóm tắt

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 O ( n ) O(n) 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 " \infty -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.

Từ khóa


Tài liệu tham khảo

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.

A. BRANDT, "Multi-level 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, Springer-Verlag, Berlin and New York, 1973, pp. 82-89.

A. BRANDT, Multi-Level Adaptive Techniques, IBM Research Report RC6026, 1976.

A. BRANDT, "Elliptic difference operators and smoothing rates." (In preparation.)

Fedorenko, R. P., 1961, A relaxation method of solution of elliptic difference equations, \v{Z}. Vy\v{c}isl. Mat i Mat. Fiz., 1, 922

Fedorenko, R. P., 1964, On the speed of convergence of an iteration process, \v{Z}. Vy\v{c}isl. Mat i Mat. Fiz., 4, 559

Hyman, James M., 1977, Mesh refinement and local inversion of elliptic partial differential equations, J. Comput. Phys., 23, 124, 10.1016/0021-9991(77)90116-4

Jameson, Antony, 1976, Numerical solution of nonlinear partial differential equations of mixed type, 275

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.

Pearson, Carl E., 1968, On non-linear ordinary differential equations of boundary layer type, J. Math. and Phys., 47, 351, 10.1002/sapm1968471351

Y. SHIFTAN, Multi-Grid Method for Solving Elliptic Difference Equations, M. Sc. Thesis, Weizmann Institute of Science, Rehovot, Israel, 1972. (Hebrew)

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.

Southwell, R. V., 1940, Relaxation Methods in Engineering Science. A treatise on approximate computation

Southwell, R. V., 1946, Relaxation Methods in Theoretical Physics

Stiefel, Eduard, 1952, Über einige Methoden der Relaxationsrechnung, Z. Angew. Math. Phys., 3, 1, 10.1007/bf02080981

de la Vallee Poussin, F., 1968, An accelerated relaxation algorithm for iterative solution of elliptic equations, SIAM J. Numer. Anal., 5, 340, 10.1137/0705029

Wachspress, Eugene L., 1966, Iterative solution of elliptic systems, and applications to the neutron diffusion equations of reactor physics

E. L. WACHSPRESS, "Variational acceleration of linear iteration," Proc. Army Workshop Watervliet Arsenal, Albany, New York, 1974.

Ahamed, S. V., 1965, Accelerated convergence of numerical solution of linear and non-linear vector field problems, Comput. J., 8, 73, 10.1093/comjnl/8.1.73

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.

P. O. FREDERICKSON, Fast Approximate Inversion of Large Sparse Linear Systems, Math. Report 7-75, Lakehead University, Ontario, Canada, 1975.

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.

Nicolaides, R. A., 1975, On multiple grid and related techniques for solving discrete elliptic systems, J. Comput. Phys., 19, 418, 10.1016/0021-9991(75)90072-8

Settari, A., 1973, A generalization of the additive correction methods for the iterative solution of matrix equations, SIAM J. Numer. Anal., 10, 506, 10.1137/0710046

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.

Brandt, Achi, 1977, Multi-level adaptive techniques (MLAT) for partial differential equations: ideas and software, 277

Gear, C. William, 1971, Numerical initial value problems in ordinary differential equations

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.

Nicolaides, R. A., 1977, On the 𝑙² convergence of an algorithm for solving finite element equations, Math. Comp., 31, 892, 10.2307/2006120

Richtmyer, Robert D., 1967, Difference methods for initial-value problems, 2