Integration of barotropic vorticity equation over spherical geodesic grid using multilevel adaptive wavelet collocation method

In this paper, we present the multilevel adaptive wavelet collocation method for solving non-divergent barotropic vorticity equation over spherical geodesic grid. This method is based on multi-dimensional second generation wavelet over a spherical geodesic grid. The method is more useful in capturing, identifying, and analyzing local structure [1] than any other traditional methods (i.e. finite difference, spectral method), because those methods are either full or partial miss important phenomena such as trends, breakdown points, discontinuities in higher derivatives of the solution. Wavelet decomposition is used for interpolation and adaptive grid refinement on different levels.     

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     

Wavelet optimized finite difference method using interpolating wavelets for self-adjoint singularly perturbed problems

We design a wavelet optimized finite difference (WOFD) scheme for solving self-adjoint singularly perturbed boundary value problems. The method is based on an interpolating wavelet transform using polynomial interpolation on dyadic grids. Small dissipation of the solution is captured significantly using an adaptive grid. The adaptive feature is performed automatically by thresholding the wavelet coefficients. Numerical examples have been solved and compared with non-standard finite difference schemes in [J.M.S. Lubuma, K.C. Patidar, Uniformly convergent non-standard finite difference methods for self-adjoint singular perturbation problems, J. Comput. Appl. Math. 191 (2006) 228–238]. The proposed method outperforms the non-standard finite difference for studying singular perturbation problems for small dissipations (very small ) and effective grid generation. Therefore, the proposed method is better for studying the more challenging cases of singularly perturbed problems.     

High-order adaptive finite element-singly implicit Runge-Kutta methods for parabolic differential equations

We describe an adaptive mesh refinement finite element method-of-lines procedure for solving one-dimensional parabolic partial differential equations. Solutions are calculated using Galerkin's method with a piecewise hierarchical polynomial basis in space and singly implicit Runge-Kutta (SIRK) methods in time. A modified SIRK formulation eliminates a linear systems solution that is required by the traditional SIRK formulation and leads to a new reduced-order interpolation formula. Stability and temporal error estimation techniques allow acceptance of approximate solutions at intermediate stages, yielding increased efficiency when solving partial differential equations. A priori energy estimates of the local discretization error are obtained for a nonlinear scalar problem. A posteriori estimates of local spatial discretization errors, obtained by order variation, are used with the a priori error estimates to control the adaptive mesh refinement strategy. Computational results suggest convergence of the a posteriori error estimate to the exact discretization error and verify the utility of the adaptive technique.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-90-0194; the U.S. Army Research Office under Contract Number DAAL 03-91-G-0215; by the National Science Foundation under Grant Number CDA-8805910; and by a grant from the Committee on Research, Tulane University.     

Bivariate interpolation based on univariate subdivision schemes

The paper presents a bivariate subdivision scheme interpolating data consisting of univariate functions along equidistant parallel lines by repeated refinements. This method can be applied to the construction of a surface passing through a given set of parametric curves. Following the methodology of polysplines and tension surfaces, we define a local interpolator of four consecutive univariate functions, from which we sample a univariate function at the mid-point. This refinement step is the basis to an extension of the 4-point subdivision scheme to our setting. The bivariate subdivision scheme can be reduced to a countable number of univariate, interpolatory, non-stationary subdivision schemes. Properties of the generated interpolant are derived, such as continuity, smoothness and approximation order.     

Fast and Robust Sixth Order Multigrid Computation for 3D Convection Diffusion Equation

We present a sixth-order explicit compact finite difference scheme to solve the three-dimensional (3D) convection-diffusion equation. We first use a multiscale multigrid method to solve the linear systems arising from a 19-point fourth-order discretization scheme to compute the fourth-order solutions on both a coarse grid and a fine grid. Then an operator-based interpolation scheme combined with an extrapolation technique is used to approximate the sixth-order accurate solution on the fine grid. Since the multigrid method using a standard point relaxation smoother may fail to achieve the optimal grid-independent convergence rate for solving convection-diffusion equations with a high Reynolds number, we implement the plane relaxation smoother in the multigrid solver to achieve better grid independency. Supporting numerical results are presented to demonstrate the efficiency and accuracy of the sixth-order compact (SOC) scheme, compared with the previously published fourth-order compact (FOC) scheme.     

A multiresolution finite volume scheme for two-dimensional hyperbolic conservation laws

In this paper, high-resolution finite volume schemes are combined with an adaptive mesh technique inspired by multiresolution analysis to improve the computational efficiency for two-dimensional hyperbolic conservation laws. The method is conservative. Moreover, it is stable which is proven numerically in this paper. The computational grid is dynamically adapted so that higher spatial resolution is automatically allocated to regions where strong gradients are observed. Using this proposed scheme, we compute several two-dimensional model problems and a compressive rate ranging from about 5–10 is observed in all simulations.     

Polynomial-based non-uniform interpolatory subdivision with features control

Starting from a well-known construction of polynomial-based interpolatory 4-point schemes, in this paper we present an original affine combination of quadratic polynomial samples that leads to a non-uniform 4-point scheme with edge parameters. This blending-type formulation is then further generalized to provide a powerful subdivision algorithm that combines the fairing curve of a non-uniform refinement with the advantages of a shape-controlled interpolation method and an arbitrary point insertion rule. The result is a non-uniform interpolatory 4-point scheme that is unique in combining a number of distinctive properties. In fact it generates visually-pleasing limit curves where special features ranging from cusps and flat edges to point/edge tension effects may be included without creating undesired undulations. Moreover such a scheme is capable of inserting new points at any positions of existing intervals, so that the most convenient parameter values may be chosen as well as the intervals for insertion.Such a fully flexible curve scheme is a fundamental step towards the construction of high-quality interpolatory subdivision surfaces with features control.     

On the behavior of attractors under finite difference approximation

We recall that the long-time behavior of the Kuramoto-Sivashinsky equation is the same as that of a certain finite system of ordinary differential equations. We show how a particular finite difference scheme approximating the Kuramoto-Sivashinsky may be viewed as a small C ¹ perturbation of this system for the grid spacing sufficiently small. As a consequence one may make deductions about how the global attractor and the flow on the attractor behaves under this approximation. For a sufficiently refined grid the long-time behavior of the solutions of the finite difference scheme is a function of the solutions at certain grid points, whose number and position remain fixed as the grid is refined. Though the results are worked out explicitly for the Kuramoto-Sivashinsky equation, the results extend to other infinite-dimensional dissipative systems.     

A high‐order finite difference discretization strategy based on extrapolation for convection diffusion equations

We propose a new high‐order finite difference discretization strategy, which is based on the Richardson extrapolation technique and an operator interpolation scheme, to solve convection diffusion equations. For a particular implementation, we solve a fine grid equation and a coarse grid equation by using a fourth‐order compact difference scheme. Then we combine the two approximate solutions and use the Richardson extrapolation to compute a sixth‐order accuracy coarse grid solution. A sixth‐order accuracy fine grid solution is obtained by interpolating the sixth‐order coarse grid solution using an operator interpolation scheme. Numerical results are presented to demonstrate the accuracy and efficacy of the proposed finite difference discretization strategy, compared to the sixth‐order combined compact difference (CCD) scheme, and the standard fourth‐order compact difference (FOC) scheme. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 18–32, 2004.     

Convergence of an adaptive semi-Lagrangian scheme for the Vlasov-Poisson system

An adaptive semi-Lagrangian scheme for solving the Cauchy problem associated to the periodic 1+1-dimensional Vlasov-Poisson system in the two- dimensional phase space is proposed and analyzed. A key feature of our method is the accurate evolution of the adaptive mesh from one time step to the next one, based on a rigorous analysis of the local regularity and how it gets transported by the numerical flow. The accuracy of the scheme is monitored by a prescribed tolerance parameter ε which represents the local interpolation error at each time step, in the L ^∞ metric. The numerical solutions are proved to converge in L ^∞ towards the exact ones as ε and Δt tend to zero provided the initial data is Lipschitz and has a finite total curvature, or in other words, that it belongs to . The rate of convergence is , which should be compared to the results of Besse who recently established in (SIAM J Numer Anal 42(1):350–382, 2004) similar rates for a uniform semi-Lagrangian scheme, but requiring that the initial data are in . Several numerical tests illustrate the effectiveness of our approach for generating the optimal adaptive discretizations.     

Error bounds for a convexity-preserving interpolation and its limit function

Error bounds between a nonlinear interpolation and the limit function of its associated subdivision scheme are estimated. The bounds can be evaluated without recursive subdivision. We show that this interpolation is convexity preserving, as its associated subdivision scheme. Finally, some numerical experiments are presented.     

A two-grid method for finite volume element approximations of second-order nonlinear hyperbolic equations

The two-grid method is studied for solving a two-dimensional second-order nonlinear hyperbolic equation using finite volume element method. The method is based on two different finite element spaces defined on one coarse grid with grid size H and one fine grid with grid size h, respectively. The nonsymmetric and nonlinear iterations are only executed on the coarse grid and the fine grid solution can be obtained in a single symmetric and linear step. It is proved that the coarse grid can be much coarser than the fine grid. A prior error estimate in the H¹-norm is proved to be O(h+H³|lnH|) for the two-grid semidiscrete finite volume element method. With these proposed techniques, solving such a large class of second-order nonlinear hyperbolic equations will not be much more difficult than solving one single linearized equation. Finally, a numerical example is presented to validate the usefulness and efficiency of the method.     

A second order finite difference error indicator for adaptive transonic flow computations

Summary. An adaptive finite element method for the calculation of transonic potential flows was developed. An error indicator based on first order finite differences of gradients is introduced as a local error estimator. It measures second order distributional derivatives. Estimates involving this error estimator, a residual and the error are given. The error estimator can be used as a criterion for mesh refinement. We also give some computational results. Received September 16, 1993 / Revised version received June 7, 1994     

Subdivision Schemes and Irregular Grids

The present paper deals with subdivision schemes associated with irregular grids. We first give a sufficient condition concerning the difference scheme to obtain convergence. This condition generalizes a necessary and sufficient condition for convergence known in the case of uniform and stationary schemes associated with a regular grid. Through this sufficient condition, convergence of a given subdivision scheme can be proved by comparison with another scheme. Indeed, when two schemes are equivalent in some sense, and when one satisfies the sufficient condition for convergence, the other also satisfies it and it therefore converges too. We also study the smoothness of the limit functions produced by a scheme which satisfies the sufficient condition. Finally, the results are applied to the study of Lagrange interpolating subdivision schemes of any degree, with respect to particular irregular grids.     

Error Analysis of Adaptive Finite Difference Methods Using Stretching Functions for Polar Coordinate Form of Poisson-Type Equation

Abstract

This article treats of adaptive finite difference methods for the Dirichlet boundary value problems of Poisson-type equations on a sector or a disk. It is assumed that the exact solutions have singular derivatives on a part or the whole of the boundary. Some stretching functions are used to generate nonuniform grid points. It is then shown that, under some assumptions, the adaptive finite difference solutions are convergent and the convergence can be accelerated by varying parameters in the stretching functions. Numerical examples are given to illustrate how the accuracy of numerical solutions depends on the parameters.     

基于四点插值细分小波的SAR图像去噪

针对SAR图像去噪过程中存在降低相干斑与保持有效细节这一矛盾,提出了一种基于四点插值细分小波的SAR图像去噪算法,该方法将小波和细分方法相融合,将四点插值细分规则应用到细分小波中,提出了图像去噪的新方法.该算法先用四点插值细分小波对原始图像进行分解,然后用Bayes自适应阈值及阈值函数对图像进行去噪,最后对去噪的小波系数进行重构,并通过等效视数、边缘保持指数等评价指标对去噪结果进行了评价.实验结果表明,算法的等效视数、边缘保持指数都有所提高,去噪效果得到了优化.     

A framework for polynomial preconditioners based on fast transforms II: PDE applications

The solution of systems of equations arising from systems of time-dependent partial differential equations (PDEs) is considered. Primarily, first-order PDEs are studied, but second-order derivatives are also accounted for. The discretization is performed using a general finite difference stencil in space and an implicit method in time. The systems of equations are solved by a preconditioned Krylov subspace method. The preconditioners exploit optimal and superoptimal approximations by low-degree polynomials in a normal basis matrix, associated with a fast trigonometric transform. Numerical experiments for high-order accurate discretizations are presented. The results show that preconditioners based on fast transforms yield efficient solution algorithms, even for large quotients between the time and space steps. Utilizing a spatial grid ratio less than one, the arithmetic work per grid point is bounded by a constant as the number of grid points increases. This research was supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the U.S. National Science Foundation under grant ASC-8958544.     

An iterative adaptive finite element method for elliptic eigenvalue problems

We consider the task of resolving accurately the n$n$th eigenpair of a generalized eigenproblem rooted in some elliptic partial differential equation (PDE), using an adaptive finite element method (FEM). Conventional adaptive FEM algorithms call a generalized eigensolver after each mesh refinement step. This is not practical in our situation since the generalized eigensolver needs to calculate n$n$ eigenpairs after each mesh refinement step, it can switch the order of eigenpairs, and for repeated eigenvalues it can return an arbitrary linear combination of eigenfunctions from the corresponding eigenspace. In order to circumvent these problems, we propose a novel adaptive algorithm that only calls a generalized eigensolver once at the beginning of the computation, and then employs an iterative method to pursue a selected eigenvalue–eigenfunction pair on a sequence of locally refined meshes. Both Picard’s and Newton’s variants of the iterative method are presented. The underlying partial differential equation (PDE) is discretized with higher-order finite elements (hp$hp$-FEM) but the algorithm also works for standard low-order FEM. The method is described and accompanied with theoretical analysis and numerical examples. Instructions on how to reproduce the results are provided.