Multi-level adaptive solutions to boundary-value problems

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 <italic>n</italic> discrete equations in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> operations (40<italic>n</italic> 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 "<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal infinity"> <mml:semantics> <mml:mi mathvariant="normal">∞</mml:mi> <mml:annotation encoding="application/x-tex">\infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-order" approximations and low <italic>n</italic>, 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.