Adjoint derivatives reveal the sensitivity of a computer program's output to changes in its inputs. These derivatives are useful as a building block for optimisation, uncertainty quantification, noise estimation, inverse design, etc., in many industrial and scientific applications that use PDE solvers or other codes.

Algorithmic differentiation (AD) is an established method to transform a given computation into its corresponding adjoint computation. One of the key challenges in this process is the efficiency of the resulting adjoint computation. This becomes especially pressing with the increasing use of shared-memory parallelism on multi- and many-core architectures, for which AD support is currently insufficient.

In this talk, I will present an overview of challenges and solutions for the differentiation of shared-memory-parallel code, using two examples: an unstructured-mesh CFD solver, and a structured-mesh stencil kernel, both parallelised with OpenMP. I will show how AD can be used to generate adjoint solvers that scale as well as their underlying original solvers on CPUs and a KNC XeonPhi. The talk will conclude with some recent efforts in using AD and formal verification tools to check the correctness of manually optimised adjoint solvers.

# Past Computational Mathematics and Applications Seminar

Gauss invented Gaussian quadrature following an approach entirely different from the one we now find in textbooks. I will describe leisurely the contents of Gauss's original memoir on quadrature, an impressive piece of mathematics, based on continued fractions, Padé approximation, generating functions, the hypergeometric series and more.

The talk will describe accelerated algorithms for computing full or partial matrix factorizations such as the eigenvalue decomposition, the QR factorization, etc. The key technical novelty is the use of randomized projections to reduce the effective dimensionality of intermediate steps in the computation. The resulting algorithms execute faster on modern hardware than traditional algorithms, and are particularly well suited for processing very large data sets.

The algorithms described are supported by a rigorous mathematical analysis that exploits recent work in random matrix theory. The talk will briefly review some representative theoretical results.

For many applications in science and engineering, the ability to efficiently and accurately approximate solutions to elliptic PDEs dictates what physical phenomena can be simulated numerically. In this seminar, we present a high-order accurate discretization technique for variable coefficient PDEs with smooth coefficients. The technique comes with a nested dissection inspired direct solver that scales linearly or nearly linearly with respect to the number of unknowns. Unlike the application of nested dissection methods to classic discretization techniques, the constant prefactors do not grow with the order of the discretization. The discretization is robust even for problems with highly oscillatory solutions. For example, a problem 100 wavelengths in size can be solved to 9 digits of accuracy with 3.7 million unknowns on a desktop computer. The precomputation of the direct solver takes 6 minutes on a desktop computer. Then applying the computed solver takes 3 seconds. The recent application of the algorithm to inverse media scattering also will be presented.

Structural optimization can be interpreted as the attempt to find the best mechanical structure to support specific load cases respecting some possible constraints. Within this context, topology optimization aims to obtain the connectivity, shape and location of voids inside a prescribed structural design domain. The methods for the design of stiff lightweight structures are well established and can already be used in a specific range of industries where such structures are important, e.g., in aerospace and automobile industries.

In this seminar, we will go through the basic engineering concepts used to quantify and analyze the computational models of mechanical structures. After presenting the motivation, the methods and mathematical tools used in structural topology optimization will be discussed. In our method, an implicit level set function is used to describe the structural boundaries. The optimization problem is approximated by linearization of the objective and constraint equations via Taylor’s expansion. Shape sensitivities are used to evaluate the change in the structural performance due to a shape movement and to feed the mathematical optimiser in an iterative procedure. Recent developments comprising multiscale and Multiphysics problems will be presented and a specific application proposal including acoustic-structure interaction will be discussed.

We describe a convergence acceleration technique for generic optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the base algorithm, providing improved estimates of the solution on the fly, while the original optimization method is running. Numerical experiments are detailed on classical classification problems.

Abstract: We study nonuniform sampling in shift-invariant spaces whose generator is a totally positive function. For a subclass of such generators the sampling theorems can be formulated in analogy to the theorems of Beurling and Landau for bandlimited functions. These results are optimal and validate the heuristic reasonings in the engineering literature. In contrast to the cardinal series, the reconstruction procedures for sampling in a shift-invariant space with a totally positive generator are local and thus accessible to numerical linear algebra.

A subtle connection between sampling in shift-invariant spaces and the theory of Gabor frames leads to new and optimal results for Gabor frames. We show that the set of phase-space shifts of $g$ (totally positive with a Gaussian part) with respect to a rectangular lattice forms a frame, if and only if the density of the lattice is strictly larger than 1. This solves an open problem going backto Daubechies in 1990 for the class of totally positive functions of Gaussian type.

Almost all real-world applications involve a degree of uncertainty. This may be the result of noisy measurements, restrictions on observability, or simply unforeseen events. Since many models in both engineering and the natural sciences make use of partial differential equations (PDEs), it is natural to consider PDEs with random inputs. In this context, passing from modelling and simulation to optimization or control results in stochastic PDE-constrained optimization problems. This leads to a number of theoretical, algorithmic, and numerical challenges.

From a mathematical standpoint, the solution of the underlying PDE is a random field, which in turn makes the quantity of interest or the objective function an implicitly defined random variable. In order to minimize this distributed objective, one can use, e.g., stochastic order constraints, a distributionally robust approach, or risk measures. In this talk, we will make use of risk measures.

After motivating the approach via a model for the mitigation of an airborne pollutant, we build up an analytical framework and introduce some useful risk measures. This allows us to prove the existence of solutions and derive optimality conditions. We then present several approximation schemes for handling non-smooth risk measures in order to leverage existing numerical methods from PDE-constrained optimization. Finally, we discuss solutions techniques and illustrate our results with numerical examples.

During the last decade, the progress in the computational performance of commercial mixed-integer programming solvers have been significant. Part of this success is due to faster computers and better software engineering but a more significant part of it is due to the power of the cutting planes used in these solvers.

In the first part of this talk, we will discuss main components of a MIP solver and describe some classical families of valid inequalities (Gomory mixed integer cuts, mixed integer rounding cuts, split cuts, etc.) that are routinely used in these solvers. In the second part, we will discuss recent progress in cutting plane theory that has not yet made its way to commercial solvers. In particular, we will discuss cuts from lattice-free convex sets and answer a long standing question in the affirmative by deriving a finite cutting plane algorithm for mixed-integer programming.