This paper is a contemporary review of QMC (‘quasi-Monte Carlo’) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s, where s may be large, or even infinite. After a general introduction, the paper surveys recent developments in lattice methods, digital nets, and related themes. Among those recent developments are methods of construction of both lattices and digital nets, to yield QMC rules that have a prescribed rate of convergence for sufficiently smooth functions, and ideally also guaranteed slow growth (or no growth) of the worst-case error as s increases. A crucial role is played by parameters called ‘weights’, since a careful use of the weight parameters is needed to ensure that the worst-case errors in an appropriately weighted function space are bounded, or grow only slowly, as the dimension s increases. Important tools for the analysis are weighted function spaces, reproducing kernel Hilbert spaces, and discrepancy, all of which are discussed with an appropriate level of detail.

In this article we consider finite element methods for approximating the solution of partial differential equations on surfaces. We focus on surface finite elements on triangulated surfaces, implicit surface methods using level set descriptions of the surface, unfitted finite element methods and diffuse interface methods. In order to formulate the methods we present the necessary geometric analysis and, in the context of evolving surfaces, the necessary transport formulae. A wide variety of equations and applications are covered. Some ideas of the numerical analysis are presented along with illustrative numerical examples.

Many different procedures have been proposed for optimization calculations when first derivatives are not available. Further, several researchers have contributed to the subject, including some who wish to prove convergence theorems, and some who wish to make any reduction in the least calculated value of the objective function. There is not even a key idea that can be used as a foundation of a review, except for the problem itself, which is the adjustment of variables so that a function becomes least, where each value of the function is returned by a subroutine for each trial vector of variables. Therefore the paper is a collection of essays on particular strategies and algorithms, in order to consider the advantages, limitations and theory of several techniques. The subjects addressed are line search methods, the restriction of vectors of variables to discrete grids, the use of geometric simplices, conjugate direction procedures, trust region algorithms that form linear or quadratic approximations to the objective function, and simulated annealing. We study the main features of the methods themselves, instead of providing a catalogue of references to published work, because an understanding of these features may be very helpful to future research.

Recent research in inverse problems seeks to develop a mathematically coherent foundation for combining data-driven models, and in particular those based on deep learning, with domain-specific knowledge contained in physical–analytical models. The focus is on solving ill-posed inverse problems that are at the core of many challenging applications in the natural sciences, medicine and life sciences, as well as in engineering and industrial applications. This survey paper aims to give an account of some of the main contributions in data-driven inverse problems.

We give an overview of recent developments concerning the use of adjoint methods in two areas: the a posteriori error analysis of finite element methods for the numerical solution of partial differential equations where the quantity of interest is a functional of the solution, and superconvergent extraction of integral functionals by postprocessing.

We study the entropy stability of difference approximations to nonlinear hyperbolic conservation laws, and related time-dependent problems governed by additional dissipative and dispersive forcing terms. We employ a comparison principle as the main tool for entropy stability analysis, comparing the entropy production of a given scheme against properly chosen entropy-conservative schemes.

To this end, we introduce general families of entropy-conservative schemes, interesting in their own right. The present treatment of such schemes extends our earlier recipe for construction of entropy-conservative schemes, introduced in Tadmor (1987b). The new families of entropy-conservative schemes offer two main advantages, namely, (i) their numerical fluxes admit an explicit, closed-form expression, and (ii) by a proper choice of their path of integration in phase space, we can distinguish between different families of waves within the same computational cell; in particular, entropy stability can be enforced on rarefactions while keeping the sharp resolution of shock discontinuities.

A comparison with the numerical viscosities associated with entropy-conservative schemes provides a useful framework for the construction and analysis of entropy-stable schemes. We employ this framework for a detailed study of entropy stability for a host of first- and second-order accurate schemes. The comparison approach yields a precise characterization of the entropy stability of semi-discrete schemes for both scalar problems and systems of equations.

We extend these results to fully discrete schemes. Here, spatial entropy dissipation is balanced by the entropy production due to time discretization with a suffciently small time-step, satisfying a suitable CFL condition. Finally, we revisit the question of entropy stability for fully discrete schemes using a different approach based on homotopy arguments. We prove entropy stability under optimal CFL conditions.

Knowing thus the Algorithm of this calculus, which I call Differential Calculus, all differential equations can be solved by a common method (Gottfried Wilhelm von Leibniz, 1646–1719).

When, several years ago, I saw for the first time an instrument which, when carried, automatically records the number of steps taken by a pedestrian, it occurred to me at once that the entire arithmetic could be subjected to a similar kind of machinery so that not only addition and subtraction, but also multiplication and division, could be accomplished by a suitably arranged machine easily, promptly and with sure results…. For it is unworthy of excellent men to lose hours like slaves in the labour of calculations, which could safely be left to anyone else if the machine was used…. And now that we may give final praise to the machine, we may say that it will be desirable to all who are engaged in computations which, as is well known, are the managers of financial affairs, the administrators of others estates, merchants, surveyors, navigators, astronomers, and those connected with any of the crafts that use mathematics (Leibniz).

A large number of imaging problems reduce to the optimization of a cost function, with typical structural properties. The aim of this paper is to describe the state of the art in continuous optimization methods for such problems, and present the most successful approaches and their interconnections. We place particular emphasis on optimal first-order schemes that can deal with typical non-smooth and large-scale objective functions used in imaging problems. We illustrate and compare the different algorithms using classical non-smooth problems in imaging, such as denoising and deblurring. Moreover, we present applications of the algorithms to more advanced problems, such as magnetic resonance imaging, multilabel image segmentation, optical flow estimation, stereo matching, and classification.

Optimization problems in which the variable is not a vector but a symmetric matrix which is required to be positive semidefinite have been intensely studied in the last ten years. Part of the reason for the interest stems from the applicability of such problems to such diverse areas as designing the strongest column, checking the stability of a differential inclusion, and obtaining tight bounds for hard combinatorial optimization problems. Part also derives from great advances in our ability to solve such problems efficiently in theory and in practice (perhaps ‘or’ would be more appropriate: the most effective computational methods are not always provably efficient in theory, and vice versa). Here we describe this class of optimization problems, give a number of examples demonstrating its significance, outline its duality theory, and discuss algorithms for solving such problems.

Domain decomposition refers to divide and conquer techniques for solving partial differential equations by iteratively solving subproblems defined on smaller subdomains. The principal advantages include enhancement of parallelism and localized treatment of complex and irregular geometries, singularities and anomalous regions. Additionally, domain decomposition can sometimes reduce the computational complexity of the underlying solution method.

In this article, we survey iterative domain decomposition techniques that have been developed in recent years for solving several kinds of partial differential equations, including elliptic, parabolic, and differential systems such as the Stokes problem and mixed formulations of elliptic problems. We focus on describing the salient features of the algorithms and describe them using easy to understand matrix notation. In the case of elliptic problems, we also provide an introduction to the convergence theory, which requires some knowledge of finite element spaces and elementary functional analysis.

We discuss the finite element approximation of eigenvalue problems associated with compact operators. While the main emphasis is on symmetric problems, some comments are present for non-self-adjoint operators as well. The topics covered include standard Galerkin approximations, non-conforming approximations, and approximation of eigenvalue problems in mixed form. Some applications of the theory are presented and, in particular, the approximation of the Maxwell eigenvalue problem is discussed in detail. The final part tries to introduce the reader to the fascinating setting of differential forms and homological techniques with the description of the Hodge–Laplace eigenvalue problem and its mixed equivalent formulations. Several examples and numerical computations complete the paper, ranging from very basic exercises to more significant applications of the developed theory.

Random matrix theory is now a big subject with applications in many disciplines of science, engineering and finance. This article is a survey specifically oriented towards the needs and interests of a numerical analyst. This survey includes some original material not found anywhere else. We include the important mathematics which is a very modern development, as well as the computational software that is transforming the theory into useful practice.

The heterogeneous multiscale method (HMM), a general framework for designing multiscale algorithms, is reviewed. Emphasis is given to the error analysis that comes naturally with the framework. Examples of finite element and finite difference HMM are presented. Applications to dynamical systems and stochastic simulation algorithms with multiple time scales, spall fracture and heat conduction in microprocessors are discussed.

The structure from motion (SfM) problem in computer vision is to recover the three-dimensional (3D) structure of a stationary scene from a set of projective measurements, represented as a collection of two-dimensional (2D) images, via estimation of motion of the cameras corresponding to these images. In essence, SfM involves the three main stages of (i) extracting features in images (e.g. points of interest, lines, etc.) and matching these features between images, (ii) camera motion estimation (e.g. using relative pairwise camera positions estimated from the extracted features), and (iii) recovery of the 3D structure using the estimated motion and features (e.g. by minimizing the so-called reprojection error). This survey mainly focuses on relatively recent developments in the literature pertaining to stages (ii) and (iii). More specifically, after touching upon the early factorization-based techniques for motion and structure estimation, we provide a detailed account of some of the recent camera location estimation methods in the literature, followed by discussion of notable techniques for 3D structure recovery. We also cover the basics of the simultaneous localization and mapping (SLAM) problem, which can be viewed as a specific case of the SfM problem. Further, our survey includes a review of the fundamentals of feature extraction and matching (i.e. stage (i) above), various recent methods for handling ambiguities in 3D scenes, SfM techniques involving relatively uncommon camera models and image features, and popular sources of data and SfM software.

More than anything else, the increase of computing power seems to stimulate the greed for tackling ever larger problems involving large-scale numerical simulation. As a consequence, the need for understanding something like the intrinsic complexity of a problem occupies a more and more pivotal position. Moreover, computability often only becomes feasible if an algorithm can be found that is asymptotically optimal. This means that storage and the number of floating point operations needed to resolve the problem with desired accuracy remain proportional to the problem size when the resolution of the discretization is refined. A significant reduction of complexity is indeed often possible, when the underlying problem admits a continuous model in terms of differential or integral equations. The physical phenomena behind such a model usually exhibit characteristic features over a wide range of scales. Accordingly, the most successful numerical schemes exploit in one way or another the interaction of different scales of discretization. A very prominent representative is the multigrid methodology; see, for instance, Hackbusch (1985) and Bramble (1993). In a way it has caused a breakthrough in numerical analysis since, in an important range of cases, it does indeed provide asymptotically optimal schemes. For closely related multilevel techniques and a unified treatment of several variants, such as multiplicative or additive subspace correction methods, see Bramble, Pasciak and Xu (1990), Oswald (1994), Xu (1992), and Yserentant (1993). Although there remain many unresolved problems, multigrid or multilevel schemes in the classical framework of finite difference and finite element discretizations exhibit by now a comparatively clear profile. They are particularly powerful for elliptic and parabolic problems.

This review concerns the computation of curvature-dependent interface motion governed by geometric partial differential equations. The canonical problem of mean curvature flow is that of finding a surface which evolves so that, at every point on the surface, the normal velocity is given by the mean curvature. In recent years the interest in geometric PDEs involving curvature has burgeoned. Examples of applications are, amongst others, the motion of grain boundaries in alloys, phase transitions and image processing. The methods of analysis, discretization and numerical analysis depend on how the surface is represented. The simplest approach is when the surface is a graph over a base domain. This is an example of a sharp interface approach which, in the general parametric approach, involves seeking a parametrization of the surface over a base surface, such as a sphere. On the other hand an interface can be represented implicitly as a level surface of a function, and this idea gives rise to the so-called level set method. Another implicit approach is the phase field method, which approximates the interface by a zero level set of a phase field satisfying a PDE depending on a new parameter. Each approach has its own advantages and disadvantages. In the article we describe the mathematical formulations of these approaches and their discretizations. Algorithms are set out for each approach, convergence results are given and are supported by computational results and numerous graphical figures. Besides mean curvature flow, the topics of anisotropy and the higher order geometric PDEs for Willmore flow and surface diffusion are covered.

In the past few years meshless methods for numerically solving partial differential equations have come into the focus of interest, especially in the engineering community. This class of methods was essentially stimulated by difficulties related to mesh generation. Mesh generation is delicate in many situations, for instance, when the domain has complicated geometry; when the mesh changes with time, as in crack propagation, and remeshing is required at each time step; when a Lagrangian formulation is employed, especially with nonlinear PDEs. In addition, the need for flexibility in the selection of approximating functions (e.g., the flexibility to use non-polynomial approximating functions), has played a significant role in the development of meshless methods. There are many recent papers, and two books, on meshless methods; most of them are of an engineering character, without any mathematical analysis.

In this paper we address meshless methods and the closely related generalized finite element methods for solving linear elliptic equations, using variational principles. We give a unified mathematical theory with proofs, briefly address implementational aspects, present illustrative numerical examples, and provide a list of references to the current literature.

The aim of the paper is to provide a survey of a part of this new field, with emphasis on mathematics. We present proofs of essential theorems because we feel these proofs are essential for the understanding of the mathematical aspects of meshless methods, which has approximation theory as a major ingredient. As always, any new field is stimulated by and related to older ideas. This will be visible in our paper.

We consider the efficient evaluation of accurate radiation boundary conditions for time domain simulations of wave propagation on unbounded spatial domains. This issue has long been a primary stumbling block for the reliable solution of this important class of problems. In recent years, a number of new approaches have been introduced which have radically changed the situation. These include methods for the fast evaluation of the exact nonlocal operators in special geometries, novel sponge layers with reflectionless interfaces, and improved techniques for applying sequences of approximate conditions to higher order. For the primary isotropic, constant coefficient equations of wave theory, these new developments provide an essentially complete solution of the numerical radiation condition problem.

In this survey we consider the development and mathematical analysis of numerical methods for kinetic partial differential equations. Kinetic equations represent a way of describing the time evolution of a system consisting of a large number of particles. Due to the high number of dimensions and their intrinsic physical properties, the construction of numerical methods represents a challenge and requires a careful balance between accuracy and computational complexity. Here we review the basic numerical techniques for dealing with such equations, including the case of semi-Lagrangian methods, discrete-velocity models and spectral methods. In addition we give an overview of the current state of the art of numerical methods for kinetic equations. This covers the derivation of fast algorithms, the notion of asymptotic-preserving methods and the construction of hybrid schemes.

Subdivision schemes are efficient computational methods for the design and representation of 3D surfaces of arbitrary topology. They are also a tool for the generation of refinable functions, which are instrumental in the construction of wavelets. This paper presents various flavours of subdivision, seasoned by the personal viewpoint of the authors, which is mainly concerned with geometric modelling. Our starting point is the general setting of scalar multivariate nonstationary schemes on regular grids. We also briefly review other classes of schemes, such as schemes on general nets, matrix schemes, non-uniform schemes and nonlinear schemes. Different representations of subdivision schemes, and several tools for the analysis of convergence, smoothness and approximation order are discussed, followed by explanatory examples.