A “multigrid” extension of theFFT for the numerical inversion of Fourier and Laplace Transforms

An algorithm for accurate numerical inversion of slowly convergent Fourier and Laplace Transforms is studied. It makes use of several equidistant grids with the same number of points, covering different symmetric intervals of the time and frequency axes. Typically, the number of operations per computed function value is about twice as large as for an ordinary FFT. The distribution of points is, however, for many applications much more adequate because, globally, the union of the grids is an approximately equidistant point set on a logarithmic scale.Dedicated to Gene H. Golub on the occasion of his 60'th birthday     

An implementation of a discretization method for semi-infinite programming

For linear semi-infinite programming problems a discretization method is presented. A first coarse grid is successively refined in such a way that the solution on the foregoing grids can be used on the one hand as starting points for the subsequent grids and on the other hand to considerably reduce the number of constraints which have to be considered in the subsequent problems. This enables an efficient treatment of large problems with moderate storage requirements. A numerically stable Simplex-algorithm is used to solve the LP-subproblems. Numerical examples from bivariate Chebyshev approximation are presented.     

An active set strategy to generate quadrilateral grids

We consider the problem of the generation of quadrilateral grids on planar domains. This problem is numerically solved by a two phases method: an iterative procedure based on the well-known variational approach, and an active set procedure to obtain unfolded quadrilaterals. This second phase is performed only when it is really necessary, in fact the first phase alone gives satisfactory results on a large number of domains. This two phases approach provides a robust method with low computational cost. Numerical experiments show that this method is able to generate unfolded grids also on complex domains.     

Stability and accuracy of adapted finite element methods for singularly perturbed problems

The stability and accuracy of a standard finite element method (FEM) and a new streamline diffusion finite element method (SDFEM) are studied in this paper for a one dimensional singularly perturbed connvection-diffusion problem discretized on arbitrary grids. Both schemes are proven to produce stable and accurate approximations provided that the underlying grid is properly adapted to capture the singularity (often in the form of boundary layers) of the solution. Surprisingly the accuracy of the standard FEM is shown to depend crucially on the uniformity of the grid away from the singularity. In other words, the accuracy of the adapted approximation is very sensitive to the perturbation of grid points in the region where the solution is smooth but, in contrast, it is robust with respect to perturbation of properly adapted grid inside the boundary layer. Motivated by this discovery, a new SDFEM is developed based on a special choice of the stabilization bubble function. The new method is shown to have an optimal maximum norm stability and approximation property in the sense that where u _N is the SDFEM approximation in linear finite element space V ^N of the exact solution u. Finally several optimal convergence results for the standard FEM and the new SDFEM are obtained and an open question about the optimal choice of the monitor function for the moving grid method is answered. This work was supported in part by NSF DMS-0209497 and NSF DMS-0215392 and the Changjiang Professorship through Peking University.     

Stability estimates based on numerical ranges with an application to a spectral method

This paper is concerned with the stability of numerical processes for solving initial value problems. We present a stability result which is related to a well-known theorem by von Neumann, but the requirements to be satisfied are less severe and easier to verify.As an illustration we consider a simple convection-diffusion equation. For the spatial discretization we use a spectral collocation method (based on so-called Legendre-Gauss-Lobatto points). We show that the fully discretized numerical process is stable, provided that the temporal step size is bounded by a constant depending only on the convection-diffusion equation, the number of collocation points and the time-stepping method under consideration.This research has been supported by the Netherlands Organization for Scientific Research (N.W.O.).     

A numerical ODE solver that preserves the fixed points and their stability

In this paper, we provide a one-step predictor-corrector method for numerically solving first-order differential initial-value problems with two fixed points. The method preserves the stability behaviour of the fixed points, which results in an efficient integrator for this kind of problem. Some numerical examples are provided to show the good performance of the method.     

Numerical analysis of a multiscale finite element scheme for the resolution of the stationary Schrödinger equation

A numerical method for the resolution of the one-dimensional Schrödinger equation with open boundary conditions was presented in N. Ben Abdallah and O. Pinaud (Multiscale simulation of transport in an open quantum system: resonances and WKB interpolation. J. Comp. Phys. 213(1), 288–310 (2006)). The main attribute of this method is a significant reduction of the computational cost for a desired accuracy. It is based particularly on the derivation of WKB basis functions, better suited for the approximation of highly oscillating wave functions than the standard polynomial interpolation functions. The present paper is concerned with the numerical analysis of this method. Consistency and stability results are presented. An error estimate in terms of the mesh size and independent on the wavelength λ is established. This property illustrates the importance of this method, as multiwavelength grids can be chosen to get accurate results, reducing by this manner the simulation time.     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

A note on an implementation of a method for quadratic semi-infinite programming

For convex quadratic semi-infinite programming problems aFortran-package is described. A first coarse grid is successively refined in such a way that the solution on the foregoing grids can be used on the one hand as starting points for the subsequent grids and on the other hand to considerably reduce the number of constraints which have to be considered in the subsequent problems. This enables an efficient treatment of large problems with moderate storage requirements. Powell's (1983) numerically stable convex quadratic programming implementation is used to solve the QP-subproblems.     

Integration matrix based on arbitrary grids with a preconditioner for pseudospectral method

A matrix representation of integration for arbitrary grids is introduced. Suitable results are then obtained to be used along with differentiation matrix preconditioner to implement Pseudospectral method on integro-differential equations using arbitrary grids. Numerical examples are given to clarify the efficiency of the new method.     

Multirate Runge–Kutta schemes for advection equations

Explicit time integration methods can be employed to simulate a broad spectrum of physical phenomena. The wide range of scales encountered lead to the problem that the fastest cell of the simulation dictates the global time step. Multirate time integration methods can be employed to alter the time step locally so that slower components take longer and fewer time steps, resulting in a moderate to substantial reduction of the computational cost, depending on the scenario to simulate [S. Osher, R. Sanders, Numerical approximations to nonlinear conservation laws with locally varying time and space grids, Math. Comput. 41 (1983) 321–336; H. Tang, G. Warnecke, A class of high resolution schemes for hyperbolic conservation laws and convection-diffusion equations with varying time and pace grids, SIAM J. Sci. Comput. 26 (4) (2005) 1415–1431; E. Constantinescu, A. Sandu, Multirate timestepping methods for hyperbolic conservation laws, SIAM J. Sci. Comput. 33 (3) (2007) 239–278]. In air pollution modeling the advection part is usually integrated explicitly in time, where the time step is constrained by a locally varying Courant–Friedrichs–Lewy (CFL) number. Multirate schemes are a useful tool to decouple different physical regions so that this constraint becomes a local instead of a global restriction. Therefore it is of major interest to apply multirate schemes to the advection equation. We introduce a generic recursive multirate Runge–Kutta scheme that can be easily adapted to an arbitrary number of refinement levels. It preserves the linear invariants of the system and is of third order accuracy when applied to certain explicit Runge–Kutta methods as base method.     

Stability of multistep-methods on variable grids

Summary This paper is concerned with the stability of multistep methods for ordinary initial-value problems on grids with variable mesh-sizes. A necessary and sufficient condition for stability is given from which generalizations of recent results by Gear et al. and by Zlatev can be obtained as special cases. As an application the stability of the variable BDF-formulas is treated.     

A note on conjugate gradient convergence

Summary. The one-dimensional discrete Poisson equation on a uniform grid with points produces a linear system of equations with a symmetric, positive-definite coefficient matrix. Hence, the conjugate gradient method can be used, and standard analysis gives an upper bound of ) on the number of iterations required for convergence. This paper introduces a systematically defined set of solutions dependent on a parameter , and for several values of , presents exact analytic expressions for the number of steps ) needed to achieve accuracy . The asymptotic behavior of these expressions has the form )} as and )} as . In particular, two choices of corresponding to nonsmooth solutions give , i.e., iteration counts independent of ; this is in contrast to the standard bounds. The standard asymptotic convergence behavior, , is seen for a relatively smooth solution. Numerical examples illustrate and supplement the analysis. Received August 30, 1995 / Revised version received January 23, 1996     

The cascadic multigrid method for elliptic problems

Summary. The paper deals with certain adaptive multilevel methods at the confluence of nested multigrid methods and iterative methods based on the cascade principle of [10]. From the multigrid point of view, no correction cycles are needed; from the cascade principle view, a basic iteration method without any preconditioner is used at successive refinement levels. For a prescribed error tolerance on the final level, more iterations must be spent on coarser grids in order to allow for less iterations on finer grids. A first candidate of such a cascadic multigrid method was the recently suggested cascadic conjugate gradient method of [9], in short CCG method, whichused the CG method as basic iteration method on each level. In [18] it has been proven, that the CCG method is accurate with optimal complexity for elliptic problems in 2D and quasi-uniform triangulations. The present paper simplifies that theory and extends it to more general basic iteration methods like the traditional multigrid smoothers. Moreover, an adaptive control strategy for the number of iterations on successive refinement levels for possibly highly non-uniform grids is worked out on the basis of a posteriori estimates. Numerical tests confirm the efficiency and robustness of the cascadic multigrid method. Received November 12, 1994 / Revised version received October 12, 1995     

Local time stepping and discontinuous Galerkin methods for symmetric first order hyperbolic systems

We present a new non-conforming space-time mesh refinement method for the symmetric first order hyperbolic system. This method is based on the one hand on the use of a conservative higher order discontinuous Galerkin approximation for space discretization and a finite difference scheme in time, on the other hand on appropriate discrete transmission conditions between the grids. We use a discrete energy technique to drive the construction of the matching procedure between the grids and guarantee the stability of the method.     

On richardson extrapolation for finite difference methods on regular grids

Summary Difference solutions of partial differential equations can in certain cases be expanded by even powers of a discretization parameterh. If we haven solutions corresponding to different mesh widthsh ₁,...,h _n we can improve the accuracy by Richardson extrapolation and get a solution of order 2n, yet only on the intersection of all grids used, i.e. normally on the coarsest grid. To interpolate this high order solution with the same accuracy in points not belonging to all grids, we need 2n points in an interval of length (2n–1)h ₁.This drawback can be avoided by combining such an interpolation with the extrapolation byh. In this case the approximation depends only on grid points in an interval of length 3/2h ₁. The length of this interval is independent of the desired order.By combining this approach with the method of Kreiss, boundary conditions on curved boundaries can be discretized with a high order even on coarse grids.This paper is based on a lecture held at the 5th Sanmarinian University Session of the International Academy of Sciences San Marino, at San Marino, 1988-08-27-1988-09-05     

Global error estimation and control in linearly-implicit parallel two-step peer W-methods

The class of linearly-implicit parallel two-step peer W-methods has been designed recently for efficient numerical solutions of stiff ordinary differential equations. Those schemes allow for parallelism across the method, that is an important feature for implementation on modern computational devices. Most importantly, all stage values of those methods possess the same properties in terms of stability and accuracy of numerical integration. This property results in the fact that no order reduction occurs when they are applied to very stiff problems. In this paper, we develop parallel local and global error estimation schemes that allow the numerical solution to be computed for a user-supplied accuracy requirement in automatic mode. An algorithm of such global error control and other technical particulars are also discussed here. Numerical examples confirm efficiency of the presented error estimation and stepsize control algorithm on a number of test problems with known exact solutions, including nonstiff, stiff, very stiff and large-scale differential equations. A comparison with the well-known stiff solver RODAS is also shown.     

Convergence of higher order upwind finite volume schemes on unstructured grids for scalar conservation laws in several space dimensions

Summary. We prove convergence of a class of higher order upwind finite volume schemes on unstructured grids for scalar conservation laws in several space dimensions. The result is applied to the discontinuous Galerkin method due to Cockburn, Hou and Shu. Received April 15, 1993 / Revised version received March 13, 1995     

A variable step implicit block multistep method for solving first-order ODEs

A new four-point implicit block multistep method is developed for solving systems of first-order ordinary differential equations with variable step size. The method computes the numerical solution at four equally spaced points simultaneously. The stability of the proposed method is investigated. The Gauss-Seidel approach is used for the implementation of the proposed method in the PE(CE)^m mode. The method is presented in a simple form of Adams type and all coefficients are stored in the code in order to avoid the calculation of divided difference and integration coefficients. Numerical examples are given to illustrate the efficiency of the proposed method.     

An interpolation matched interface and boundary method for elliptic interface problems

An interpolation matched interface and boundary (IMIB) method with second-order accuracy is developed for elliptic interface problems on Cartesian grids, based on original MIB method proposed by Zhou et al. [Y. Zhou, G. Wei, On the fictious-domain and interpolation formulations of the matched interface and boundary method, J. Comput. Phys. 219 (2006) 228-246]. Explicit and symmetric finite difference formulas at irregular grid points are derived by virtue of the level set function. The difference scheme using IMIB method is shown to satisfy the discrete maximum principle for a certain class of problems. Rigorous error analyses are given for the IMIB method applied to one-dimensional (1D) problems with piecewise constant coefficients and two-dimensional (2D) problems with singular sources. Comparison functions are constructed to obtain a sharp error bound for 1D approximate solutions. Furthermore, we compare the ghost fluid method (GFM), immersed interface method (IIM), MIB and IMIB methods for 1D problems. Finally, numerical examples are provided to show the efficiency and robustness of the proposed method.