速度追踪问题中鞍点系统的新分裂迭代

 有限元离散一类速度追踪问题后得到具有鞍点结构的线性系统,针对该鞍点系统,本文提出了一种新的分裂迭代技术.证明了新的分裂迭代方法的无条件收敛性,详细分析了新的分裂预条件子对应的预处理矩阵的谱性质.数值结果验证了对于大范围的网格参数和正则参数,新的分裂预条件子在求解有限元离散速度追踪问题得到的鞍点系统时的可行性和有效性.     

A computationally efficient modification of mixed finite element methods for flow problems with full transmissivity tensors

The mixed finite element method for approximately solving flow equations in porous media has received a good deal of attention in the literature. The main idea is to solve for the head/pressure and fluid velocity (Darcy velocity) simultaneously to obtain a higher order approximation of the fluid velocity. In the case of a diagonal transmissivity tensor the algebraic equations resulting from the discretization can be reduced to a system of algebraic equations for the head/pressure variable alone. This reduction results in a smaller number of unknows to be solved for in an iterative method such as preconditioned conjugate gradient method. The fluid velocity is then obtained from an algebraic relationship. In the case of full transmissivity tensor, the algebraic reduction is more difficult. This paper investigates some algorithms resulting from the modification of the mixed finite element that take advantage of the mixed finite element method for the diagonal tensor case. The resulting schemes are more efficient implementations that maintain the same order of accuracy as the original schemes. © 1993 John Wiley & Sons, Inc.     

New Optimization Approach to Multiphase Flow

A new optimization formulation for simulating multiphase flow in porous media is introduced. A locally mass-conservative, mixed finite-element method is employed for the spatial discretization. An unconditionally stable, fully-implicit time discretization is used and leads to a coupled system of nonlinear equations that must be solved at each time step. We reformulate this system as a least squares problem with simple bounds involving only one of the phase saturations. Both a Gauss–Newton method and a quasi-Newton secant method are considered as potential solvers for the optimization problem. Each evaluation of the least squares objective function and gradient requires solving two single-phase self-adjoint, linear, uniformly-elliptic partial differential equations for which very efficient solution techniques have been developed.     

Entropy-conservative spatial discretization of the multidimensional quasi-gasdynamic system of equations

The multidimensional quasi-gasdynamic system written in the form of mass, momentum, and total energy balance equations for a perfect polytropic gas with allowance for a body force and a heat source is considered. A new conservative symmetric spatial discretization of these equations on a nonuniform rectangular grid is constructed (with the basic unknown functions—density, velocity, and temperature—defined on a common grid and with fluxes and viscous stresses defined on staggered grids). Primary attention is given to the analysis of entropy behavior: the discretization is specially constructed so that the total entropy does not decrease. This is achieved via a substantial revision of the standard discretization and applying numerous original features. A simplification of the constructed discretization serves as a conservative discretization with nondecreasing total entropy for the simpler quasi-hydrodynamic system of equations. In the absence of regularizing terms, the results also hold for the Navier–Stokes equations of a viscous compressible heat-conducting gas.     

ERROR ESTIMATES FOR TWO-SCALE COMPOSITE FINITE ELEMENT APPROXIMATIONS OF NONLINEAR PARABOLIC EQUATIONS

We study spatially semidiscrete and fully discrete two-scale composite finite element method for approximations of the nonlinear parabolic equations with homogeneous Dirich-let boundary conditions in a convex polygonal domain in the plane.This new class of finite elements,which is called composite finite elements,was first introduced by Hackbusch and Sauter[Numer.Math.,75(1997),pp.447-472]for the approximation of partial differential equations on domains with complicated geometry.The aim of this paper is to introduce an efficient numerical method which gives a lower dimensional approach for solving par-tial differential equations by domain discretization method.The composite finite element method introduces two-scale grid for discretization of the domain,the coarse-scale and the fine-scale grid with the degrees of freedom lies on the coarse-scale grid only.While the fine-scale grid is used to resolve the Dirichlet boundary condition,the dimension of the finite element space depends only on the coarse-scale grid.As a consequence,the resulting linear system will have a fewer number of unknowns.A continuous,piecewise linear composite finite element space is employed for the space discretization whereas the time discretization is based on both the backward Euler and the Crank-Nicolson methods.We have derived the error estimates in the L∞(L2)-norm for both semidiscrete and fully discrete schemes.Moreover,numerical simulations show that the proposed method is an efficient method to provide a good approximate solution.     

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.     

Extension of the EJIIM to stationary two-phase Stokes equations

We extend the Explicit Jump Immersed InterfaceMethod (EJIIM) to stationary two phase Stokes equations with discontinuous viscosity. As the underlying finite difference method the discretization in velocity and pressure variables is used on a staggered grid. The resulting algorithm converges with second order in velocity and first in pressure. The iteration count for solving the resulting linear system remains practically constant under grid refinement and is independent of the viscosity contrast. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A TWO-GRID METHOD FOR THE C0 INTERIOR PENALTY DISCRETIZATION OF THE MONGE-AMP(E)RE EQUATION

The purpose of this paper is to analyze an efficient method for the solution of the nonlinear system resulting from the discretization of the elliptic Monge-Ampère equation by a $C^0$ interior penalty method with Lagrange finite elements. We consider the two-grid method for nonlinear equations which consists in solving the discrete nonlinear system on a coarse mesh and using that solution as initial guess for one iteration of Newton's method on a finer mesh. Thus both steps are inexpensive. We give quasi-optimal $W^{1,\infty}$ error estimates for the discretization and estimate the difference between the interior penalty solution and the two-grid numerical solution. Numerical experiments confirm the computational efficiency of the approach compared to Newton's method on the fine mesh.     

Self–regularization by projection for noisy pseudodifferential equations of negative order

It is well known, that pseudodifferential equations of negative order considered in Sobolev spaces with small smoothness indices are ill–posed. On the other hand, it is known that efficient discretization schemes with properly chosen discretization parameters allow to obtain a regularization effect for such equations. The main accomplishment of the present paper is the principle for the adaptive choice of the discretization parameters directly from noisy discrete data. We argue that the combination of this principle with wavelet–based matrix compression techniques leads to algorithms which are order–optimal in the sense of complexity.     

Reduced Finite Element Discretizations of the Stokes and Navier-Stokes Equations

ABSTRACT

If finite element spaces for the velocity and pressure do not satisfy the Babu?ka-Brezzi condition, a stable conforming discretization of the Stokes or Navier-Stokes equations can be obtained by enriching the velocity space by suitable functions. Writing any function from the enriched space as a sum of a function from the original space and a function from the supplementary space, the discretization will contain a number of additional terms compared with a conforming discretization for the original pair of spaces. We show that not all these terms are necessary for the solvability of the discrete problem and for optimal convergence properties of the discrete solutions, which is useful for saving computer memory and for establishing a connection to stabilized methods.     

Mean-Square Approximation of Navier-Stokes Equations with Additive Noise in Vorticity-Velocity Formulation

We consider a time discretization of incompressible Navier-Stokes equations with spatial periodic boundary conditions and additive noise in the vorticity-velocity formulation. The approximation is based on freezing the velocity on time subintervals resulting in a linear stochastic parabolic equation for vorticity. At each time step, the velocity is expressed via vorticity using a formula corresponding to the Biot-Savart-type law. We prove the first mean-square convergence order of the vorticity approximation.     

Goal-oriented mesh adaptation for FE-vibration analyses of shell-like structures

The well–known semidiscrete approach in structural dynamics consists of two steps. First the discretization of the spatial domain using finite elements is performed. In the second step the numerical integration of the resulting system of ordinary differential equations is executed. The numerical schemes in both discretization steps contribute to the total discretization error. In this contribution the focus is on the spatial discretization error and on efficient strategies for error assessment and error reduction by goal–oriented mesh adaptation schemes. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Quadratic Störmer‐type methods for the solution of the Boussinesq equation by the method of lines

We study the numerical treatment of Boussinesq PDE equation using the method of lines. For the space discretization, we choose either classical finite differences or Fourier pseudospectral methods. Both cases result in a system of second‐order ordinary differential equations (ODEs) that is quadratic. In order to take advantage of this special feature, we choose to solve the ODE system using a new type of hybrid Numerov method specially constructed for such problems. Other efficient ODE solvers taken from the literature are used to solve the system of ODEs as well. By taking all the combinations of space discretization methods and ODE solvers, we discuss the stability and accuracy features revealed from the numerical tests. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2008     

Explicit solution of the incompressible Navier–Stokes equations with linear finite elements

A three-field finite element scheme for the explicit iterative solution of the stationary incompressible Navier–Stokes equations is studied. In linearized form the scheme is associated with a generalized time-dependent Stokes system discretized in time. The resulting system of equations allows for a stable approximation of velocity, pressure and stress deviator tensor, by means of continuous piecewise linear finite elements, in both two- and three-dimensional space. Convergence in an appropriate sense applying to this finite element discretization is demonstrated, for the stationary Stokes system.     

Efficient computation of characteristic roots of delay differential equations using LMS methods

We aim at the efficient computation of the rightmost, stability-determining characteristic roots of a system of delay differential equations. The approach we use is based on the discretization of the time integration operator by a linear multistep (LMS) method. The size of the resulting algebraic eigenvalue problem is inversely proportional to the steplength. We summarize theoretical results on the location and numerical preservation of roots. Furthermore, we select nonstandard LMS methods, which are better suited for our purpose. We present a new procedure that aims at computing efficiently and accurately all roots in any right half-plane. The performance of the new procedure is demonstrated for small- and large-scale systems of delay differential equations.     

A multigrid solver to the Helmholtz equation with a point source based on travel time and amplitude

The Helmholtz equation arises when modeling wave propagation in the frequency domain. The equation is discretized as an indefinite linear system, which is difficult to solve at high wave numbers. In many applications, the solution of the Helmholtz equation is required for a point source. In this case, it is possible to reformulate the equation as two separate equations: one for the travel time of the wave and one for its amplitude. The travel time is obtained by a solution of the factored eikonal equation, and the amplitude is obtained by solving a complex‐valued advection–diffusion–reaction equation. The reformulated equation is equivalent to the original Helmholtz equation, and the differences between the numerical solutions of these equations arise only from discretization errors. We develop an efficient multigrid solver for obtaining the amplitude given the travel time, which can be efficiently computed. This approach is advantageous because the amplitude is typically smooth in this case and, hence, more suitable for multigrid solvers than the standard Helmholtz discretization. We demonstrate that our second‐order advection–diffusion–reaction discretization is more accurate than the standard second‐order discretization at high wave numbers, as long as there are no reflections or caustics. Moreover, we show that using our approach, the problem can be solved more efficiently than using the common shifted Laplacian multigrid approach.     

Stokes方程的投影／方向分裂谱方法

我们提出和分析了一种求解Stokes方程的数值方法．新方法基于空间上的Legendre谱离散,时间上则采用投影／方向分裂格式．更确切地说,时间离散的出发点是旋度形式的压力校正投影法,在此基础上进一步应用方向分裂法,把速度和压力方程分裂为一系列一维的椭圆型子问题．然后生成的这些一维子问题用Legendre谱方法进行空间离散．另外,我们证明了全离散格式的稳定性．一些数值实验验证了收敛性和方法的有效性．     

A fourth-order split-step pseudospectral scheme for the Kuramoto-Tsuzuki equation

The numerics of the Kuramoto-Tsuzuki equation is dealt with in this paper. We propose a split-step Fourier pseudospectral discretization for solving the problem, which is split into one linear subproblem and one nonlinear subproblem. The nonlinear subproblem is integrated exactly via solving the equations for the amplitude and phase angle of the unknown complex-valued function respectively. The linear subproblem is first approximated by Fourier pseudospectral discretization to the spatial derivative, and then integrated exactly in phase space via solving the equations for the Fourier coefficients analytically. We apply a fourth-order splitting integration in time advances, and therefore the overall error in space discretization is of spectral order and the overall error in time discretization is of fourth order which merely comes from the splitting. The scheme is fully explicit, easy to implement and quite efficient thanks to FFT. Moreover, it is time reversible and gauge invariant which are two properties in the continuous problem. Extensive numerical results are reported, which are geared towards testing the convergence and demonstrating the efficiency and accuracy.     

A finite-element coarse-grid projection method for incompressible flow simulations

Coarse grid projection (CGP) methodology is a novel multigrid method for systems involving decoupled nonlinear evolution equations and linear elliptic Poisson equations. The nonlinear equations are solved on a fine grid and the linear equations are solved on a corresponding coarsened grid. Mapping operators execute data transfer between the grids. The CGP framework is constructed upon spatial and temporal discretization schemes. This framework has been established for finite volume/difference discretizations as well as explicit time integration methods. In this article we present for the first time a version of CGP for finite element discretizations, which uses a semi-implicit time integration scheme. The mapping functions correspond to the finite-element shape functions. With the novel data structure introduced, the mapping computational cost becomes insignificant. We apply CGP to pressure-correction schemes used for the incompressible Navier-Stokes flow computations. This version is validated on standard test cases with realistic boundary conditions using unstructured triangular meshes. We also pioneer investigations of the effects of CGP on the accuracy of the pressure field. It is found that although CGP reduces the pressure field accuracy, it preserves the accuracy of the pressure gradient and thus the velocity field, while achieving speedup factors ranging from approximately 2 to 30. The minimum speedup occurs for velocity Dirichlet boundary conditions, while the maximum speedup occurs for open boundary conditions.     

Robust AMLI methods for parabolic Crouzeix-Raviart FEM systems

For the iterative solution of linear systems of equations arising from finite element discretization of elliptic problems there exist well-established techniques to construct numerically efficient and computationally optimal preconditioners. Among those, most often preferred choices are Multigrid methods (geometric or algebraic), Algebraic MultiLevel Iteration (AMLI) methods, Domain Decomposition techniques.In this work, the method in focus is AMLI. We extend its construction and the underlying theory over to systems arising from discretizations of parabolic problems, using non-conforming finite element methods (FEM). The AMLI method is based on an approximated block two-by-two factorization of the original system matrix. A key ingredient for the efficiency of the AMLI preconditioners is the quality of the utilized block two-by-two splitting, quantified by the so-called Cauchy-Bunyakowski-Schwarz (CBS) constant, which measures the abstract angle between the two subspaces, associated with the two-by-two block splitting of the matrix.The particular choice of space discretization for the parabolic equations, used in this paper, is Crouzeix-Raviart non-conforming elements on triangular meshes. We describe a suitable splitting of the so-arising matrices and derive estimates for the associated CBS constant. The estimates are uniform with respect to discretization parameters in space and time as well as with respect to coefficient and mesh anisotropy, thus providing robustness of the method.