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.     

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.     

Multigrid and multilevel methods for quadratic spline collocation

Multigrid methods are developed and analyzed for quadratic spline collocation equations arising from the discretization of one-dimensional second-order differential equations. The rate of convergence of the two-grid method integrated with a damped Richardson relaxation scheme as smoother is shown to be faster than 1/2, independently of the step-size. The additive multilevel versions of the algorithms are also analyzed. The development of quadratic spline collocation multigrid methods is extended to two-dimensional elliptic partial differential equations. Multigrid methods for quadratic spline collocation methods are not straightforward: because the basis functions used with quadratic spline collocation are not nodal basis functions, the design of efficient restriction and extension operators is nontrivial. Experimental results, with V-cycle and full multigrid, indicate that suitably chosen multigrid iteration is a very efficient solver for the quadratic spline collocation equations. Supported by Communications and Information Technology Ontario (CITO), Canada. Supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Thirteen ways to estimate global error

Summary Various techniques that have been proposed for estimating the accumulated discretization error in the numerical solution of differential equations, particularly ordinary differential equations, are classified, described, and compared. For most of the schemes either an outline of an error analysis is given which explains why the scheme works or a weakness of the scheme is illustrated.This research is partially supported by NSF Grant No. MCS-8107046     

The splitting finite-difference time-domain methods for Maxwell's equations in two dimensions

In this paper, we consider splitting methods for Maxwell's equations in two dimensions. A new kind of splitting finite-difference time-domain methods on a staggered grid is developed. The corresponding schemes consist of only two stages for each time step, which are very simple in computation. The rigorous analysis of the schemes is given. By the energy method, it is proved that the scheme is unconditionally stable and convergent for the problems with perfectly conducting boundary conditions. Numerical dispersion analysis and numerical experiments are presented to show the efficient performance of the proposed methods. Furthermore, the methods are also applied to solve a scattering problem successfully.     

Operator-splitting methods in respect of eigenvalue problems for nonlinear equations and applications for Burgers equations

In this article we consider iterative operator-splitting methods for nonlinear differential equations with respect to their eigenvalues. The main focus of the proposed idea is the fixed-point iterative scheme that linearizes our underlying equations. On the basis of the approximated eigenvalues of such linearized systems we choose the order of the operators for our iterative splitting scheme. The convergence properties of such a mixed method are studied and demonstrated. We confirm with numerical applications the effectiveness of the proposed scheme in comparison with the standard operator-splitting methods by providing improved results and convergence rates. We apply our results to deposition processes.     

Sparse grids for boundary integral equations

Summary. The potential of sparse grid discretizations for solving boundary integral equations is studied for the screen problem on a square in . Theoretical and numerical results on approximation rates, preconditioning, adaptivity and compression for piecewise constant and linear sparse grid spaces are obtained. Received March 17, 1998 / Revised version received September 10, 1998     

High performance parallel numerical methods for Volterra equations with weakly singular kernels

Non-stationary discrete time waveform relaxation methods for Abel systems of Volterra integral equations using fractional linear multistep formulae are introduced. Fully parallel discrete waveform relaxation methods having an optimal convergence rate are constructed. A significant expression of the error is proved, which allows us to estimate the number of iterations needed to satisfy a prescribed tolerance and allows us to identify the problems where the optimal methods offer the best performance. The numerical experiments confirm the theoretical expectations.     

A stabilized semi-implicit Galerkin scheme for Navier-Stokes equations

By introducing a time relaxation term for the time derivative of higher frequency components, we proposed a stabilized semi-implicit Galerkin scheme for evolutionary Navier-Stokes equations in this paper. Analysis shows that such a scheme has weaker stability conditions than that of a classical semi-implicit Galerkin scheme and, when a suitable relaxation parameter σ is chosen, it generates an approximate solution with the same accuracy as the classical one. That means the proposed scheme might use a larger time step to generate a bounded approximate solution. Thus it is more suitable for long time simulations.     

Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems

Two classes of incomplete factorization preconditioners are considered for nonsymmetric linear systems arising from second order finite difference discretizations of non-self-adjoint elliptic partial differential equations. Analytic and experimental results show that relaxed incomplete factorization methods exhibit numerical instabilities of the type observed with other incomplete factorizations, and the effects of instability are characterized in terms of the relaxation parameter. Several stabilized incomplete factorizations are introduced that are designed to avoid numerically unstable computations. In experiments with two-dimensional problems with variable coefficients and on nonuniform meshes, the stabilized methods are shown to be much more robust than standard incomplete factorizations.The work presented in this paper was supported by the National Science Foundation under grants DMS-8607478, CCR-8818340, and ASC-8958544, and by the U.S. Army Research Office under grant DAAL-0389-K-0016.     

Nonlinear Galerkin methods and mixed finite elements: two-grid algorithms for the Navier-Stokes equations

Summary. A nonlinear Galerkin method using mixed finite elements is presented for the two-dimensional incompressible Navier-Stokes equations. The scheme is based on two finite element spaces and for the approximation of the velocity, defined respectively on one coarse grid with grid size and one fine grid with grid size and one finite element space for the approximation of the pressure. Nonlinearity and time dependence are both treated on the coarse space. We prove that the difference between the new nonlinear Galerkin method and the standard Galerkin solution is of the order of $H^2$, both in velocity ( and pressure norm). We also discuss a penalized version of our algorithm which enjoys similar properties. Received October 5, 1993 / Revised version received November 29, 1993     

Relaxation approximation to bed-load sediment transport

In this work we propose and apply a numerical method based on finite volume relaxation approximation for computing the bed-load sediment transport in shallow water flows, in one and two space dimensions. The water flow is modeled by the well-known nonlinear shallow water equations which are coupled with a bed updating equation. Using a relaxation approximation, the nonlinear set of equations (and for two different formulations) is transformed to a semilinear diagonalizable problem with linear characteristic variables. A second order MUSCL-TVD method is used for the advection stage while an implicit–explicit Runge–Kutta scheme solves the relaxation stage. The main advantages of this approach are that neither Riemann problem solvers nor nonlinear iterations are required during the solution process. For the two different formulations, the applicability and effectiveness of the presented scheme is verified by comparing numerical results obtained for several benchmark test problems.     

Reducible quadrature methods for Volterra integral equations of the first kind

Quadrature rules, generated by linear multistep methods for ordinary differential equations, are employed to construct a wide class of direct quadrature methods for the numerical solution of first kind Volterra integral equations. Our class covers several methods previously considered in the literature. The methods are convergent provided that both the first and second characteristic polynomial of the linear multistep method satisfy the root condition. Furthermore, the stability behaviour for fixed positive values of the stepsizeh is analyzed, and it turns out that convergence implies (fixedh) stability. The subclass formed by the backward differentiation methods up to order six is discussed and illustrated with numerical examples.     

Dirac delta methods for Helmholtz transmission problems

In this paper we use a boundary integral method with single layer potentials to solve a class of Helmholtz transmission problems in the plane. We propose and analyze a novel and very simple quadrature method to solve numerically the equivalent system of integral equations which provides an approximation of the solution of the original problem with linear convergence (quadratic in some special cases). Furthermore, we also investigate a modified quadrature approximation based on the ideas of qualocation methods. This new scheme is again extremely simple to implement and has order three in weak norms.      

Qualocation methods for elliptic boundary integral equations

Summary. The qualocation methods developed in this paper, with spline trial and test spaces, are suitable for classes of boundary integral equations with convolutional principal part, on smooth closed curves in the plane. Some of the methods are suitable for all strongly elliptic equations; that is, for equations in which the even symbol part of the operator dominates. Other methods are suitable when the odd part dominates. Received December 27, 1996 / Revised version received April 14, 1997     

Domain imbedding methods for the Stokes equations

Summary We study direct and iterative domain imbedding methods for the Stokes equations on certain non-rectangular domains in two space dimensions. We analyze a continuous analog of numerical domain imbedding for bounded, smooth domains, and give an example of a simple numerical algorithm suggested by the continuous analysis. This algorithms is applicable for simply connected domains which can be covered by rectangular grids, with uniformly spaced grid lines in at least one coordinate direction. We also discuss a related FFT-based fast solver for Stokes problems with physical boundary conditions on rectangles, and present some numerical results.     

Backward differentiation type formulas for Volterra integral equations of the second kind

Summary Numerical integration formulas are discussed which are obtained by differentiation of the Volterra integral equation and by applying backward differentiation formulas to the resulting integro-differential equation. In particular, the stability of the method is investigated for a class of convolution kernels. The accuracy and stability behaviour of the method proposed in this paper is compared with that of (i) a block-implicit Runge-Kutta scheme, and (ii) the scheme obtained by applying directly a quadrature rule which is reducible to the backward differentiation formulas. The present method is particularly advantageous in the case of stiff Volterra integral equations.     

Multi-parameter error resolution for the collocation method of Volterra integral equations

In this paper, a multi-parameter error resolution technique is introduced and applied to the collocation method for Volterra integral equations. By using this technique, an approximation of higher accuracy is obtained by using a multi-processor in parallel. Additionally, a correction scheme for approximation of higher accuracy and a global superconvergence result are presented.     

Superconvergence of collocation methods for a class of weakly singular Volterra integral equations

We discuss the application of spline collocation methods to a certain class of weakly singular Volterra integral equations. It will be shown that, by a special choice of the collocation parameters, superconvergence properties can be obtained if the exact solution satisfies certain conditions. This is in contrast with the theory of collocation methods for Abel type equations. Several numerical examples are given which illustrate the theoretical results.     

Continuous-time accelerated block successive overrelaxation methods for time-dependent Stokes equations

In order to solve the time-dependent Stokes equation, we follow the “Method of Lines” to obtain structured linear constant-coefficient differential–algebraic equations (DAEs). By taking advantage of the structure, we propose a class of waveform relaxation methods, called continuous-time accelerated block SOR (CABSOR) methods, for solving the obtained DAEs. The new methods are theoretically analyzed. The theory is applied to a two-dimensional time-dependent Stokes equation and verified by numerical experiments.