Locally linearized fractional step methods for nonlinear parabolic problems

This work deals with the efficient numerical solution of a class of nonlinear time-dependent reaction-diffusion equations. Via the method of lines approach, we first perform the spatial discretization of the original problem by applying a mimetic finite difference scheme. The system of ordinary differential equations arising from that process is then integrated in time with a linearly implicit fractional step method. For that purpose, we locally decompose the discrete nonlinear diffusion operator using suitable Taylor expansions and a domain decomposition splitting technique. The totally discrete scheme considers implicit time integrations for the linear terms while explicitly handling the nonlinear ones. As a result, the original problem is reduced to the solution of several linear systems per time step which can be trivially decomposed into a set of uncoupled parallelizable linear subsystems. The convergence of the proposed methods is illustrated by numerical experiments.     

Time stepping for vectorial operator splitting

We present a fully implicit finite difference method for the unsteady incompressible Navier-Stokes equations. It is based on the one-step θ-method for discretization in time and a special coordinate splitting (called vectorial operator splitting) for efficiently solving the nonlinear stationary problems for the solution at each new time level. The resulting system is solved in a fully coupled approach that does not require a boundary condition for the pressure. A staggered arrangement of velocity and pressure on a structured Cartesian grid combined with the fully implicit treatment of the boundary conditions helps us to preserve the properties of the differential operators and thus leads to excellent stability of the overall algorithm. The convergence properties of the method are confirmed via numerical experiments.     

An exponential transformation based splitting method for fast computations of highly oscillatory solutions

Splitting, or decomposition, methods have been widely used for achieving higher computational efficiency in solving wave equations. A major concern has remained, however, if the wave number involved is exceptionally large. In the case, merits of a conventional splitting method may diminish due to the fact that tiny discretization steps need to be employed to compensate high oscillations. This paper studies an alternative way for solving highly oscillatory paraxial wave problems via a modified splitting strategy. In the process, an exponential transformation is first introduced to convert the underlying differential equation to coupled nonlinear equations. Then the resulted oscillation-free system is treated by a Local-One-Dimensional (LOD) scheme for desired accuracy, efficiency and computability. The splitting method acquired is asymptotically stable and easy to use. Computational experiments are given to illustrate our numerical procedures.     

Dimension splitting for evolution equations

In this paper, we are concerned with splitting methods for the time integration of abstract evolution equations. We introduce an analytic framework which allows us to prove optimal convergence orders for various splitting methods, including the Lie and Peaceman–Rachford splittings. Our setting is applicable for a wide variety of linear equations and their dimension splittings. In particular, we analyze parabolic problems with Dirichlet boundary conditions, as well as degenerate equations on bounded domains. We further illustrate our theoretical results with a set of numerical experiments. This work was supported by the Austrian Science Fund under grant M961-N13.     

Convergence analysis of the FEM approximation of the first order projection method for incompressible flows with and without the inf-sup condition

In this paper we obtain convergence results for the fully discrete projection method for the numerical approximation of the incompressible Navier–Stokes equations using a finite element approximation for the space discretization. We consider two situations. In the first one, the analysis relies on the satisfaction of the inf-sup condition for the velocity-pressure finite element spaces. After that, we study a fully discrete fractional step method using a Poisson equation for the pressure. In this case the velocity-pressure interpolations do not need to accomplish the inf-sup condition and in fact we consider the case in which equal velocity-pressure interpolation is used. Optimal convergence results in time and space have been obtained in both cases.     

Tridiagonal implicit method to evaluate European and American options under infinite activity Lévy models

We propose an efficient implicit method to evaluate European and American options when the underlying asset follows an infinite activity Lévy model. Since the Lévy measure of the infinite activity model has the singularity at the origin, we approximate infinitely many small jumps by samples of a diffusion. The proposed methods to solve partial integro–differential equations for European options and linear complementarity problems for American options via an operator splitting method involve solving linear systems with tridiagonal matrices and so can significantly reduce the computations associated with the discrete integral operators. The numerical experiments verify that the proposed method has the second-order convergence rate under an infinite activity Lévy model.     

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.     

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.     

Defect-based local error estimators for splitting methods,with application to Schrödinger equations,Part I: The linear case

We introduce a defect correction principle for exponential operator splitting methods applied to time-dependent linear Schrödinger equations and construct a posteriori local error estimators for the Lie–Trotter and Strang splitting methods. Under natural commutator bounds on the involved operators we prove asymptotical correctness of the local error estimators, and along the way recover the known a priori convergence bounds. Numerical examples illustrate the theoretical local and global error estimates.     

Fast Runge-Kutta approximation of inhomogeneous parabolic equations

The result after N steps of an implicit Runge-Kutta time discretization of an inhomogeneous linear parabolic differential equation is computed, up to accuracy ɛ, by solving only linear systems of equations. We derive, analyse, and numerically illustrate this fast algorithm.     

Birkhoff normal form for splitting methods applied to semilinear Hamiltonian PDEs. Part II. Abstract splitting

We consider Hamiltonian PDEs that can be split into a linear unbounded operator and a regular non linear part. We consider abstract splitting methods associated with this decomposition where no discretization in space is made. We prove a normal form result for the corresponding discrete flow under generic non resonance conditions on the frequencies of the linear operator and on the step size, and under a condition of zero momentum on the nonlinearity. This result implies the conservation of the regularity of the numerical solution associated with the splitting method over arbitrary long time, provided the initial data is small enough. This result holds for rounded numerical schemes avoiding at each step possible high frequency energy drift. We apply these results to nonlinear Schrödinger equations as well as the nonlinear wave equation.     

Conserved quantities of some Hamiltonian wave equations after full discretization

Hamiltonian PDEs have some invariant quantities, which would be good to conserve with the numerical integration. In this paper, we concentrate on the nonlinear wave and Schrödinger equations. Under hypotheses of regularity and periodicity, we study how a symmetric space discretization makes that the space discretized system also has some invariants or `nearly' invariants which well approximate the continuous ones. We conjecture some facts which would explain the good numerical approximation of them after time integration when using symplectic Runge-Kutta methods or symmetric linear multistep methods for second-order systems.     

Incremental unknowns for solving partial differential equations

Summary Incremental unknowns have been proposed in [T] as a method to approximate fractal attractors by using finite difference approximations of evolution equations. In the case of linear elliptic problems, the utilization of incremental unknown methods provides a new way for solving such problems using several levels of discretization; the method is similar but different from the classical multigrid method.In this article we describe the application of incremental unknowns for solving Laplace equations in dimensions one and two. We provide theoretical results concerning two-level approximations and we report on numerical tests done with multi-level approximations.     

Space–time discontinuous Galerkin finite element method for shallow water flows

A space–time discontinuous Galerkin (DG) finite element method is presented for the shallow water equations over varying bottom topography. The method results in nonlinear equations per element, which are solved locally by establishing the element communication with a numerical HLLC flux. To deal with spurious oscillations around discontinuities, we employ a dissipation operator only around discontinuities using Krivodonova's discontinuity detector. The numerical scheme is verified by comparing numerical and exact solutions, and validated against a laboratory experiment involving flow through a contraction. We conclude that the method is second order accurate in both space and time for linear polynomials.     

Fast parallel solvers for symmetric boundary element domain decomposition equations

Summary. The boundary element method (BEM) is of advantage in many applications including far-field computations in magnetostatics and solid mechanics as well as accurate computations of singularities. Since the numerical approximation is essentially reduced to the boundary of the domain under consideration, the mesh generation and handling is simpler than, for example, in a finite element discretization of the domain. In this paper, we discuss fast solution techniques for the linear systems of equations obtained by the BEM (BE-equations) utilizing the non-overlapping domain decomposition (DD). We study parallel algorithms for solving large scale Galerkin BE–equations approximating linear potential problems in plane, bounded domains with piecewise homogeneous material properties. We give an elementary spectral equivalence analysis of the BEM Schur complement that provides the tool for constructing and analysing appropriate preconditioners. Finally, we present numerical results obtained on a massively parallel machine using up to 128 processors, and we sketch further applications to elasticity problems and to the coupling of the finite element method (FEM) with the boundary element method. As shown theoretically and confirmed by the numerical experiments, the methods are of algebraic complexity and of high parallel efficiency, where denotes the usual discretization parameter. Received August 28, 1996 / Revised version received March 10, 1997     

Convergence estimates of a projection-difference method for an operator-differential equation

This article investigates the projection-difference method for a Cauchy problem for a linear operator-differential equation with a leading self-adjoint operator A(t) and a subordinate linear operator K(t) in Hilbert space. This method leads to the solution of a system of linear algebraic equations on each time level; moreover, the projection subspaces are linear spans of eigenvectors of an operator similar to A(t). The convergence estimates are obtained. The application of the developed method for solving the initial boundary value problem is given.     

A local least-squares method for solving nonlinear partial differential equations of second order

In this paper a mesh-free method for the treatment of time-independent and time-dependent nonlinear PDEs of second order is presented. The basic idea of the discretization is a local least-squares approximation, similar to the moving least-squares approach in data approximation. However, in our approach the PDE is incorporated as an additional minimization constraint. The discretization leads to a fixed-point problem, which is solved by iteration. Because of the local nature of the method only small dimensional matrix inversions have to be done. The approximation error of the discretization—even on unstructured meshes—is comparable to respective versions of finite elements. As a by-product the method provides an a posteriori measure for the local approximation error. We discuss implementational aspects and present numerical simulations.     

Runge-Kutta methods without order reduction for linear initial boundary value problems

Summary. It is well-known the loss of accuracy when a Runge–Kutta method is used together with the method of lines for the full discretization of an initial boundary value problem. We show that this phenomenon, called order reduction, is caused by wrong boundary values in intermediate stages. With a right choice, the order reduction can be avoided and the optimal order of convergence in time is achieved. We prove this fact for time discretizations of abstract initial boundary value problems based on implicit Runge–Kutta methods. Moreover, we apply these results to the full discretization of parabolic problems by means of Galerkin finite element techniques. We present some numerical examples in order to confirm that the optimal order is actually achieved. Received July 10, 2000 / Revised version received March 13, 2001 / Published online October 17, 2001     

MULTILEVEL AUGMENTATION METHODS FOR SOLVING OPERATOR EQUATIONS

We introduce multilevel augmentation methods for solving operator equations based on direct sum decompositions of the range space of the operator and the solution space of the operator equation and a matrix splitting scheme. We establish a general setting for the analysis of these methods, showing that the methods yield approximate solutions of the same convergence order as the best approximation from the subspace. These augmentation methods allow us to develop fast, accurate and stable nonconventional numerical algorithms for solving operator equations. In particular, for second kind equations, special splitting techniques are proposed to develop such algorithms. These algorithms are then applied to solve the linear systems resulting from matrix compression schemes using wavelet-like functions for solving Fredholm integral equations of the second kind. For this special case, a complete analysis for computational complexity and convergence order is presented. Numerical examples are included to demonstra     

Error estimates for a mixed finite element discretization of some degenerate parabolic equations

We consider a numerical scheme for a class of degenerate parabolic equations, including both slow and fast diffusion cases. A particular example in this sense is the Richards equation modeling the flow in porous media. The numerical scheme is based on the mixed finite element method (MFEM) in space, and is of one step implicit in time. The lowest order Raviart–Thomas elements are used. Here we extend the results in Radu et al. (SIAM J Numer Anal 42:1452–1478, 2004), Schneid et al. (Numer Math 98:353–370, 2004) to a more general framework, by allowing for both types of degeneracies. We derive error estimates in terms of the discretization parameters and show the convergence of the scheme. The features of the MFEM, especially of the lowest order Raviart–Thomas elements, are now fully exploited in the proof of the convergence. The paper is concluded by numerical examples.