Modulus‐based multigrid methods for linear complementarity problems

By employing modulus‐based matrix splitting iteration methods as smoothers, we establish modulus‐based multigrid methods for solving large sparse linear complementarity problems. The local Fourier analysis is used to quantitatively predict the asymptotic convergence factor of this class of multigrid methods. Numerical results indicate that the modulus‐based multigrid methods of the W‐cycle can achieve optimality in terms of both convergence factor and computing time, and their asymptotic convergence factors can be predicted perfectly by the local Fourier analysis of the corresponding modulus‐based two‐grid methods.     

Operator splitting methods for pricing American options under stochastic volatility

We consider the numerical pricing of American options under Heston’s stochastic volatility model. The price is given by a linear complementarity problem with a two-dimensional parabolic partial differential operator. We propose operator splitting methods for performing time stepping after a finite difference space discretization. The idea is to decouple the treatment of the early exercise constraint and the solution of the system of linear equations into separate fractional time steps. With this approach an efficient numerical method can be chosen for solving the system of linear equations in the first fractional step before making a simple update to satisfy the early exercise constraint. Our analysis suggests that the Crank–Nicolson method and the operator splitting method based on it have the same asymptotic order of accuracy. The numerical experiments show that the operator splitting methods have comparable discretization errors. They also demonstrate the efficiency of the operator splitting methods when a multigrid method is used for solving the systems of linear equations.     

Integrated fast and high‐accuracy computation of convection diffusion equations using multiscale multigrid method

We present an explicit sixth‐order compact finite difference scheme for fast high‐accuracy numerical solutions of the two‐dimensional convection diffusion equation with variable coefficients. The sixth‐order scheme is based on the well‐known fourth‐order compact (FOC) scheme, the Richardson extrapolation technique, and an operator interpolation scheme. For a particular implementation, we use multiscale multigrid method to compute the fourth‐order solutions on both the coarse grid and the fine grid. Then, an operator interpolation scheme combined with the Richardson extrapolation technique is used to compute a sixth‐order accurate fine grid solution. We compare the computed accuracy and the implementation cost of the new scheme with the standard nine‐point FOC scheme and Sun–Zhang's sixth‐order method. Two convection diffusion problems are solved numerically to validate our proposed sixth‐order scheme. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

A monotone conservative Eulerian–Lagrangian scheme for reaction‐diffusion‐convection equations modeling chemotaxis

A numerical method for convection dominated diffusion problems, that exploits the use of characteristics, is derived and analyzed. It is shown to preserve positivity of solutions and be locally mass conserving. Stability, consistency and order one convergence are verified. Because of the way in which it determines characteristic pre‐images of grid cells, the method can be easily implemented for 1‐, 2‐, or 3‐dimensional problems on rectangular grids.© 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

The combination of collocation,finite difference,and multigrid methods for solution of the two‐dimensional wave equation

In this article, we apply compact finite difference approximations of orders two and four for discretizing spatial derivatives of wave equation and collocation method for the time component. The resulting method is unconditionally stable and solves the wave equation with high accuracy. The solution is approximated by a polynomial at each grid point that its coefficients are determined by solving a linear system of equations. We employ the multigrid method for solving the resulted linear system. Multigrid method is an iterative method which has grid independently convergence and solves the linear system of equations in small amount of computer time. Numerical results show that the compact finite difference approximation of fourth order, collocation and multigrid methods produce a very efficient method for solving the wave equation. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

A multigrid upwind strategy for accelerating steady‐state computations of waves propagating with curvature‐dependent speeds

A multigrid strategy using upwind finite differencing is developed for accelerating the steady state computations of waves, [14] propagating with curvature‐dependent speeds. This will allow the rapid computation of a “burn table.” In a high explosive material, a burn table will allow the elimination of solving chemical reaction ODEs by feeding in source terms to the reactive flow equations for solution of the system of ignition of the high explosive material. Standard iterative methods show a quick reduction of the residual followed by a slow final convergence to the solution at high iterations. Such systems, including a nonlinear system such as this, are excellent choices for the use of multigrid methods to speed up convergence. Numerical steady‐state solutions to the eikonal equation on several test grids are conducted. Results are presented for these cases in 2D and a cubic grid in 3D using a Runge‐Kutta time iteration for the smoothing operator until steady state is reached. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 179–192, 2002; DOI 10.1002/num.1002     

Local Fourier analysis for multigrid with overlapping smoothers applied to systems of PDEs

Since their popularization in the late 1970s and early 1980s, multigrid methods have been a central tool in the numerical solution of the linear and nonlinear systems that arise from the discretization of many PDEs. In this paper, we present a local Fourier analysis (LFA, or local mode analysis) framework for analyzing the complementarity between relaxation and coarse‐grid correction within multigrid solvers for systems of PDEs. Important features of this analysis framework include the treatment of arbitrary finite‐element approximation subspaces, leading to discretizations with staggered grids, and overlapping multiplicative Schwarz smoothers. The resulting tools are demonstrated for the Stokes, curl–curl, and grad–div equations. Copyright © 2011 John Wiley & Sons, Ltd.     

非对称椭圆型变分问题的多重网格法

1.引言 多重网格法是求解椭圆型方程边值问题的一种有效的迭代解法,其特点是方法收敛速度与网格长度h无关,因此为达到具有相同精度的解只需O(N)次的运算量(N为离散后的线性方程组未知数个数).从而比一般的迭代法有效得多.现在这个方法已被广泛     

Mixed two‐grid finite difference methods for solving one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations

The aim of this paper is to propose mixed two‐grid finite difference methods to obtain the numerical solution of the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. The finite difference equations at all interior grid points form a large‐sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a family of finite difference methods for discretizing the spatial and time derivatives. The obtained system has been solved by two‐grid method, where the two‐grid method is used for solving the large‐sparse linear systems. Also, in the proposed method, the spectral radius with local Fourier analysis is calculated for different values of h and Δt. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. Copyright © 2016 John Wiley & Sons, Ltd.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

Accuracy,robustness and efficiency comparison in iterative computation of convection diffusion equation with boundary layers

Nine‐point fourth‐order compact finite difference scheme, central difference scheme, and upwind difference scheme are compared for solving the two‐dimensional convection diffusion equations with boundary layers. The domain is discretized with a stretched nonuniform grid. A grid transformation technique maps the nonuniform grid to a uniform one, on which the difference schemes are applied. A multigrid method and a multilevel preconditioning technique are used to solve the resulting sparse linear systems. We compare the accuracy of the computed solutions from different discretization schemes, and demonstrate the relative efficiency of each scheme. Comparisons of maximum absolute errors, iteration counts, CPU timings, and memory cost are made with respect to the two solution strategies. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 379–394, 2000     

Parallel coarse‐grid selection

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse‐grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse‐grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd.     

Consistency of iterative operator‐splitting methods: Theory and applications

In this article, we describe a different operator‐splitting method for decoupling complex equations with multidimensional and multiphysical processes for applications for porous media and phase‐transitions. We introduce different operator‐splitting methods with respect to their usability and applicability in computer codes. The error‐analysis for the iterative operator‐splitting methods is discussed. Numerical examples are presented. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

CASCADIC MULTIGRID METHODS FOR MORTAR WILSON FINITE ELEMENT METHODS ON PLANAR LINEAR ELASTICITY

Cascadic multigrid technique for mortar Wilson finite element method of homogeneous boundary value planar linear elasticity is described and analyzed. First the mortar Wilson finite element method for planar linear elasticity will be analyzed, and the error estimate under L2 and H1 norm is optimal. Then a cascadic multigrid method for the mortar finite element discrete problem is described. Suitable grid transfer operator and smoother are developed which lead to an optimal cascadic multigrid method. Finally, the computational results are presented.     

Multigrid for second‐order ADN elliptic systems

This paper theoretically examines a multigrid strategy for solving systems of elliptic partial differential equations (PDEs) introduced in the work of Lee. Unlike most multigrid solvers that are constructed directly from the whole system operator, this strategy builds the solver using a factorization of the system operator. This factorization is composed of an algebraic coupling term and a diagonal (decoupled) differential operator. Exploiting the factorization, this approach can produce decoupled systems on the coarse levels. The corresponding coarse‐grid operators are in fact the Galerkin variational coarsening of the diagonal differential operator. Thus, rather than performing delicate coarse‐grid selection and interpolation weight procedures on the original strongly coupled system as often done, these procedures are isolated to the diagonal differential operator. To establish the theoretical results, however, we assume that these systems of PDEs are elliptic in the Agmon–Douglis–Nirenberg (ADN) sense and apply the factorization and multigrid only to the principal part of the system of PDEs. Two‐grid error bounds are established for the iteration applied to the complete system of PDEs. Numerical results are presented to illustrate the effectiveness of this strategy and to expose factors that affect the convergence of the methods derived from this strategy.     

Analysis of a two‐level method for anisotropic diffusion equations on aligned and nonaligned grids

This paper is on the convergence analysis for two‐grid and multigrid methods for linear systems arising from conforming linear finite element discretization of the second‐order elliptic equations with anisotropic diffusion. The multigrid algorithm with a line smoother is known to behave well when the discretization grid is aligned with the anisotropic direction; however, this is not the case with a nonaligned grid. The analysis in this paper is mainly focused on two‐level algorithms. For aligned grids, a lower bound is given for a pointwise smoother, and this bound shows a deterioration in the convergence rate, whereas for ‘maximally’ nonaligned grids (with no edges in the triangulation parallel to the direction of the anisotropy), the pointwise smoother results in a robust convergence. With a specially designed block smoother, we show that, for both aligned and nonaligned grids, the convergence is uniform with respect to the anisotropy ratio and the mesh size in the energy norm. The analysis is complemented by numerical experiments that confirm the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.     

Modulus‐based matrix splitting iteration methods for linear complementarity problems

For the large sparse linear complementarity problems, by reformulating them as implicit fixed‐point equations based on splittings of the system matrices, we establish a class of modulus‐based matrix splitting iteration methods and prove their convergence when the system matrices are positive‐definite matrices and H₊‐matrices. These results naturally present convergence conditions for the symmetric positive‐definite matrices and the M‐matrices. Numerical results show that the modulus‐based relaxation methods are superior to the projected relaxation methods as well as the modified modulus method in computing efficiency. Copyright © 2009 John Wiley & Sons, Ltd.     

Stability of time‐splitting schemes for the Stokes problem with stabilized finite elements

The time‐dependent Stokes problem is solved using continuous, piecewise linear finite elements and a classical stabilization procedure. Four order‐one methods are proposed for the time discretization. The first one is nothing but the Euler backward scheme and requires a large linear system involving the velocity and pressure unknowns to be solved. The other three schemes allow velocity and pressure computations to be decoupled, namely the pressure‐matrix method, a method based on an inexact LU factorization, and an operator splitting method. Stability and condition number estimates are derived. Numerical experiments in two space dimensions confirm the theoretical predictions. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:632–656, 2001