Abstract

The efficient numerical treatment of high-dimensional problems is hampered by the curse of dimensionality. We review approximation techniques which overcome this problem to some extent. Here, we focus on methods stemming from Kolmogorov's theorem, the ANOVA decomposition and the sparse grid approach and discuss their prerequisites and properties. Moreover, we present energy-norm based sparse grids and demonstrate that, for functions with bounded mixed derivatives on the unit hypercube, the associated approximation rate in terms of the involved degrees of freedom shows no dependence on the dimension at all, neither in the approximation order nor in the order constant.

Introduction

The discretization of PDEs by conventional methods is limited to problems with up to three or four dimensions due to storage requirements and computational complexity. The reason is the so-called curse of dimensionality, a term coined in (Bellmann 1961). Here, the cost to compute and represent an approximation with a prescribed accuracy ε depends exponentially on the dimensionality d of the problem considered. We encounter complexities of the order O(ε−d/r) with r > 0 depending on the respective approach, the smoothness of the function under consideration, the polynomial degree of the ansatz functions and the details of the implementation. If we consider simple uniform grids with piecewise d-polynomial functions over a bounded domain in a finite element or finite difference approach, this complexity estimate translates to O(Nd) grid points or degrees of freedom for which approximation accuracies of the order O(N−r) are achieved.

Abstract

In this paper, we survey some recent progress in the smoothed analysis of algorithms and heuristics in mathematical programming, combinatorial optimization, computational geometry, and scientific computing. Our focus will be more on problems and results rather than on proofs. We discuss several perturbation models used in smoothed analysis for both continuous and discrete inputs. Perhaps more importantly, we present a collection of emerging open questions as food for thought in this field.

Prelinminaries

The quality of an algorithm is often measured by its time complexity (Aho, Hopcroft & Ullman (1983) and Cormen, Leiserson, Rivest & Stein (2001)). There are other performance parameters that might be important as well, such as the amount of space used in computation, the number of bits needed to achieve a given precision (Wilkinson (1961)), the number of cache misses in a system with a memory hierarchy (Aggarwal et al. (1987), Frigo et al. (1999), and Sen et al. (2002)), the error probability of a decision algorithm (Spielman & Teng (2003a)), the number of random bits needed in a randomized algorithm (Motwani & Raghavan (1995)), the number of calls to a particular “oracle” program, and the number of iterations of an iterative algorithm (Wright (1997), Ye (1997), Nesterov & Nemirovskii (1994), and Golub & Van Loan (1989)). The quality of an approximation algorithm could be its approximation ratio (Vazirani (2001)) and the quality of an online algorithm could be its competitive ratio (Sleator & Tarjan (1985) and Borodin & El-Yaniv (1998)).

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), and Santander (2005). The next conference is expected to be held in 2008. More information about FoCM is available at its website http://www.focm.net.

The conference in Santander on June 30 – July 9, 2005, 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.

Introduction

The question, “Is the long term qualitative behaviour of numerical solutions accurate?” is increasingly being asked. One way of gauging this is to examine the success or otherwise of the numerical code to maintain certain conserved quantities such as energy or potential vorticity. For example, numerical solutions of a conservative system are usually presented together with plots of energy dissipation. But what if the conserved quantity is a less well studied quantity than energy or is not easily measured in the approximate function space? What if there is more than one conserved quantity? Is it possible to construct an integrator that maintains, a priori, several laws at once?

Arguably, the most physically important conserved quantities arise via Noether's theorem; the system has an underlying variational principle and a Lie group symmetry leaves the Lagrangian invariant. A Lie group is a group whose elements depend in a smooth way on real or complex parameters. Energy, momentum and potential vorticity, used to track the development of certain weather fronts, are conserved quantities arising from translation in time and space, and fluid particle relabelling respectively. The Lie groups for all three examples act on the base space which is discretised. It is not obvious how to build their automatic conservation into a discretisation, and expressions for the conserved quantities must be known exactly in order to track them.

Abstract

In nonlinear approximation we seek ways to approximate complicated functions by simpler functions using methods that depend nonlinearly on the function being approximated. Recently, a particular kind of nonlinear approximation, namely greedy approximation has attracted a lot of attention in both theoretical and applied settings. Greedy type algorithms have proven to be very useful in various applications such as image compression, signal processing, design of neural networks, and the numerical solution of nonlinear partial differential equations. A theory of greedy approximation is now emerging. Some fundamental convergence results have already been established and many fundamental problems remain unsolved. In this survey we place emphasis on the study of the efficiency of greedy algorithms with regards to redundant systems (dictionaries). Redundancy, on the one hand, offers much promise for greater efficiency in terms of the rate of approximation. On the other hand, it gives rise to highly nontrivial theoretical and practical problems. We note that there is solid justification for the importance of redundant systems in both theoretical questions and practical applications. This survey is a continuation of the survey Temlyakov (2003a) on nonlinear approximations. Here we concentrate on more recent results on greedy approximation.

Introduction

In the last decade we have seen successes in the study of nonlinear approximation (see the surveys DeVore (1998) and Temlyakov (2003a)). This study was motivated by numerous applications. Nonlinear approximation is important in applications because of its efficiency.

Abstract

These pages summarize some results on the efficiency of polynomial equation solving. We focus on semantic algorithms, i.e., algorithms whose running time depends on some intrinsic/semantic invariant associated with the input data. Both computer algebra and numerical analysis algorithms are discussed. We show a probabilistic and positive answer to Smale's 17th problem. Estimates of the probability distribution of the condition number of singular complex matrices are also exhibited.

Introduction

These pages summarize some results on upper and lower complexity bounds in Elimination Theory. They are a revision of the program stated in Pardo (1995).

We focus on Efficient Polynomial Equation Solving. This is one of the challenges in the recent history of Computational Mathematics. Two main frameworks in scientific computing deal with this problem. Following different approaches, symbolic/algebraic computing and numerical analysis developed their own techniques for solving polynomial equations. We survey statements of both approaches. New results are contained in Sections 1.4 and 1.5.

Multivariate Polynomial Equation Solving is a central topic both in Computational Mathematics and Computational Algebraic Geometry (Elimination Theory in nineteenth century terminology). Its origin goes back to work of Sturm, Hermite, Cayley, and Sylvester, among others. Elimination Theory consists of the preparation of input data (polynomial equations and inequalities) to answer questions involving quantifiers. This approach also underlies Kronecker (1882), Hilbert (1890) and further developments in Algebraic Geometry.

Introduction

Although Java first gained fame with applets in Web browsers and then became a popular tool for creating large enterprise services, the developers of Java originally intended it for embedded applications in consumer devices such as TV remote controls and Personal Data Assistants (see Chapter 1). The term “embedded” generally refers to encapsulating a processor into a device, along with programs stored in non-volatile memory, to provide services and features specific to that device. Microcontrollers, for example, are the most common type of embedded processors.

By embedded Java we refer to a device that contains either a conventional processor running a JVM or a special type of processor that either directly executes Java bytecodes or assists a conventional processor with executing bytecodes. The motivations for device designers to embed Java depend on the particular device, but, in general, Java provides flexibility, interactivity, networking, portability, and fast development of the software for embedded projects.

Today several types of commercial devices come with Java built into them. As mentioned in Chapter 1, over 600 million JavaCards have been sold around the world as of mid-2004, and several hundred cell phone models include Java.

Embedded applications typically must deal with very limited resources. A full-blown J2SE application on a desktop with a Swing graphical interface might require several megabytes of RAM.

Introduction

In Chapter 6 we presented the basic techniques for loading image files into applets and applications. We used instances of the Image class to hold images and invoked the drawImage() method in the Graphics class to display them. In this chapter we explore further the image handling and processing capabilities of Java.

In the first few sections we look in greater detail at the Image class and introduce its BufferedImage subclass, which offers many useful features. We discuss how to monitor the loading of images, how to scale image displays, how to create images, and how to save images to files.

We then switch to topics related to image processing. We show how to gain access to the pixels of an image, how to modify them, how to make an image from a pixel array, and how to use these techniques to create animations. We then discuss the standard filters provided with Java 2D and also give an example of a custom filter.

We give only a brief overview of the wide range of image tools available with Java. The classes mentioned here, for example, hold many overloaded constructors and methods that provide many options. See the Java 2 API Specifications for thorough descriptions of the classes. Also, see the book by Knudsen [1] and the other resources for in-depth discussions of images in Java [2, 3].

Introduction

In Part I of this book and Web Course we tried to provide an introduction to the essential elements of the Java language that allow you to begin creating useful programs in short order. In this chapter we discuss several practical techniques that will expand the capabilities of your programs. We begin with a discussion of how to print your graphics displays and then discuss several user interface features such as cursor icons and popup menus, handling keystrokes, and audio. We also review various ways to improve the speed of Java programs.

Printing

Java 1.1 provided the capability to print what is displayed on a Java component [1]. Java 1.2 added Java 2D, which expanded the print capabilities to support greater control over multiple page printing and other features. (We should point out that printing only works with applications since the SecurityManager in browser JVMs blocks printing from applets.)

In Java graphics the usual job of the paint() method in AWT and the paintComponent() method in Swing is to send drawing commands to the monitor screen. Java printing simply entails sending drawing commands to the printer instead of the monitor screen. In rendering Java components, we have seen that a Graphics context object is passed to the paint() and paintComponent() methods. To render to the printer, you obtain an instance of PrintGraphics, which is a subclass of Graphics, and pass it to the paint() or paintComponent() method.