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.

The Society for the Foundations of Computational Mathematics supports and promotes fundamental research in computational mathematics and its applications, interpreted in the broadest sense. It fosters interaction among mathematics, computer science and other areas of computational science through its conferences, workshops and publications. As part of this endeavour to promote research across a wide spectrum of subjects concerned with computation, the Society brings together leading researchers working in diverse fields. Major conferences of the Society have been held in Park City (1995), Rio de Janeiro (1997), Oxford (1999), Minneapolis (2002), Santander (2005), and Hong Kong (2008). The next conference is expected to be held in 2011. More information about FoCM is available at its website http://www.focm.net.

The conference in Hong Kong on June 16 – 26, 2008, was attended by several hundred scientists. FoCM conferences follow a set pattern: mornings are devoted to plenary talks, while in the afternoon the conference divides into a number of workshops, each devoted to a different theme within the broad theme of foundations of computational mathematics. This structure allows for a very high standard of presentation, while affording endless opportunities for cross-fertilization and communication across subject boundaries. Workshops at the Hong Kong conference were held in the following nineteen fields:

1. – Approximation theory

2. – Asymptotic analysis

3. – Computational algebraic geometry

4. – Computational dynamics

5. – Computational number theory

6. – Foundations of numerical PDEs

7. – Geometric integration and computational mechanics

8. – Image and signal processing

9. – Information-based complexity

10. […]

Abstract

When studying a dynamical system from a global viewpoint, there are only few theoretical tools at our disposal. This is especially true if we want to describe all aspects of the dynamics with a reasonable amount of detail. A combination of analytic, symbolic and numerical tools, together with qualitative and topological considerations, can give a reasonably good description. Furthermore it is possible to derive paradigmatic models which can be analysed theoretically and allow us to study pieces of the dynamics. It is also important to know the relevance of different phenomena. Are they confined to a narrow domain of the phase space or to a tiny region of the parameter space or do they really play a significant role? Several theoretical/numerical tools are presented, and applied to different problems in celestial mechanics, unfolding of singularities and other problems. This is part of a project aimed towards understanding finite-dimensional systems in a global way. To avoid technicalities we shall assume that all maps and flows considered in this paper are analytic.

Introduction

Many properties are known for low-dimensional conservative systems, like Area-Preserving or Measure-Preserving Maps (APM, MPM) or systems which can be reduced to them as 2-degrees of freedom Hamiltonian systems and volume-preserving 3D flows. Most of these properties have a local character, either around a fixed point, around a given orbit, like a periodic orbit or a homoclinic orbit, or around an invariant curve or torus.

Abstract

Introduction

In the numerical simulation of partial differential equations, the existence of subgrid scale phenomena poses considerable difficulties. With subgrid scale phenomena, we mean those processes which could influence the solution on the computational grid but which have length scales shorter than the grid size. Highly oscillatory initial data may, for example, interact with fine scales in the material properties and produce coarse scale contributions to the solution.

Abstract

Asymptotic methods include asymptotic evaluation of integrals, asymptotic expansion of solutions to differential equations, singular perturbation techniques, discrete asymptotics, etc. In this survey, we present some of the most significant developments in these areas in the second half of the 20th century. Also mentioned will be a new method known as the Riemann-Hilbert approach, which has had a significant impact in the field in recent years.

Introduction

What is asymptotics? It is the branch of analysis that deals with problems concerning the determination of the behavior of a function as one of its parameters tends to a specific value, or a sequence as its index tends to infinity. Thus, it includes, for example, Stirling's formula, asymptotic expansion of the Lebesgue constant in Fourier series, and even the prime number theorem. But, in general, it refers to just the two main areas: (i) asymptotic evaluation of integrals, and (ii) asymptotic solutions to differential equations. The second area sometimes also includes the subject of singular perturbation theory. But the results in this subarea are mostly formal (i.e., not mathematically rigorous). Although occasionally one may also include the methods of asymptotic enumeration in the general area of asymptotics, the development of this area is far behind those in the two areas mentioned above. For instance, a turning point theory for difference equations was not introduced until just around the turn of this century, while the corresponding theory for differential equations was developed in the 1930's.

Introduction

When you put several commands together to accomplish some purpose beyond the capacity of any one individually, you are programming. Mathematica is intentionally designed for this purpose. Like anything else, getting good at programming takes practice. But it is also exceedingly handy to have familiarity with commands that lend themselves to such greater enterprises. We've seen plenty of Mathematica in the first seven chapters; in this chapter we'll discuss commands that are especially useful for programming. Keep in mind that we only have room here for a brief introduction to these concepts. Entire books, much longer than this one, have been written on this subject. Think of this chapter as a gentle introduction.

We begin in Section 8.2 with some important background material, a consideration of the internal form of any and every Mathematica expression. Every expression, input, output (or a cell, or an entire notebook) is highly structured. Before it is possible to operate on any such expression, you simply have to know what you are dealing with. You have to understand its structure.

Some of the most fundamental structures in Mathematica are the various types of numbers. These are addressed in Section 8.3. The internal forms of the various types of numbers are discussed, along with notions such as precision and accuracy. Mathematica has the capacity to carry out calculations to arbitrarily high precision. In this section we also discuss a myriad of possibilities for the display of numbers.

Opening Saved Notebooks

You can open any Mathematica notebook file by double-clicking on its icon with your mouse. It will appear on your screen exactly as it was when it was saved. You can open two or more notebooks at the same time if you wish.

Adding Text to Notebooks

Text Cells

Mathematica has an integrated word processor that is simple to use once you are familiar with the cell structure of a Mathematica notebook (see Section 1.5, “Input and Output,” on page 3 for a discussion of input and output cells). To add text to a notebook, you need to create a text cell. To do this, first go to the Window menu and select Show Toolbar. A toolbar will appear across the top of your notebook window. Now position your mouse between any two cells in your notebook (or below the last cell in the notebook, or above the first cell) where you want to add text. The cursor will change from a vertical bar to a horizontal bar. Now click. You should notice a horizontal black line that runs completely across your notebook window. Next, use your mouse to select Text from the pull-down menu on the toolbar, and start typing. As soon as you do, a new text cell will be inserted in your notebook at the position of the horizontal black line, and it will contain the text you type.