Current methods for the automatic generation of grids are reviewed. The approaches to grid generation that are discussed include Cartesian, multi-block-structured, overlapping and unstructured. Emphasis is placed on those methods that can create high-quality grids appropriate for the solution of equations of a hyperbolic nature, such as those that arise in fluid dynamics. Numerous figures illustrate the different grid generation techniques.

Many crucial scientific computing applications, ranging from national security to medical advances, rely on high-performance linear algebra algorithms and technologies, underscoring their importance and broad impact. Here we present the state-of-the-art design and implementation practices for the acceleration of the predominant linear algebra algorithms on large-scale accelerated multicore systems. Examples are given with fundamental dense linear algebra algorithms – from the LU, QR, Cholesky, and LDLT factorizations needed for solving linear systems of equations, to eigenvalue and singular value decomposition (SVD) problems. The implementations presented are readily available via the open-source PLASMA and MAGMA libraries, which represent the next generation modernization of the popular LAPACK library for accelerated multicore systems.

To generate the extreme level of parallelism needed for the efficient use of these systems, algorithms of interest are redesigned and then split into well-chosen computational tasks. The task execution is scheduled over the computational components of a hybrid system of multicore CPUs with GPU accelerators and/or Xeon Phi coprocessors, using either static scheduling or light-weight runtime systems. The use of light-weight runtime systems keeps scheduling overheads low, similar to static scheduling, while enabling the expression of parallelism through sequential-like code. This simplifies the development effort and allows exploration of the unique strengths of the various hardware components. Finally, we emphasize the development of innovative linear algebra algorithms using three technologies – mixed precision arithmetic, batched operations, and asynchronous iterations – that are currently of high interest for accelerated multicore systems.

The present review paper has several objectives. Its primary aim is to give an idea of the general features of virtual element methods (VEMs), which were introduced about a decade ago in the field of numerical methods for partial differential equations, in order to allow decompositions of the computational domain into polygons or polyhedra of a very general shape.

Nonetheless, the paper is also addressed to readers who have already heard (and possibly read) about VEMs and are interested in gaining more precise information, in particular concerning their application in specific subfields such as ${C}^1$ -approximations of plate bending problems or approximations to problems in solid and fluid mechanics.

One of the main challenges in molecular dynamics is overcoming the ‘timescale barrier’: in many realistic molecular systems, biologically important rare transitions occur on timescales that are not accessible to direct numerical simulation, even on the largest or specifically dedicated supercomputers. This article discusses how to circumvent the timescale barrier by a collection of transfer operator-based techniques that have emerged from dynamical systems theory, numerical mathematics and machine learning over the last two decades. We will focus on how transfer operators can be used to approximate the dynamical behaviour on long timescales, review the introduction of this approach into molecular dynamics, and outline the respective theory, as well as the algorithmic development, from the early numerics-based methods, via variational reformulations, to modern data-based techniques utilizing and improving concepts from machine learning. Furthermore, its relation to rare event simulation techniques will be explained, revealing a broad equivalence of variational principles for long-time quantities in molecular dynamics. The article will mainly take a mathematical perspective and will leave the application to real-world molecular systems to the more than 1000 research articles already written on this subject.

We survey recent work on approximation algorithms for computing degree-constrained subgraphs in graphs and their applications in combinatorial scientific computing. The problems we consider include maximization versions of cardinality matching, edge-weighted matching, vertex-weighted matching and edge-weighted $b$-matching, and minimization versions of weighted edge cover and $b$-edge cover. Exact algorithms for these problems are impractical for massive graphs with several millions of edges. For each problem we discuss theoretical foundations, the design of several linear or near-linear time approximation algorithms, their implementations on serial and parallel computers, and applications. Our focus is on practical algorithms that yield good performance on modern computer architectures with multiple threads and interconnected processors. We also include information about the software available for these problems.

In this paper we review results on asymptotic stability of stationary states of PDEs. After scaling, our normal form is ut = Pu + ε f(u, ux,…) + F(x, t), where the (vector-valued) function u(x, t) depends on the space variable x and time t. The differential operator P is linear, F(x, t) is a smooth forcing, which decays to zero for t → ∞, and εf(u, …) is a nonlinear perturbation. We will discuss conditions that ensure u → 0 for t → ∞ when |ε| is sufficiently small. If this holds, we call the problem asymptotically stable.

While there are many approaches to show asymptotic stability, we mainly concentrate on the resolvent technique. However, comparisons with the Lyapunov technique will also be given. The emphasis on the resolvent technique is motivated by the recent interest in pseudospectra.

This article surveys research on the application of compatible finite element methods to large-scale atmosphere and ocean simulation. Compatible finite element methods extend Arakawa’s C-grid finite difference scheme to the finite element world. They are constructed from a discrete de Rham complex, which is a sequence of finite element spaces linked by the operators of differential calculus. The use of discrete de Rham complexes to solve partial differential equations is well established, but in this article we focus on the specifics of dynamical cores for simulating weather, oceans and climate. The most important consequence of the discrete de Rham complex is the Hodge–Helmholtz decomposition, which has been used to exclude the possibility of several types of spurious oscillations from linear equations of geophysical flow. This means that compatible finite element spaces provide a useful framework for building dynamical cores. In this article we introduce the main concepts of compatible finite element spaces, and discuss their wave propagation properties. We survey some methods for discretizing the transport terms that arise in dynamical core equation systems, and provide some example discretizations, briefly discussing their iterative solution. Then we focus on the recent use of compatible finite element spaces in designing structure preserving methods, surveying variational discretizations, Poisson bracket discretizations and consistent vorticity transport.

This article, a companion to the article by Philippe G. Ciarlet on the mathematical modelling of shells also in this issue of Acta Numerica, focuses on numerical issues raised by the analysis of shells.

Finite element procedures are widely used in engineering practice to analyse the behaviour of shell structures. However, the concept of ‘shell finite element’ is still somewhat fuzzy, as it may correspond to very different ideas and techniques in various actual implementations. In particular, a significant distinction can be made between shell elements that are obtained via the discretization of shell models, and shell elements – such as the general shell elements – derived from 3D formulations using some kinematic assumptions, without the use of any shell theory. Our first objective in this paper is to give a unified perspective of these two families of shell elements. This is expected to be very useful as it paves the way for further thorough mathematical analyses of shell elements. A particularly important motivation for this is the understanding and treatment of the deficiencies associated with the analysis of thin shells (among which is the locking phenomenon). We then survey these deficiencies, in the framework of the asymptotic behaviour of shell models. We conclude the article by giving some detailed guidelines to numerically assess the performance of shell finite elements when faced with these pathological phenomena, which is essential for the design of improved procedures.

We introduce basic ideas of binary separation by a linear hyperplane, which is a technique exploited in the support vector machine (SVM) concept. This is a decision-making tool for pattern recognition and related problems. We describe a fundamental standard problem (SP) and show how this is used in most existing research to develop a dual-based algorithm for its solution. This algorithm is shown to be deficient in certain aspects, and we develop a new primal-based SQP-like algorithm, which has some interesting features. Most practical SVM problems are not adequately handled by a linear hyperplane. We describe the nonlinear SVM technique, which enables a nonlinear separating surface to be computed, and we propose a new primal algorithm based on the use of low-rank Cholesky factors.

It may be, however, that exact separation is not desirable due to the presence of uncertain or mislabelled data. Dealing with this situation is the main challenge in developing suitable algorithms. Existing dual-based algorithms use the idea of L1 penalties, which has merit. We suggest how penalties can be incorporated into a primal-based algorithm. Another aspect of practical SVM problems is often the huge size of the data set, which poses severe challenges both for software package development and for control of ill-conditioning. We illustrate some of these issues with numerical experiments on a range of problems.

We present an overviewof the basic theory, modern optimal transportation extensions and recent algorithmic advances. Selected modelling and numerical applications illustrate the impact of optimal transportation in numerical analysis.

Floating-point numbers have an intuitive meaning when it comes to physics-based numerical computations, and they have thus become the most common way of approximating real numbers in computers. The IEEE-754 Standard has played a large part in making floating-point arithmetic ubiquitous today, by specifying its semantics in a strict yet useful way as early as 1985. In particular, floating-point operations should be performed as if their results were first computed with an infinite precision and then rounded to the target format. A consequence is that floating-point arithmetic satisfies the ‘standard model’ that is often used for analysing the accuracy of floating-point algorithms. But that is only scraping the surface, and floating-point arithmetic offers much more.

In this survey we recall the history of floating-point arithmetic as well as its specification mandated by the IEEE-754 Standard. We also recall what properties it entails and what every programmer should know when designing a floating-point algorithm. We provide various basic blocks that can be implemented with floating-point arithmetic. In particular, one can actually compute the rounding error caused by some floating-point operations, which paves the way to designing more accurate algorithms. More generally, properties of floating-point arithmetic make it possible to extend the accuracy of computations beyond working precision.

Schwarz methods use a decomposition of the computational domain into subdomains and need to impose boundary conditions on the subdomain boundaries. In domain truncation one restricts the unbounded domain to a bounded computational domain and must also put boundary conditions on the computational domain boundaries. In both fields there are vast bodies of literature and research is very active and ongoing. It turns out to be fruitful to think of the domain decomposition in Schwarz methods as a truncation of the domain onto subdomains. Seminal precursors of this fundamental idea are papers by Hagstrom, Tewarson and Jazcilevich (1988), Després (1990) and Lions (1990). The first truly optimal Schwarz method that converges in a finite number of steps was proposed by Nataf (1993), and used precisely transparent boundary conditions as transmission conditions between subdomains. Approximating these transparent boundary conditions for fast convergence of Schwarz methods led to the development of optimized Schwarz methods – a name that has become common for Schwarz methods based on domain truncation. Compared to classical Schwarz methods, which use simple Dirichlet transmission conditions and have been successfully used in a wide range of applications, optimized Schwarz methods are much less well understood, mainly due to their more sophisticated transmission conditions.

A key application of Schwarz methods with such sophisticated transmission conditions turned out to be time-harmonic wave propagation problems, because classical Schwarz methods simply do not work in this case. The past decade has given us many new Schwarz methods based on domain truncation. One review from an algorithmic perspective (Gander and Zhang 2019) showed the equivalence of many of these new methods to optimized Schwarz methods. The analysis of optimized Schwarz methods, however, is lagging behind their algorithmic development. The general abstract Schwarz framework cannot be used for the analysis of these methods, and thus there are many open theoretical questions about their convergence. Just as for practical multigrid methods, Fourier analysis has been instrumental for understanding the convergence of optimized Schwarz methods and for tuning their transmission conditions. Similar to local Fourier mode analysis in multigrid, the unbounded two-subdomain case is used as a model for Fourier analysis of optimized Schwarz methods due to its simplicity. Many aspects of the actual situation, e.g. boundary conditions of the original problem and the number of subdomains, were thus neglected in the unbounded two-subdomain analysis. While this gave important insight, new phenomena beyond the unbounded two-subdomain models were discovered.

This present situation is the motivation for our survey: to give a comprehensive review and precise exploration of convergence behaviours of optimized Schwarz methods based on Fourier analysis, taking into account the original boundary conditions, many-subdomain decompositions and layered media. We consider as our model problem the operator $-\Delta + \eta $ in the diffusive case $\eta>0$ (screened Laplace equation) or the oscillatory case $\eta <0$ (Helmholtz equation), in order to show the fundamental difference in behaviour of Schwarz solvers for these problems. The transmission conditions we study include the lowest-order absorbing conditions (Robin), and also more advanced perfectly matched layers (PMLs), both developed first for domain truncation. Our intensive work over the last two years on this review has led to several new results presented here for the first time: in the bounded two-subdomain analysis for the Helmholtz equation, we see strong influence of the original boundary conditions imposed on the global problem on the convergence factor of the Schwarz methods, and the asymptotic convergence factors with small overlap can differ from the unbounded two-subdomain analysis. In the many-subdomain analysis, we find the scaling with the number of subdomains, e.g. when the subdomain size is fixed, robust convergence of the double-sweep Schwarz method for the free-space wave problem, either with fixed overlap and zeroth-order Taylor conditions or with a logarithmically growing PML, and we find that Schwarz methods with PMLs work like smoothers that converge faster for higher Fourier frequencies; in particular, for the free-space wave problem, plane waves (in the error) passing through interfaces at a right angle converge more slowly. In addition to our main focus on analysis in Sections 2 and 3, we start in Section 1 with an expository historical introduction to Schwarz methods, and in Section 4 we give a brief interpretation of the recently proposed optimal Schwarz methods for decompositions with cross-points from the viewpoint of transmission conditions. We conclude in Section 5 with a summary of open research problems. In Appendix A we provide a Matlab program for a block LU form of an optimal Schwarz method with cross-points, and in Appendix B we give the Maple program for the two-subdomain Fourier analysis.

The objective of this article is to lay down the proper mathematical foundations of the two-dimensional theory of linearly elastic shells. To this end, it provides, without any recourse to any a priori assumptions of a geometrical or mechanical nature, a mathematical justification of two-dimensional linear shell theories, by means of asymptotic methods, with the thickness as the ‘small’ parameter.

A major virtue of this approach is that it naturally leads to precise mathematical definitions of linearly elastic ‘membrane’ and ‘flexural’ shells. Another noteworthy feature is that it highlights in particular the role played by two fundamental tensors, each associated with a displacement field of the middle surface, the linearized change of metric and linearized change of curvature tensors.

More specifically, under fundamentally distinct sets of assumptions bearing on the geometry of the middle surface, on the boundary conditions, and on the order of magnitude of the applied forces, it is shown that the three-dimensional displacements, once properly scaled, converge (in H1, or in L2, or in ad hoc completions) as the thickness approaches zero towards a ‘two-dimensional’ limit that satisfies either the linear two-dimensional equations of a ‘membrane’ shell (themselves divided into two subclasses) or the linear two-dimensional equations of a ‘flexural’ shell. Note that this asymptotic analysis automatically provides in each case the ‘limit’ two-dimensional equations, together with the function space over which they are well-posed.

The linear two-dimensional shell equations that are most commonly used in numerical simulations, namely Koiter's equations, Naghdi's equations, and ‘shallow’ shell equations, are then carefully described, mathematically analysed, and likewise justified by means of asymptotic analyses.

The existence and uniqueness of solutions to each one of these linear two-dimensional shell equations are also established by means of crucial inequalities of Korn's type on surfaces, which are proved in detail at the beginning of the article.

This article serves as a mathematical basis for the numerically oriented companion article by Dominique Chapelle, also in this issue of Acta Numerica.

In recent decades, condition numbers have joined forces with probabilistic analysis to give rise to a form of condition-based analysis of algorithms. In this paper we survey how this analysis is done via a number of examples. We precede this catalogue of examples with short primers on both condition numbers and probabilistic analyses.

We describe the burgeoning field of numerical relativity, which aims to solve Einstein's equations of general relativity numerically. The field presents many questions that may interest numerical analysts, especially problems related to nonlinear partial differential equations: elliptic systems, hyperbolic systems, and mixed systems. There are many novel features, such as dealing with boundaries when black holes are excised from the computational domain, or how even to pose the problem computationally when the coordinates must be determined during the evolution from initial data. The most important unsolved problem is that there is no known general 3-dimensional algorithm that can evolve Einstein's equations with black holes that is stable. This review is meant to be an introduction that will enable numerical analysts and other computational scientists to enter the field. No previous knowledge of special or general relativity is assumed.

In this article we will focus on only a small part of financial mathematics, namely the use of partial differential equations for pricing futures. Even within this narrow range it is hard to be systematic and complete, or even to do better than existing books such as Wilmott, Howison and Dewynne (1995), Achdou and Pironneau (2005), or software manuals such as Lapeyre, Martini and Sulem (2010). So this article may be valuable only to the extent that it reflects ten years of teaching, conferences and interaction with the protagonists of financial mathematics.

Also, because the theory of partial differential equations is not always well known, we have chosen a pragmatic approach and left out the details of the theory or the proofs of some results, and refer the reader to other books. The numerical algorithms, on the other hand, are given in detail.

Numerical methods are usually constructed for solving mathematical problems such as differential equations or optimization problems. In this contribution we discuss the fact that numerical methods, applied inversely, were also important in establishing these models. We show in detail the discovery of the laws of planetary motion by Kepler and Newton, which stood at the beginning of modern science. The 400th anniversary of the publication of Kepler's laws (1609) is a good occasion for this investigation.

Low-rank tensor representations can provide highly compressed approximations of functions. These concepts, which essentially amount to generalizations of classical techniques of separation of variables, have proved to be particularly fruitful for functions of many variables. We focus here on problems where the target function is given only implicitly as the solution of a partial differential equation. A first natural question is under which conditions we should expect such solutions to be efficiently approximated in low-rank form. Due to the highly nonlinear nature of the resulting low-rank approximations, a crucial second question is at what expense such approximations can be computed in practice. This article surveys basic construction principles of numerical methods based on low-rank representations as well as the analysis of their convergence and computational complexity.

This overview is devoted to splitting methods, a class of numerical integrators intended for differential equations that can be subdivided into different problems easier to solve than the original system. Closely connected with this class of integrators are composition methods, in which one or several low-order schemes are composed to construct higher-order numerical approximations to the exact solution. We analyse in detail the order conditions that have to be satisfied by these classes of methods to achieve a given order, and provide some insight about their qualitative properties in connection with geometric numerical integration and the treatment of highly oscillatory problems. Since splitting methods have received considerable attention in the realm of partial differential equations, we also cover this subject in the present survey, with special attention to parabolic equations and their problems. An exhaustive list of methods of different orders is collected and tested on simple examples. Finally, some applications of splitting methods in different areas, ranging from celestial mechanics to statistics, are also provided.

We propose a geometric framework to describe and analyse a wide array of operator splitting methods for solving monotone inclusion problems. The initial inclusion problem, which typically involves several operators combined through monotonicity-preserving operations, is seldom solvable in its original form. We embed it in an auxiliary space, where it is associated with a surrogate monotone inclusion problem with a more tractable structure and which allows for easy recovery of solutions to the initial problem. The surrogate problem is solved by successive projections onto half-spaces containing its solution set. The outer approximation half-spaces are constructed by using the individual operators present in the model separately. This geometric framework is shown to encompass traditional methods as well as state-of-the-art asynchronous block-iterative algorithms, and its flexible structure provides a pattern to design new ones.