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.     

Waveform relaxation for reaction-diffusion equations

We report a new waveform relaxation (WR) algorithm for general semi-linear reaction-diffusion equations. The superlinear rate of convergence of the new WR algorithm is proved, and we also show the advantages of the new approach superior to the classical WR algorithms by the estimation on iteration errors. The corresponding discrete WR algorithm for reaction-diffusion equations is presented, and further the parallelism of the discrete WR algorithm is analyzed. Moreover, the new approach is extended to handle the coupled reaction-diffusion equations. Numerical experiments are carried out to verify the effectiveness of the theoretic work.     

Towards efficient tracking of inertial particles with high-order multidomain methods

This paper develops an efficient particle tracking algorithm to be used in fluid simulations approximated by a high-order multidomain discretization of the Navier–Stokes equations. We discuss how to locate a particle's host subdomain, how to interpolate the flow field to its location, and how to integrate its motion in time. A search algorithm for the nearest subdomain and quadrature point, tuned to a typical quadrilateral isoparametric spectral subdomain, takes advantage of the inverse of the linear blending equation. We show that to compute particle-laden flows, a sixth-order Lagrangian polynomial that uses points solely within a subdomain is sufficiently accurate to interpolate the carrier phase variables to the particle position. Time integration of particles with a lower-order Adams–Bashforth scheme, rather than the fourth-order Runge–Kutta scheme often used for the integration of the carrier phase, increases computational efficiency while maintaining engineering accuracy. We verify the tracking algorithm with numerical tests on a steady channel flow and an unsteady backward-facing step flow.     

Stability and accuracy of time-extrapolated ADI-FDTD methods for solving wave equations

Some recent work on the ADI-FDTD method for solving Maxwell's equations in 3-D have brought out the importance of extrapolation methods for the time stepping of wave equations. Such extrapolation methods have previously been used for the solution of ODEs. The present context (of wave equations) brings up two main questions which have not been addressed previously: (1) when will extrapolation in time of an unconditionally stable scheme for a wave equation again feature unconditional stability, and (2) how will the accuracy and computational efficiency depend on how frequently in time the extrapolations are carried out. We analyze these issues here.     

Isomonodromic differential equations and differential categories

We study isomonodromicity of systems of parameterized linear differential equations and related conjugacy properties of linear differential algebraic groups by means of differential categories. We prove that isomonodromicity is equivalent to isomonodromicity with respect to each parameter separately under a filtered-linearly closed assumption on the field of functions of parameters. Our result implies that one does not need to solve any non-linear differential equations to test isomonodromicity anymore. This result cannot be further strengthened by weakening the requirement on the parameters as we show by giving a counterexample. Also, we show that isomonodromicity is equivalent to conjugacy to constants of the associated parameterized differential Galois group, extending a result of P. Cassidy and M. Singer, which we also prove categorically. We illustrate our main results by a series of examples, using, in particular, a relation between the Gauss–Manin connection and parameterized differential Galois groups.     

Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.     

A dual graph-norm refinement indicator for finite volume approximations of the Euler equations

Summary. We generalise and apply a refinement indicator of the type originally designed by Mackenzie, Süli and Warnecke in [15] and [16] for linear Friedrichs systems to the Euler equations of inviscid, compressible fluid flow. The Euler equations are symmetrized by means of entropy variables and locally linearized about a constant state to obtain a symmetric hyperbolic system to which an a posteriori error analysis of the type introduced in [15] can be applied. We discuss the details of the implementation of the refinement indicator into the DLR--Code which is based on a finite volume method of box type on an unstructured grid and present numerical results. Received May 15, 1995 / Revised version received April 17, 1996     

On computation of solution curves for semilinear elliptic problems

We consider computation of solution curves for semilinear elliptic equations. In case solution is stable, we present an algorithm with monotone convergence, which is a considerable improvement of the corresponding schemes in [4] and [5]. For the unstable solutions, we show how to construct a fourth-order evolution equation, for which the same solution will be stable.     

Embedding theorems for HNN extensions of inverse semigroups

A variant of an HNN extension of an inverse semigroup introduced by Gilbert [N.D. Gilbert, HNN extensions of inverse semigroups and groupoids, J. Algebra 272 (2004) 27-45] is defined provided that associated subsemigroups are order ideals. We show this presentation still makes sense without the assumption on associated subsemigroups in the sense that it gives a semigroup deserving to be an HNN extension, and it is embedded into another variant using the automata theoretical technique based on combinatorial and geometrical properties of Schützenberger graphs.     

Spatial approximation of stochastic convolutions

We study linear stochastic evolution partial differential equations driven by additive noise. We present a general and flexible framework for representing the infinite dimensional Wiener process, which drives the equation. Since the eigenfunctions and eigenvalues of the covariance operator of the process are usually not available for computations, we propose an expansion in an arbitrary frame. We show how to obtain error estimates when the truncated expansion is used in the equation. For the stochastic heat and wave equations, we combine the truncated expansion with a standard finite element method and derive a priori bounds for the mean square error. Specializing the frame to biorthogonal wavelets in one variable, we show how the hierarchical structure, support and cancelation properties of the primal and dual bases lead to near sparsity and can be used to simplify the simulation of the noise and its update when new terms are added to the expansion.     

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.     

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.     

A mountain pass method for the numerical solution of semilinear wave equations

Summary It is well-known that periodic solutions of semilinear wave equations can be obtained as critical points of related functionals. In the situation that we studied, there is usually an obvious solution obtained as a solution of linear problem. We formulate a dual variational problem in such a way that the obvious solution is a local minimum. We then find additional non-obvious solutions via a numerical mountain pass algorithm, based on the theorems of Ambrosetti, Rabinowitz and Ekeland. Numerical results are presented.Research supported in part by grant DMS-9208636 from the National Science FoundationResearch supported in part by grant DMS-9102632 from the National Science Foundation     

An inverse problem of identifying the coefficient of first-order in a degenerate parabolic equation

This work studies an inverse problem of determining the first-order coefficient of degenerate parabolic equations using the measurement data specified at a fixed internal point. Being different from other ordinary parameter identification problems in parabolic equations, in our mathematical model there exists degeneracy on the lateral boundaries of the domain, which may cause the corresponding boundary conditions to go missing. By the contraction mapping principle, the uniqueness of the solution for the inverse problem is proved. A numerical algorithm on the basis of the predictor-corrector method is designed to obtain the numerical solution and some typical numerical experiments are also performed in the paper. The numerical results show that the proposed method is stable and the unknown function is recovered very well. The results obtained in the paper are interesting and useful, and can be extended to other more general inverse coefficient problems of degenerate PDEs.     

Malcev presentations for subsemigroups of direct products of coherent groups

The direct product of a free group and a polycyclic group is known to be coherent. This paper shows that every finitely generated subsemigroup of the direct product of a virtually free group and an abelian group admits a finite Malcev presentation. (A Malcev presentation is a presentation of a special type for a semigroup that embeds into a group. A group is virtually free if it contains a free subgroup of finite index.) By considering the direct product of two free semigroups, it is also shown that polycyclic groups, unlike nilpotent groups, can contain finitely generated subsemigroups that do not admit finite Malcev presentations.     

Boundedness and stability of solutions to difference equations

This paper is concerned with the qualitative behaviour of solutions to difference equations. We focus on boundedness and stability of solutions and we present a unified theory that applies both to autonomous and nonautonomous equations and to nonlinear equations as well as linear equations. Our presentation brings together new, established, and hard-to-find results from the literature and provides a theory that is both memorable and easy to apply. We show how the theoretical results given here relate to some of those in the established literature and by means of simple examples we indicate how the use of Lipschitz constants in this way can provide useful insights into the qualitative behaviour of solutions to some nonlinear problems including those arising in numerical analysis.     

Stability of collocation-based Runge-Kutta-Nyström methods

We analyse the attainable order and the stability of Runge-Kutta-Nyström (RKN) methods for special second-order initial-value problems derived by collocation techniques. Like collocation methods for first-order equations the step point order ofs-stage methods can be raised to 2s for alls. The attainable stage order is one higher and equalss+1. However, the stability results derived in this paper show that we have to pay a high price for the increased stage order.These investigations were supported by the University of Amsterdam who provided the third author with a research grant for spending a total of two years in Amsterdam.     

Local linear convergence of approximate projections onto regularized sets

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.     

超定线性方程极大极小解的一种近似算法

本文通过构造一个无约束凸规划问题,建立了求超定线性方程组的极大极小解的一种近似算法,证明了算法的收剑性,并给出了初步的数值结果.     

Polynomial evaluation and associated polynomials

We show a connection between the Clenshaw algorithm for evaluating a polynomial , expanded in terms of a system of orthogonal polynomials, and special linear combinations of associated polynomials. These results enable us to get the derivatives of analogously to the Horner algorithm for evaluating polynomials in monomial representations. Furthermore we show how a polynomial given in monomial (!) representation can be evaluated for using the Clenshaw algorithm without complex arithmetic. From this we get a connection between zeros of polynomials expanded in terms of Chebyshev polynomials and the corresponding polynomials in monomial representation with the same coefficients. Received January 2, 1995 / Revised version received April 9, 1997