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.

# Past Computational Mathematics and Applications Seminar

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.

In variational imaging and other inverse problem modeling, regularisation plays a major role. In recent years, high order regularizers such as the total generalised variation, the mean curvature and the Gaussian curvature are increasingly studied and applied, and many improved results over the widely-used total variation model are reported.

Here we first introduce the fractional order derivatives and the total fractional-order variation which provides an alternative regularizer and is not yet formally analysed. We demonstrate that existence and uniqueness properties of the new model can be analysed in a fractional BV space, and, equally, the new model performs as well as the high order regularizers (which do not yet have much theory).

In the usual framework, the algorithms of a fractional order model are not fast due to dense matrices involved. Moreover, written in a Bregman framework, the resulting Sylvester equation with Toeplitz coefficients can be solved efficiently by a preconditioned solver. Further ideas based on adaptive integration can also improve the computational efficiency in a dramatic way.

Numerical experiments will be given to illustrate the advantages of the new regulariser for both restoration and registration problems.

We will present a very general framework for unconstrained stochastic optimization which is based on standard trust region framework using random models. In particular this framework retains the desirable features such step acceptance criterion, trust region adjustment and ability to utilize of second order models. We make assumptions on the stochasticity that are different from the typical assumptions of stochastic and simulation-based optimization. In particular we assume that our models and function values satisfy some good quality conditions with some probability fixed, but can be arbitrarily bad otherwise. We will analyze the convergence and convergence rates of this general framework and discuss the requirement on the models and function values. We will will contrast our results with existing results from stochastic approximation literature. We will finish with examples of applications arising the area of machine learning.