The quantification of probabilistic uncertainties in the outputs of physical, biological, and social systems governed by partial differential equations with random inputs require, in practice, the discretization of those equations. Stochastic finite element methods refer to an extensive class of algorithms for the approximate solution of partial differential equations having random input data, for which spatial discretization is effected by a finite element method. Fully discrete approximations require further discretization with respect to solution dependences on the random variables. For this purpose several approaches have been developed, including intrusive approaches such as stochastic Galerkin methods, for which the physical and probabilistic degrees of freedom are coupled, and non-intrusive approaches such as stochastic sampling and interpolatory-type stochastic collocation methods, for which the physical and probabilistic degrees of freedom are uncoupled. All these method classes are surveyed in this article, including some novel recent developments. Details about the construction of the various algorithms and about theoretical error estimates and complexity analyses of the algorithms are provided. Throughout, numerical examples are used to illustrate the theoretical results and to provide further insights into the methodologies.

The computational solution of problems can be restricted by the availability of solution methods for linear(ized) systems of equations. In conjunction with iterative methods, preconditioning is often the vital component in enabling the solution of such systems when the dimension is large. We attempt a broad review of preconditioning methods.

An inverse eigenvalue problem concerns the reconstruction of a structured matrix from prescribed spectral data. Such an inverse problem arises in many applications where parameters of a certain physical system are to be determined from the knowledge or expectation of its dynamical behaviour. Spectral information is entailed because the dynamical behaviour is often governed by the underlying natural frequencies and normal modes. Structural stipulation is designated because the physical system is often subject to some feasibility constraints. The spectral data involved may consist of complete or only partial information on eigenvalues or eigenvectors. The structure embodied by the matrices can take many forms. The objective of an inverse eigenvalue problem is to construct a matrix that maintains both the specific structure as well as the given spectral property. In this expository paper the emphasis is to provide an overview of the vast scope of this intriguing problem, treating some of its many applications, its mathematical properties, and a variety of numerical techniques.

Wilkinson defined a sparse matrix as one with enough zeros that it pays to take advantage of them.1 This informal yet practical definition captures the essence of the goal of direct methods for solving sparse matrix problems. They exploit the sparsity of a matrix to solve problems economically: much faster and using far less memory than if all the entries of a matrix were stored and took part in explicit computations. These methods form the backbone of a wide range of problems in computational science. A glimpse of the breadth of applications relying on sparse solvers can be seen in the origins of matrices in published matrix benchmark collections (Duff and Reid 1979a, Duff, Grimes and Lewis 1989a, Davis and Hu 2011). The goal of this survey article is to impart a working knowledge of the underlying theory and practice of sparse direct methods for solving linear systems and least-squares problems, and to provide an overview of the algorithms, data structures, and software available to solve these problems, so that the reader can both understand the methods and know how best to use them.

This paper surveys the construction, properties, and applications of generalized barycentric coordinates on polygons and polyhedra. Applications include: surface mesh parametrization in geometric modelling; image, curve, and surface deformation in computer graphics; and polygonal and polyhedral finite element methods.

Numerical simulation of high frequency acoustic, elastic or electro-magnetic wave propagation is important in many applications. Recently the traditional techniques of ray tracing based on geometrical optics have been augmented by numerical procedures based on partial differential equations. Direct simulations of solutions to the eikonal equation have been used in seismology, and lately approximations of the Liouville or Vlasov equation formulations of geometrical optics have generated impressive results. There are basically two techniques that follow from this latter approach: one is wave front methods and the other moment methods. We shall develop these methods in some detail after a brief review of more traditional algorithms for simulating high frequency wave propagation.

Methods for the solution of boundary integral equations have changed significantly during the last two decades. This is due, in part, to improvements in computer hardware, but more importantly, to the development of fast algorithms which scale linearly or nearly linearly with the number of degrees of freedom required. These methods are typically iterative, based on coupling fast matrix-vector multiplication routines with conjugate-gradient-type schemes. Here, we discuss methods that are currently under development for the fast, direct solution of boundary integral equations in three dimensions. After reviewing the mathematical foundations of such schemes, we illustrate their performance with some numerical examples, and discuss the potential impact of the overall approach in a variety of settings.

Digital images are matrices of equally spaced pixels, each containing a photon count. This photon count is a stochastic process due to the quantum nature of light. It follows that all images are noisy. Ever since digital images have existed, numerical methods have been proposed to improve the signal-to-noise ratio. Such ‘denoising’ methods require a noise model and an image model. It is relatively easy to obtain a noise model. As will be explained in the present paper, it is even possible to estimate it from a single noisy image.

We review recent work on level set methods for following the evolution of complex interfaces. These techniques are based on solving initial value partial differential equations for level set functions, using techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. The methodology results in robust, accurate, and efficient numerical algorithms for propagating interfaces in highly complex settings. We review the basic theory and approximations, describe a hierarchy of fast methods, including an extremely fast marching level set scheme for monotonically advancing fronts, based on a stationary formulation of the problem, and discuss extensions to multiple interfaces and triple points. Finally, we demonstrate the technique applied to a series of examples from geometry, material science and computer vision, including mean curvature flow, minimal surfaces, grid generation, fluid mechanics, combustion, image processing, computer vision, and etching, deposition and lithography in the microfabrication of electronic components.

Nonlinear eigenvalue problems arise in a variety of science and engineering applications, and in the past ten years there have been numerous breakthroughs in the development of numerical methods. This article surveys nonlinear eigenvalue problems associated with matrix-valued functions which depend nonlinearly on a single scalar parameter, with a particular emphasis on their mathematical properties and available numerical solution techniques. Solvers based on Newton’s method, contour integration and sampling via rational interpolation are reviewed. Problems of selecting the appropriate parameters for each of the solver classes are discussed and illustrated with numerical examples. This survey also contains numerous MATLAB code snippets that can be used for interactive exploration of the discussed methods.

The main ideas of path following by predictor–corrector and piecewise-linear methods, and their application in the direction of homotopy methods and nonlinear eigenvalue problems are reviewed. Further new applications to areas such as polynomial systems of equations, linear eigenvalue problems, interior methods for linear programming, parametric programming and complex bifurcation are surveyed. Complexity issues and available software are also discussed.

This paper provides an overview of AMG methods for solving large-scale systems of equations, such as those from discretizations of partial differential equations. AMG is often understood as the acronym of ‘algebraic multigrid’, but it can also be understood as ‘abstract multigrid’. Indeed, we demonstrate in this paper how and why an algebraic multigrid method can be better understood at a more abstract level. In the literature, there are many different algebraic multigrid methods that have been developed from different perspectives. In this paper we try to develop a unified framework and theory that can be used to derive and analyse different algebraic multigrid methods in a coherent manner. Given a smoother $R$ for a matrix $A$, such as Gauss–Seidel or Jacobi, we prove that the optimal coarse space of dimension $n_{c}$ is the span of the eigenvectors corresponding to the first $n_{c}$ eigenvectors $\bar{R}A$ (with $\bar{R}=R+R^{T}-R^{T}AR$). We also prove that this optimal coarse space can be obtained via a constrained trace-minimization problem for a matrix associated with $\bar{R}A$, and demonstrate that coarse spaces of most existing AMG methods can be viewed as approximate solutions of this trace-minimization problem. Furthermore, we provide a general approach to the construction of quasi-optimal coarse spaces, and we prove that under appropriate assumptions the resulting two-level AMG method for the underlying linear system converges uniformly with respect to the size of the problem, the coefficient variation and the anisotropy. Our theory applies to most existing multigrid methods, including the standard geometric multigrid method, classical AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG and spectral AMGe.

Interior methods for optimization were widely used in the 1960s, primarily in the form of barrier methods. However, they were not seriously applied to linear programming because of the dominance of the simplex method. Barrier methods fell from favour during the 1970s for a variety of reasons, including their apparent inefficiency compared with the best available alternatives. In 1984, Karmarkar's announcement of a fast polynomial-time interior method for linear programming caused tremendous excitement in the field of optimization. A formal connection can be shown between his method and classical barrier methods, which have consequently undergone a renaissance in interest and popularity. Most papers published since 1984 have concentrated on issues of computational complexity in interior methods for linear programming. During the same period, implementations of interior methods have displayed great efficiency in solving many large linear programs of ever-increasing size. Interior methods have also been applied with notable success to nonlinear and combinatorial problems. This paper presents a self-contained survey of major themes in both classical material and recent developments related to the theory and practice of interior methods.

In this paper we discuss the adaptation of the methods of homology from algebraic topology to the problem of pattern recognition in point cloud data sets. The method is referred to as persistent homology, and has numerous applications to scientific problems. We discuss the definition and computation of homology in the standard setting of simplicial complexes and topological spaces, then show how one can obtain useful signatures, called barcodes, from finite metric spaces, thought of as sampled from a continuous object. We present several different cases where persistent homology is used, to illustrate the different ways in which the method can be applied.

In convection-diffusion problems, transport processes dominate while diffusion effects are confined to a relatively small part of the domain. This state of affairs means that one cannot rely on the formal ellipticity of the differential operator to ensure the convergence of standard numerical algorithms. Thus new ideas and approaches are required.

The survey begins by examining the asymptotic nature of solutions to stationary convection-diffusion problems. This provides a suitable framework for the understanding of these solutions and the difficulties that numerical techniques will face. Various numerical methods expressly designed for convection-diffusion problems are then presented and extensively discussed. These include finite difference and finite element methods and the use of special meshes.

In this paper we present a general, theoretical foundation for the construction of cubature formulae to approximate multivariate integrals. The focus is on cubature formulae that are exact for certain vector spaces of polynomials. Our main quality criteria are the algebraic and trigonometric degrees. The constructions using ideal theory and invariant theory are outlined. The known lower bounds for the number of points are surveyed and characterizations of minimal cubature formulae are given. We include references to all known minimal cubature formulae. Finally, some methods to construct cubature formulae illustrate the previously introduced concepts and theorems.

This article describes the current state of the art of interior-point methods (IPMs) for convex, conic, and general nonlinear optimization. We discuss the theory, outline the algorithms, and comment on the applicability of this class of methods, which have revolutionized the field over the last twenty years.

In this survey we discuss properties of specific methods of approximation that belong to a family of greedy approximation methods (greedy algorithms). It is now well understood that we need to study nonlinear sparse representations in order to significantly increase our ability to process (compress, denoise, etc.) large data sets. Sparse representations of a function are not only a powerful analytic tool but they are utilized in many application areas such as image/signal processing and numerical computation. The key to finding sparse representations is the concept of m-term approximation of the target function by the elements of a given system of functions (dictionary). The fundamental question is how to construct good methods (algorithms) of approximation. Recent results have established that greedy-type algorithms are suitable methods of nonlinear approximation in both m-term approximation with regard to bases, and m-term approximation with regard to redundant systems. It turns out that there is one fundamental principle that allows us to build good algorithms, both for arbitrary redundant systems and for very simple well-structured bases, such as the Haar basis. This principle is the use of a greedy step in searching for a new element to be added to a given m-term approximant.

Let P(x) = 0 be a system of n polynomial equations in n unknowns. Denoting P = (p1,…, pn), we want to find all isolated solutions of

for x = (x1,…,xn). This problem is very common in many fields of science and engineering, such as formula construction, geometric intersection problems, inverse kinematics, power flow problems with PQ-specified bases, computation of equilibrium states, etc. Elimination theory-based methods, most notably the Buchberger algorithm (Buchberger 1985) for constructing Gröbner bases, are the classical approach to solving (1.1), but their reliance on symbolic manipulation makes those methods seem somewhat unsuitable for all but small problems.

This survey describes probabilistic algorithms for linear algebraic computations, such as factorizing matrices and solving linear systems. It focuses on techniques that have a proven track record for real-world problems. The paper treats both the theoretical foundations of the subject and practical computational issues.

Topics include norm estimation, matrix approximation by sampling, structured and unstructured random embeddings, linear regression problems, low-rank approximation, subspace iteration and Krylov methods, error estimation and adaptivity, interpolatory and CUR factorizations, Nyström approximation of positive semidefinite matrices, single-view (‘streaming’) algorithms, full rank-revealing factorizations, solvers for linear systems, and approximation of kernel matrices that arise in machine learning and in scientific computing.