Abstract

Itô stochastic calculus is a mean-square or L2 calculus with different transformation rules to deterministic calculus. In particular, in view of its definition, an Itô integral is not as robust to approximation as the deterministic Riemann integral. This has some critical implications for the development of effective numerical schemes for stochastic differential equations (SDEs). Higher order numerical schemes for both strong and weak convergences have been derived using stochastic Taylor expansions, but most proofs in the literature assume the uniform boundedness of all relevant partial derivatives of the coefficient functions, which is highly restrictive. Problems also arise if solutions are restricted to certain regions, e.g. must be positive and the coefficient functions involve square roots.

Pathwise convergence is an alternative to the strong and weak convergences of the literature. It arises naturally in many important applications and, in fact, numerical calculations are carried out pathwise. Pathwise convergent numerical schemes for both SDEs and random ordinary differential equations (RODEs) will be discussed here. In particular, we see that a strong Taylor scheme for SDEs of order γ converges pathwise with order γ – ∈ for every arbitrarily small ∈ > 0 under the usual assumptions. We also introduce modified Taylor schemes which converge pathwise in a similar way, even when the coefficient derivatives are not uniformly bounded or are restricted to certain regions. In particular, these schemes can be applied without difficulty to volatility models in finance.

High oscillation is everywhere and it is difficult to compute. The conjunction of these two statements forms the rationale of this volume and it is therefore appropriate to deliberate further upon them.

Rapidly oscillating phenomena occur in electromagnetics, quantum theory, fluid dynamics, acoustics, electrodynamics, molecular modelling, computerised tomography and imaging, plasma transport, celestial mechanics – and this is a partial list! The main reason to the ubiquity of these phenomena is the presence of signals or data at widely different scales. Typically, the slowest signal is the carrier of important information, yet it is overlayed with signals, usually with smaller amplitude but with considerably smaller wavelength (cf. the top of Fig. 1). This presence of different frequencies renders both analysis and computation considerably more challenging. Another example of problems associated with high oscillation is provided by the wave packet at the bottom of Fig. 1 and by other phenomena which might appear dormant (or progress sedately, at measured pace) for a long time, only to demonstrate suddenly (and often unexpectedly) much more hectic behaviour.

The difficulty implicit in high oscillation becomes a significant stumbling block once we attempt to produce reliable numerical results. In principle, the problem can be alleviated by increasing the resolution of the computation (the step size, spatial discretization parameter, number of modes in an expansion, the bandwidth of a filter), since high oscillation is, after all, an artefact of resolution: zoom in sufficiently and all signals oscillate slowly.

Introduction

The numerical treatment of ordinary differential equations has continued to be a lively area of numerical analysis for more than a century, with interesting applications in various fields and rich theory. There are three main developments in the design of numerical techniques and in the analysis of the algorithms:

• Non-stiff differential equations. In the 19th century (Adams, Bashforth, and later Runge, Heun and Kutta), numerical integrators have been designed that are efficient (high order) and easy to apply (explicit) in practical situations.

• Stiff differential equations. In the middle of the 20th century one became aware that earlier developed methods are impractical for a certain class of differential equations (stiff problems) due to stability restrictions. New integrators (typically implicit) were needed as well as new theories for a better understanding of the algorithms.

• Geometric numerical integration. In long-time simulations of Hamiltonian systems (molecular dynamics, astronomy) neither classical explicit methods nor implicit integrators for stiff problems give satisfactory results. In the last few decades, special numerical methods have been designed that preserve the geometric structure of the exact flow and thus have an improved long-time behaviour.

The basic developments (algorithmic and theoretical) of these epochs are documented in the monographs [HNW93], [HW96], and [HLW06]. Within geometric numerical integration we can also distinguish between non-stiff and stiff situations. Since here the main emphasis is on conservative Hamiltonian systems, the term “stiff” has to be interpreted as “highly oscillatory”.

Abstract

In this paper I present a history of tractability of continuous problems, which has its beginning in the successful numerical tests for highdimensional integration of finance problems. Tractability results will be illustrated for two multivariate problems, integration and linear tensor products problems, in the worst case setting. My talk at FoCM'08 in Hong Kong and this paper are based on the book Tractability of Multivariate Problems, written jointly with Erich Novak. The first volume of our book has been recently published by the European Mathematical Society.

Introduction

Many people have recently become interested in studying the tractability of continuous problems. This area of research addresses the computational complexity of multivariate problems defined on spaces of functions of d variables, with d that can be in the hundreds or thousands; in fact, d can even be arbitrarily large. Such problems occur in numerous applications including physics, chemistry, finance, economics, and the computational sciences.

As with all problems arising in information-based complexity, we want to solve multivariate problems to within ∈, using algorithms that use finitely many functions values or values of some linear functionals. Let n(∈, d) be the minimal number of function values or linear functionals that is needed to compute the solution of the d-variate problem to within ∈.

For many multivariate problems defined over standard spaces of functions n(∈, d) is exponentially large in d.

Abstract

Introduction

Almost forty years ago an ingenious new method was discovered for the solution of the initial value problem of the Korteweg–de Vries (KdV) equation [GGKM67]. This new method, which was later called the inverse scattering transform (IST) method was based on the mysterious fact that the KdV equation is equivalent to two linear eigenvalue equations called a Lax pair (in honor of Peter Lax, [Lax68] who first understood that the IST method was the consequence of this remarkable property). The KdV equation belongs to a large class of nonlinear equations which are called integrable. Although there exist several types of integrable equations, which include PDEs, ODEs, singular-integrodifferential equations, difference equations and cellular automata, the existence of an associated Lax pair provides a common feature of all these equations.

After several attempts to extend the inverse scattering transform method from initial value problems to boundary value problems, a unified method for solving boundary value problems for linear and integrable nonlinear PDEs was introduced by the first author in [Fok97] and reviewed in [Fok08].

Abstract

Introduction

There is huge mathematical and engineering interest in acoustic and electromagnetic wave scattering problems, driven by many applications such as modelling radar, sonar, acoustic noise barriers, atmospheric particle scattering, ultrasound and VLSI. For time harmonic problems in infinite domains and media which are predominantly homogeneous, the boundary element method is a very popular solver, used in a number of large commercial codes, see e.g. [CSCVHH04]. In many practical applications the characteristic length scale L of the domain is large compared to the wavelength λ. Then the small dimensionless wavelength λ/L induces oscillatory solutions, and the application of conventional (piece-wise polynomial) boundary elements for this multiscale problem yields full matrices of dimension at least N = (L/λ)d-1 (in ℝd). (Domain finite elements lead to sparse matrices but require even larger N.) Since this “loss of robustness” as L/λ→∞ puts high frequency problems outside the reach of many standard algorithms, much recent research has been devoted to finding more robust methods.

Abstract

The running time of many iterative numerical algorithms is dominated by the condition number of the input, a quantity measuring the sensitivity of the solution with regard to small perturbations of the input. Examples are iterative methods of linear algebra, interior-point methods of linear and convex optimization, as well as homotopy methods for solving systems of polynomial equations. Thus a probabilistic analysis of these algorithms can be reduced to the analysis of the distribution of the condition number for a random input. This approach was elaborated upon for average-case complexity by many researchers.

The goal of this survey is to explain how average-case analysis can be naturally refined in the sense of smoothed analysis. The latter concept, introduced by Spielman and Teng in 2001, aims at showing that for all real inputs (even ill-posed ones), and all slight random perturbations of that input, it is unlikely that the running time will be large. A recent general result of Bürgisser, Cucker and Lotz (2008) gives smoothed analysis estimates for a variety of applications. Its proof boils down to local bounds on the volume of tubes around a real algebraic hypersurface in a sphere. This is achieved by bounding the integrals of absolute curvature of smooth hypersurfaces in terms of their degree via the principal kinematic formula of integral geometry and Bézout's theorem.

Introduction

In computer science, the most common theoretical approach to understanding the behaviour of algorithms is worst-case analysis.

Abstract

Subdivision schemes are efficient computational methods for the design, representation and approximation of 2D and 3D curves, and of surfaces of arbitrary topology in 3D. Such schemes generate curves/surfaces from discrete data by repeated refinements. While these methods are simple to implement, their analysis is rather complicated.

The first part of the paper presents the “classical” case of linear, stationary subdivision schemes refining control points. It reviews univariate schemes generating curves and their analysis. Several well-known schemes are discussed.

The second part of the paper presents three types of nonlinear subdivision schemes, which depend on the geometry of the data, and which are extensions of univariate linear schemes. The first two types are schemes refining control points and generating curves. The last is a scheme refining curves in a geometry-dependent way, and generating surfaces.

Introduction

Subdivision schemes are efficient computational tools for the generation of functions/curves/surfaces from discrete data by repeated refinements. They are used in geometric modeling for the design, representation and approximation of curves and of surfaces of arbitrary topology. A linear stationary scheme uses the same linear refinement rules at each location and at each refinement level. The refinement rules depend on a finite number of mask coefficients. Therefore, such schemes are easy to implement, but their analysis is rather complicated.

The first subdivision schemes were devised by G. de Rahm (1956) for the generation of functions with a first derivative everywhere and a second derivative nowhere.

Abstract

Introduction

Traditional methods for discretizing the Helmholtz equation based on using the equation directly suffer from the problem that they become rapidly more expensive as the wave number k (see Eq. (1.1)) increases. For example, finite element, finite difference, finite volume and discontinuous Galerkin methods all suffer from “pollution error” due to the fact that discrete waves have a slightly different wavelength than their exact counterparts (since this error in the wavelength depends on the wave number k, this leads to the “dispersion” of a wave).

Abstract

Introduction

Simulation of high-frequency waves is a problem encountered in a great many engineering and science fields. Currently the interest is driven by new applications in wireless communication (cell phones, Bluetooth, WiFi) and photonics (optical fibers, filters, switches). Simulation is also used increasingly in more classical applications. Some examples in electromagnetism are antenna design, radar signature computation and base station coverage for cell phones. In acoustics simulation is used for noise reduction, underwater communication and medical ultrasonography. Finding the location of an earthquake and oil exploration are some applications of seismic wave simulation in geophysics. Nondestructive testing is another example where both electromagnetic and acoustic waves are simulated.