Abstract This paper proposes efficient and accurate adaptive two-grid (ATG) finite element algorithms for linear and nonlinear partial differential equations (PDEs). The core methodology utilizes solutions from the $k$-th level adaptive meshes to derive solutions for the $(k+1)$-th level, which are constructed via adaptive element bisections. These algorithms effectively transform non-symmetric positive definite (non-SPD) PDEs into symmetric positive definite (SPD) problems and nonlinear PDEs into linear ones. The ATG approach offers significant advantages: it bypasses the need for complex non-symmetric or nonlinear solvers on fine meshes, maintains low degrees of freedom (d.o.f.), and minimizes interpolation errors. Furthermore, the paper establishes residue-type a posteriori error estimators, proving their reliability and efficiency even under low regularity conditions. Theoretical convergence is established for bisection-based refinements, and numerical experiments validate that ATG algorithms outperform standard adaptive and static two-grid methods.
1. Introduction
Numerical analysis in the context of partial differential equations (PDEs) often involves a compromise between computational efficiency and solution accuracy. Solving nonlinear or non-symmetric systems is traditionally resource-intensive, requiring expensive iterative solvers like Newton’s method on high-resolution meshes. While "Two-Grid" methods (solving on a coarse mesh $H$ to linearize a fine mesh $h$) and "Adaptive" methods (refining meshes locally based on error estimators) have individually addressed these costs, their integration has remained a challenge. This paper introduces the Adaptive Two-Grid (ATG) framework, which synchronizes the linearization process with the adaptive evolution of the mesh.
2. The ATG Methodology
The ATG algorithm departs from static mesh pairs by using a sequence of evolving adaptive meshes. The transition from level $k$ to level $k+1$ serves two purposes: increasing spatial resolution and providing the basis for linearization or symmetrization.
2.1 Linearization and Symmetrization
For nonlinear PDEs, the algorithm solves the full nonlinear system only on the current adaptive mesh (level $k$). This solution is then used to define a simplified linear problem for the subsequent, more refined mesh (level $k+1$). Similarly, for non-symmetric problems, the level $k$ solution is utilized to "symmetrize" the level $k+1$ problem. This ensures that the bulk of the computational work is performed on symmetric positive definite (SPD) systems, which are compatible with highly efficient solvers like the Conjugate Gradient method.
2.2 Adaptive Refinement and Error Estimation
The refinement process is guided by residue-type a posteriori error estimators. These estimators act as local indicators, identifying specific mesh elements that require bisection to reduce error. A significant theoretical contribution of this work is the establishment of an upper bound for oscillation terms. Unlike standard analyses that treat these as higher-order terms (h.o.t.), this paper accounts for the low regularity often found in numerical solutions, ensuring the estimator remains efficient even when the solution is not perfectly smooth.
3. Theoretical Rigor
The paper provides a robust mathematical foundation for the ATG framework, focusing on three pillars:
- Reliability: The error estimator provides a guaranteed upper bound on the actual error.
- Efficiency: The estimator is not overly pessimistic, ensuring that refinements are only made where necessary.
- Convergence: The authors prove that when bisection is used for mesh refinement, the numerical error strictly converges to zero.
4. Numerical Results and Discussion
The ATG algorithms were validated against several benchmark problems, including semi-linear PDEs and problems with sharp gradients (e.g., tanh profiles mimicking Allen-Cahn equations).
4.1 Efficiency Gains
The numerical experiments demonstrated massive reductions in computational overhead. In one test case, achieving a specific accuracy level with a uniform grid would have required over 10 billion degrees of freedom (DoF). In contrast, the ATG algorithm achieved the same accuracy with fewer than 240,000 DoF.
4.2 Solver Performance
Algorithm 4.1 proved significantly faster than standard adaptive finite element methods (AFEM). By restricting nonlinear iterations to the coarsest initial mesh and using linear solvers for all subsequent adaptive steps, the ATG approach avoids the cumulative cost of nested iterations on fine grids. The $H^1$ semi-norm error was observed to decay at the optimal rate relative to the DoF, confirming theoretical predictions.
5. Conclusion and Future Work
The Adaptive Two-Grid finite element algorithm represents a powerful tool for solving complex PDEs "on a budget." By leveraging the adaptive process to handle linearization, it achieves high precision with minimal degrees of freedom.
However, some constraints remain. As noted in Remark 4.7, the initial mesh must be sufficiently refined to ensure that the linearization captures the underlying physics accurately. Future research may extend this framework to more complex systems, such as the Navier-Stokes equations for fluid dynamics or time-harmonic Maxwell equations, where the computational savings of the ATG approach could be even more transformative.
Summary updated