Reliable and efficient error control for an adaptive Galerkin-characteristic method for convection-dominated diffusion problems

An efficient and reliable a-posteriori error estimator is developed for a characteristic-Galerkin finite element method for time-dependent convection-dominated problems. An adaptive algorithm with variable time and space steps is proposed and studied. At each time step in this algorithm grid coarsening occurs solely at the final iteration of the adaptive procedure, meaning that only time and space refinement is allowed before the final iteration. It is proved that at each time step this adaptive algorithm is capable of reducing errors below a given tolerance in a finite number of iteration steps. Numerical results are presented to check the theoretical analysis.     

Grid structure impact in sparse point representation of derivatives

In the Sparse Point Representation (SPR) method the principle is to retain the function data indicated by significant interpolatory wavelet coefficients, which are defined as interpolation errors by means of an interpolating subdivision scheme. Typically, a SPR grid is coarse in smooth regions, and refined close to irregularities. Furthermore, the computation of partial derivatives of a function from the information of its SPR content is performed in two steps. The first one is a refinement procedure to extend the SPR by the inclusion of new interpolated point values in a security zone. Then, for points in the refined grid, such derivatives are approximated by uniform finite differences, using a step size proportional to each point local scale. If required neighboring stencils are not present in the grid, the corresponding missing point values are approximated from coarser scales using the interpolating subdivision scheme. Using the cubic interpolation subdivision scheme, we demonstrate that such adaptive finite differences can be formulated in terms of a collocation scheme based on the wavelet expansion associated to the SPR. For this purpose, we prove some results concerning the local behavior of such wavelet reconstruction operators, which stand for SPR grids having appropriate structures. This statement implies that the adaptive finite difference scheme and the one using the step size of the finest level produce the same result at SPR grid points. Consequently, in addition to the refinement strategy, our analysis indicates that some care must be taken concerning the grid structure, in order to keep the truncation error under a certain accuracy limit. Illustrating results are presented for 2D Maxwell’s equation numerical solutions.     

An adaptive homotopy approach for non-selfadjoint eigenvalue problems

This paper presents adaptive algorithms for eigenvalue problems associated with non-selfadjoint partial differential operators. The basis for the developed algorithms is a homotopy method which departs from a well-understood selfadjoint problem. Apart from the adaptive grid refinement, the progress of the homotopy as well as the solution of the iterative method are adapted to balance the contributions of the different error sources. The first algorithm balances the homotopy, discretization and approximation errors with respect to a fixed stepsize τ in the homotopy. The second algorithm combines the adaptive stepsize control for the homotopy with an adaptation in space that ensures an error below a fixed tolerance ε. The outcome of the analysis leads to the third algorithm which allows the complete adaptivity in space, homotopy stepsize as well as the iterative algebraic eigenvalue solver. All three algorithms are compared in numerical examples.     

Adaptively refined dynamic program for linear spline regression

The linear spline regression problem is to determine a piecewise linear function for estimating a set of given points while minimizing a given measure of misfit or error. This is a classical problem in computational statistics and operations research; dynamic programming was proposed as a solution technique more than 40 years ago by Bellman and Roth (J Am Stat Assoc 64:1079–1084, 1969). The algorithm requires a discretization of the solution space to define a grid of candidate breakpoints. This paper proposes an adaptive refinement scheme for the grid of candidate breakpoints in order to allow the dynamic programming method to scale for larger instances of the problem. We evaluate the quality of solutions found on small instances compared with optimal solutions determined by a novel integer programming formulation of the problem. We also consider a generalization of the linear spline regression problem to fit multiple curves that share breakpoint horizontal coordinates, and we extend our method to solve the generalized problem. Computational experiments verify that our nonuniform grid construction schemes are useful for computing high-quality solutions for both the single-curve and two-curve linear spline regression problem.     

An Adaptive Fast Interface Tracking Method

An adaptive numerical scheme is developed for the propagation of an interface in a velocity field based on the fast interface tracking method proposed in [2]. A multiresolution stategy to represent the interface instead of point values, allows local grid refinement while controlling the approximation error on the interface. For time integration, we use an explicit Runge-Kutta scheme of second-order with a multiscale time step, which takes longer time steps for finer spatial scales. The implementation of the algorithm uses a dynamic tree data structure to represent data in the computer memory. We briefly review first the main algorithm, describe the essential data structures, highlight the adaptive scheme, and illustrate the computational efficiency by some numerical examples.     

Anisotropic mesh refinement for finite element methods based on error reduction

In this paper, we propose an anisotropic adaptive refinement algorithm based on the finite element methods for the numerical solution of partial differential equations. In 2-D, for a given triangular grid and finite element approximating space V, we obtain information on location and direction of refinement by estimating the reduction of the error if a single degree of freedom is added to V. For our model problem the algorithm fits highly stretched triangles along an interior layer, reducing the number of degrees of freedom that a standard h-type isotropic refinement algorithm would use.     

Patch-adaptive multilevel iteration

Themultilevel adaptive iteration is an attempt to improve both the robustness and efficiency of iterative sparse system solvers. Unlike in most other iterative methods, the order of processing and sequence of operations is not determined a priori. The method consists of a relaxation scheme with an active set strategy and can be viewed as an efficient implementation of the Gauß-Southwell relaxation. With this strategy, computational work is focused on where it can efficiently improve the solution quality. To obtain full efficiency, the algorithm must be used on a multilevel structure. This algorithm is then closely related to multigrid or multilevel preconditioning algorithms, and can be shown to have asymptotically optimal convergence. In this paper the focus is on a variant that uses data structures with a locally uniform grid refinement. The resulting grid system consists of a collection of patches where each patch is a uniform rectangular grid and where adaptive refinement is accomplished by arranging the patches flexibly in space. This construction permits improved implementations that better exploit high performance computer designs. This will be demonstrated by numerical examples.     

A Sequential Least Squares Method for Elliptic Equations in Non-Divergence Form

We develop a new least squares method for solving the second-order elliptic equations in non-divergence form. Two least-squares-type functionals are proposed for solving the equation in two sequential steps. We first obtain a numerical approximation to the gradient in a piecewise irrotational polynomial space. Then together with the numerical gradient, we seek a numerical solution of the primitive variable in the continuous Lagrange finite element space. The variational setting naturally provides an a posteriori error which can be used in an adaptive refinement algorithm. The error estimates under the $L^2$ norm and the energy norm for both two unknowns are derived. By a series of numerical experiments, we verify the convergence rates and show the efficiency of the adaptive algorithm.     

Comparison of refinement criteria for structured adaptive mesh refinement

We have investigated and analyzed the grid convergence issues for an adaptive mesh refinement (AMR) code. We have found that the numerical results for the AMR grid may have a larger error than those for the unrefined uniform grid. After a detailed analysis, we have found that the numerical solution at the coarse-fine interface between different levels of the grid converges only in the first-order accuracy. Therefore, the error near the coarse-fine interface can quickly dominate the error in the other regions if the coarse-fine interface is active and not covered by the fine grid. We propose, implement, and compare several refinement criteria. Some of them can catch the large-error region near the coarse-fine interface and refine them with the fine grid.     

Adaptive sparse grid algorithms with applications to electromagnetic scattering under uncertainty

We discuss adaptive sparse grid algorithms for stochastic differential equations with a particular focus on applications to electromagnetic scattering by structures with holes of uncertain size, location, and quantity. Stochastic collocation (SC) methods are used in combination with an adaptive sparse grid approach based on nested Gauss-Patterson grids. As an error estimator we demonstrate how the nested structure allows an effective error estimation through Richardson extrapolation. This is shown to allow excellent error estimation and it also provides an efficient means by which to estimate the solution at the next level of the refinement. We introduce an adaptive approach for the computation of problems with discrete random variables and demonstrate its efficiency for scattering problems with a random number of holes. The results are compared with results based on Monte Carlo methods and with Stroud based integration, confirming the accuracy and efficiency of the proposed techniques.     

An a posteriori error estimator for anisotropic refinement

Summary. Besides an algorithm for local refinement, an a posteriori error estimator is the basic tool of every adaptive finite element method. Using information generated by such an error estimator the refinement of the grid is controlled. For 2nd order elliptic problems we present an error estimator for anisotropically refined grids, like -d cuboidal and 3-d prismatic grids, that gives correct information about the size of the error; additionally it generates information about the direction into which some element has to be refined to reduce the error in a proper way. Numerical examples are presented for 2-d rectangular and 3-d prismatic grids. Received March 15, 1994 / Revised version received June 3, 1994     

Numerical analysis of a continuous Galerkin method for damped sine-Gordon equation

In this article, we discuss the numerical solution for the two-dimensional (2-D) damped sine-Gordon equation by using a space–time continuous Galerkin method. This method allows variable time steps and space mesh structures and its discrete scheme has good stability which are necessary for adaptive computations on unstructured grids. Meanwhile, it can easily get the higher-order accuracy in both space and time directions. The existence and uniqueness to the numerical solution are strictly proved and a priori error estimate in maximum-norm is given without any space–time grid conditions attached. Also, we prove that if the mesh in each time level is generated in a reasonable way, we can get the optimal order of convergence in both temporal and spatial variables. Finally, the convergence rates are presented and analyzed by some numerical experiments to illustrate the validity of the scheme.     

Adaptive meshless refinement schemes for RBF-PUM collocation

In this paper we present an adaptive discretization technique for solving elliptic partial differential equations via a collocation radial basis function partition of unity method. In particular, we propose a new adaptive scheme based on the construction of an error indicator and a refinement algorithm, which used together turn out to be ad-hoc strategies within this framework. The performance of the adaptive meshless refinement scheme is assessed by numerical tests.     

Adaptive p-version of the finite element method for solving boundary value problems for ordinary second-order differential equations

We suggest an adaptive strategy for constructing a hierarchical basis for a p-version of the finite element method used to solve boundary value problems for second-order ordinary differential equations. The choice of the order of an element on each grid interval is based on estimates of the change, in the norm of C, of the approximate solution or the value of the functional to be minimized when increasing the degree of the basis function added on this interval. The results of numerical experiments estimating the method efficiency are given for sample problems whose solutions have singularities of the boundary layer type. We make a comparison with the p-version of the finite element method, which uses a uniform growth of the degree of the basis functions, and with the h-version, which uses uniform grid refinement along with an adaptive grid refinement and coarsening strategy.     

ADAPTIVITY IN SPACE AND TIME FOR MAGNETOQUASISTATICS

This paper addresses fully space-time adaptive magnetic field computations. We describe an adaptive Whitney finite element method for solving the magnetoquasistatic formulation of Maxwell＇s equations on unstructured 3D tetrahedral grids. Spatial mesh re- finement and coarsening are based on hierarchical error estimators especially designed for combining tetrahedral H（curl）-conforming edge elements in space with linearly implicit Rosenbrock methods in time. An embedding technique is applied to get efficiency in time through variable time steps. Finally, we present numerical results for the magnetic recording write head benchmark problem proposed by the Storage Research Consortium in Japan.     

Spatially adaptive sparse grids for high-dimensional data-driven problems

Sparse grids allow one to employ grid-based discretization methods in data-driven problems. We present an extension of the classical sparse grid approach that allows us to tackle high-dimensional problems by spatially adaptive refinement, modified ansatz functions, and efficient regularization techniques. The competitiveness of this method is shown for typical benchmark problems with up to 166 dimensions for classification in data mining, pointing out properties of sparse grids in this context. To gain insight into the adaptive refinement and to examine the scope for further improvements, the approximation of non-smooth indicator functions with adaptive sparse grids has been studied as a model problem. As an example for an improved adaptive grid refinement, we present results for an edge-detection strategy.     

Second-order finite element approximations and a posteriori error estimation for two-dimensional parabolic systems

Summary We discuss an adaptive local refinement finite element method of lines for solving vector systems of parabolic partial differential equations on two-dimensional rectangular regions. The partial differential system is discretized in space using a Galerkin approach with piecewise eight-node serendipity functions. An a posteriori estimate of the spatial discretization error of the finite element solution is obtained using piecewise fifth degree polynomials that vanish on the edges of the rectangular elements of a grid. Ordinary differential equations for the finite element solution and error estimate are integrated in time using software for stiff differential systems. The error estimate is used to control a local spatial mesh refinement procedure in an attempt to keep a global measure of the error within prescribed limits. Examples appraising the accuracy of the solution and error estimate and the computational efficiency of the procedure relative to one using bilinear finite elements are presented.Dedicated to Prof. Ivo Babuka on the occasion of his 60th birthdayThis research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0156 and the U.S. Army Research Office under Contract Number DAAL 03-86-K-0112     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

A Two-Grid Finite Element Approximation for Nonlinear Time Fractional Two-Term Mixed Sub-Diffusion and Diffusion Wave Equations

In this paper, we develop a two-grid method (TGM) based on the FEM for 2D nonlinear time fractional two-term mixed sub-diffusion and diffusion wave equations. A two-grid algorithm is proposed for solving the nonlinear system, which consists of two steps: a nonlinear FE system is solved on a coarse grid, then the linearized FE system is solved on the fine grid by Newton iteration based on the coarse solution. The fully discrete numerical approximation is analyzed, where the Galerkin finite element method for the space derivatives and the finite difference scheme for the time Caputo derivative with order $\alpha\in(1,2)$ and $\alpha_{1}\in(0,1)$. Numerical stability and optimal error estimate $O(h^{r+1}+H^{2r+2}+\tau^{\min\{3-\alpha,2-\alpha_{1}\}})$ in $L^{2}$-norm are presented for two-grid scheme, where $t,$ $H$ and $h$ are the time step size, coarse grid mesh size and fine grid mesh size, respectively. Finally, numerical experiments are provided to confirm our theoretical results and effectiveness of the proposed algorithm.     

An accurate a posteriori error estimator for the Steklov eigenvalue problem and its applications

In this paper, a type of accurate a posteriori error estimator is proposed for the Steklov eigenvalue problem based on the complementary approach, which provides an asymptotic exact estimate for the approximate eigenpair. Besides, we design a type of cascadic adaptive finite element method for the Steklov eigenvalue problem based on the proposed a posteriori error estimator. In this new cascadic adaptive scheme, instead of solving the Steklov eigenvalue problem in each adaptive space directly, we only need to do some smoothing steps for linearized boundary value problems on a series of adaptive spaces and solve some Steklov eigenvalue problems on a low dimensional space. Furthermore, the proposed a posteriori error estimator provides the way to refine mesh and control the number of smoothing steps for the cascadic adaptive method. Some numerical examples are presented to validate the efficiency of the algorithm in this paper.