Many problems in scientific computation can be solved by reducing them to a problem in linear algebra. This turns out to be an extremely successful approach. Linear algebra problems often have a rich mathematical structure, which gives rise to a variety of highly efficient and well-optimized algorithms. Consequently, scientists frequently consider linear models or linear approximations to nonlinear models simply because the machinery for solving linear problems is so well developed.

Basic linear algebraic operations are so fundamental that many current computer architectures are designed to maximize performance of linear algebraic computations. Even the list of the top 500 fastest computers in the world (maintained at www.top500.org) uses the HPL benchmark for solving dense systems of linear equations as the main performance measure for ranking computer systems.

In 1973, Hanson, Krogh, and Lawson described the advantages of adopting a set of basic routines for problems in linear algebra. These basic linear algebra subprograms are commonly referred to as the Basic Linear Algebra Subprograms (BLAS), and they are typically divided into three heirarchical levels: level 1 BLAS consists of vector–vector operations, level 2 BLAS are matrix–vector operations, and level 3 BLAS are matrix–matrix operations. The BLAS have been standardized with an application programming interface (API). This allows hardware vendors, compiler writers, and other specialists to provide programmers with access to highly optimized kernel routines adapted to specific architectures. Profiling tools indicate that many scientific computations spend most of their time in those sections of the code that call the BLAS. Thus, even small improvements in the BLAS can yield substantial speedups.

The problem of solving linear systems of equations is central in scientific computation. Systems of linear equations arise in many areas of science, engineering, finance, commerce, and other disciplines. They emerge directly through mathematical models in these areas or indirectly in the numerical solution of mathematical models as for example in the solution of partial differential equations. Because of the importance of linear systems, a great deal of work has gone into methods for their solution.

A system of m equations in n unknowns may be written in matrix form as Ax = b in which the coefficient matrix A is m × n, while the unknown vector x and the right-hand side b are n-dimensional. The most important case is when the coefficient matix is square, corresponding to the same number of unknowns as equations. The more general m × n case can be reduced to this.

There are two main methods for solving these systems, direct and iterative. If arithmetic were exact, a direct algorithm would solve the system exactly in a predetermined finite number of steps. In the reality of inexact computation, a direct method still stops in the same number of steps but accepts some level of numerical error. A major consideration with respect to direct methods is mitigating this error. Direct methods are typically used on moderately sized systems in which the coefficient matrix is dense, meaning most of its elements are nonzero. By contrast, iterative methods are typically used on very large, sparse systems. Iterative methods asymptotically converge to the solution and so run until the approximation is deemed acceptable.

Directed Acyclic Graph Representation

Just as a graph is an effective way to understand a function, a directed acyclic graph is an effective way to understand a parallel computation. Such a graph shows when each calculation is done, which others can be done at the same time, what prior calculations are needed for it and into what subsequent calculations it feeds.

Starting from a directed acyclic graph and given a set of processors, then a schedule can be worked out. A schedule assigns each calculation to a specific processor to be done at a specified time.

From a schdule, the total time for a computation follows and, from this, we get the difficulty or complexity of the computation.

A Directed Acyclic Graph Defines a Computation

A computation can be accurately depicted by means of a directed acyclic graph (DAG), G = (N, A), consisting of a set of vertices N and a set of directed arcs A. In such a portrayal the vertices, or nodes, of the graph represent subtasks to be performed on the data, while the directed arcs indicate the flow of data from one subtask to the next. In particular, a directed arc (i, j) ∈ A from node i to j indicates that calculation j requires the result of calculation i.

The input data is shown at the top of the graph. We take the flow of data from the top to the bottom of the graph (or, less often, from left to right). This also becomes the flow of time; it follows that the graph can have no cycles. With this convention, we may omit the direction indicators on the arcs.

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.