Past Numerical Analysis Group Internal Seminar

We consider the problem of solving nonconvex quadratic optimization problems, potentially with additional integrality constraints on the variables.  Gurobi takes a branch-and-bound approach to solve such problems to global optimality, and in this talk we will review the three main algorithmic components that Gurobi uses:  Convex relaxations based on local linearization, globally valid cutting planes, and nonlinear local optimization heuristics.  We will explain how these parts play together, and discuss some of the implementation details.

The numerical solution of elliptic PDEs is often the most computationally intensive task in large-scale continuum mechanics simulations.  High-order finite element methods can efficiently exploit modern parallel hardware while offering very rapid convergence properties.  As the polynomial degree is increased, the efficient solution of such PDEs becomes difficult. In this talk we introduce preconditioners for high-order discretizations. We build upon the pioneering work of Pavarino, who proved in 1993 that the additive Schwarz method with vertex patches and a low-order coarse space gives a  solver for symmetric and coercive problems that is robust to the polynomial degree. 

However, for very high polynomial degrees it is not feasible to assemble or factorize the matrices for each vertex patch, as the patch matrices contain dense blocks, which couple together all degrees of freedom within a cell. The central novelty of the preconditioners we develop is that they have the same time and space complexity as sum-factorized operator application on unstructured meshes of tensor-product cells, i.e., we can solve $A x=b$ with the same complexity as evaluating $b-A x$. Our solver relies on new finite elements for the de Rham complex that enable the blocks in the stiffness matrix corresponding to the cell interiors to become diagonal for scalar PDEs or block diagonal for vector-valued PDEs.  With these new elements, the patch problems are as sparse as a low-order finite difference discretization, while having a sparser Cholesky factorization. In the non-separable case, themethod can be applied as a preconditioner by approximating the problem with a separable surrogate.  Through the careful use of incomplete factorizations and choice of space decomposition we achieve optimal fill-in in the patch factors, ultimately allowing for optimal-complexity storage and computational cost across the setup and solution stages.

We demonstrate the approach by solving the Riesz maps of $H^1$, $H(\mathrm{curl})$, and $H(\mathrm{div})$ in three dimensions at $p = 15$.

We investigate the theoretical properties of subsampling and hashing as tools for approximate Euclidean norm-preserving embeddings for vectors with (unknown) additive Gaussian noises. Such embeddings are called Johnson-Lindenstrauss embeddings due to their celebrated lemma. Previous work shows that as sparse embeddings, if a comparable embedding dimension to the Gaussian matrices is required, the success of subsampling and hashing closely depends on the $l_\infty$ to $l_2$ ratios of the vectors to be mapped. This paper shows that the presence of noise removes such constrain in high-dimensions; in other words, sparse embeddings such as subsampling and hashing with comparable embedding dimensions to dense embeddings have similar norm-preserving dimensionality-reduction properties, regardless of the $l_\infty$ to $l_2$ ratios of the vectors to be mapped. The key idea in our result is that the noise should be treated as information to be exploited, not simply a nuisance to be removed. Numerical illustrations show better performances of sparse embeddings in the presence of noise.

In this talk we are presenting a new approach for compatible finite element discretisations for atmospheric flows on a terrain following mesh. In classical compatible finite element discretisations, the H(div)-velocity space involves the application of Piola transforms when mapping from a reference element to the physical element in order to guarantee normal continuity. In the case of a terrain following mesh, this causes an undesired coupling of the horizontal and vertical velocity components. We are proposing a new finite element space, that drops the Piola transform. For solving the equations we introduce a hybridisable formulation with trace variables supported on horizontal cell faces in order to enforce the normal continuity of the velocity in the solution. Alongside the discrete formulation for various fluid equations we discuss solver approaches that are compatible with them and present our latest numerical results.

While scattering problems are posed on unbounded domains, volumetric discretizations typically require truncating the domain at a finite distance, closing the system with some sort of boundary condition.  These conditions typically suffer from some deficiency, such as perturbing the boundary value problem to be solved or changing the character of the operator so that the discrete system is difficult to solve with iterative methods.

We introduce a new technique for the Helmholtz problem, based on using the Green formula representation of the solution at the artificial boundary.  Finite element discretization of the resulting system gives optimal convergence estimates.  The resulting algebraic system can be solved effectively with a matrix-free GMRES implementation, preconditioned with the local part of the operator.  Extensions to the Morse-Ingard problem, a coupled system of pressure/temperature equations arising in modeling trace gas sensors, will also be given.

In this talk I will present a new class of algorithms for separable nonlinear inverse problems based on inexact Krylov methods. In particular, I will focus in semi-blind deblurring applications. In this setting, inexactness stems from the uncertainty in the parameters defining the blur, which are computed throughout the iterations. After giving a brief overview of the theoretical properties of these methods, as well as strategies to monitor the amount of inexactness that can be tolerated, the performance of the algorithms will be shown through numerical examples. This is joint work with Silvia Gazzola (University of Bath).

Rational functions are able to approximate functions containing branch point singularities with a root-exponential convergence rate. These appear for example in the solution of boundary value problems on domains containing corners or edges. Results from Newman in 1964 indicate that the poles of the optimal rational approximant are exponentially clustered near the branch point singularities. Trefethen and collaborators use this knowledge to linearize the approximation problem by fixing the poles in advance, giving rise to the Lightning approximation. The resulting approximation set is however highly ill-conditioned, which raises the question of stability. We show that augmenting the approximation set with polynomial terms greatly improves stability. This observation leads to a  decoupling of the approximation problem into two regimes, related to the singular and the smooth behaviour of the function. In addition, adding polynomial terms to the approximation set can result in a significant increase in convergence speed. The convergence rate is however very sensitive to the speed at which the clustered poles approach the singularity.

Most algorithms for computing a matrix function $f(A)$ are based on finding a rational (or polynomial) approximant $r(A)≈f(A)$ to the scalar function on the spectrum of $A$. These functions are often in a composite form, that is, $f(z)≈r(z)=r_k(⋯r_2(r_1(z)))$ (where $k$ is the number of compositions, which is often the iteration count, and proportional to the computational cost); this way $r$ is a rational function whose degree grows exponentially in $k$. I will review algorithms that fall into this category and highlight the remarkable power of composite (rational) functions.

An occupational hazard of mathematicians is the investigation of objects that are "optimal" in a mathematically precise sense, yet may be far from optimal in practice. This talk will discuss an extreme example of this effect: Gauss-Hermite quadrature on the real line. For large numbers of quadrature points, Gauss-Hermite quadrature is a very poor method of integration, much less efficient than simply truncating the interval and applying Gauss-Legendre quadrature or the periodic trapezoidal rule. We will present a theorem quantifying this difference and explain where the standard notion of optimality has failed.

Motivated by the physical relevance of many Hodge Laplace-type PDEs from the finite element exterior calculus, we analyse the Hodge Laplacian boundary value problem arising from the strain space in the linear elasticity complex, an exact sequence of function spaces naturally arising in several areas of continuum mechanics. We propose a discretisation based on the adaptation of discontinuous Galerkin FEM for the incompatibility operator $\mathrm{inc} := \mathrm{rot}\circ\mathrm{rot}$, using the symmetric-tensor-valued Regge finite element to discretise  the strain field; via the 'Regge calculus', this element has already been successfully applied to discretise another metric tensor, namely that arising in general relativity. Of central interest is the characterisation of the associated Sobolev space $H(\mathrm{inc};\mathbb{R}^{d\times d}_{\mathrm{sym}})$. Building on the pioneering work of van Goethem and coauthors, we also discuss promising connections between functional analysis of the $\mathrm{inc}$ operator and Kröner's theory of intrinsic elasticity in the presence of defects.

This is based on ongoing work with Dr Kaibo Hu.

Regularization of linear least squares problems is necessary in a variety of contexts. However, the optimal regularization parameter is usually unknown a priori and is often to be determined in an ad hoc manner, which may involve solving the problem for multiple regularization parameters. In this talk, we will discuss three randomized algorithms, building on the sketch-and-precondition framework in randomized numerical linear algebra (RNLA), to efficiently solve this set of problems. In particular, we consider preconditioners for a set of Tikhonov regularization problems to be solved iteratively. The first algorithm is a Cholesky-based algorithm employing a single sketch for multiple parameters; the second algorithm is SVD-based and improves the computational complexity by requiring a single decomposition of the sketch for multiple parameters. Finally, we introduce an algorithm capable of exploiting low-rank structure (specifically, low statistical dimension), requiring a single sketch and a single decomposition to compute multiple preconditioners with low-rank structure. This algorithm avoids the Gram matrix, resulting in improved stability as compared to related work.

Time-optimal control can be used to improve driving efficiency for autonomous
vehicles and it enables us explore vehicle and driver behaviour in extreme
situations. Due to the computational cost and limited scope of classical
optimal control methods we have seen new interest in applying reinforcement
learning algorithms to autonomous driving tasks.
In this talk we present methods for translating time-optimal vehicle control
problems into reinforcement learning environments. For this translation we
construct a sequence of environments, starting from the closest representation
of our optimisation problem, and gradually improve the environments reward
signal and feature quality. The trained agents we obtain are able to generalise
across different race tracks and obtain near optimal solutions, which can then
be used to speed up the solution of classical time-optimal control problems.

Many problems in engineering can be understood as controlling the bifurcation structure of a given device. For example, one may wish to delay the onset of instability, or bring forward a bifurcation to enable rapid switching between states. In this talk, we will describe a numerical technique for controlling the bifurcation diagram of a nonlinear partial differential equation by varying the shape of the domain or a parameter in the equation. Our aim is to delay or advance a given branch point to a target parameter value. The algorithm consists of solving an optimization problem constrained by an augmented system of equations that characterize the location of the branch points. The flexibility and robustness of the method also allow us to advance or delay a Hopf bifurcation to a target value of the bifurcation parameter, as well as controlling the oscillation frequency. We will apply this technique on systems arising from biology, fluid dynamics, and engineering, such as the FitzHugh-Nagumo model, Navier-Stokes, and hyperelasticity equations.

This talk is about the mathematics behind an artistic project focusing on the vibrations of soap films.

We investigate the maximum distance of a rank-two tensor to rank-one tensors. An equivalent problem is given by the minimal ratio of spectral and Frobenius norm of a tensor. For matrices the distance of a rank k matrix to a rank r matrices is determined by its singular values, but since there is a lack of a fitting analog of the singular value decomposition for tensors, this question is more difficult in the regime of tensors.
 

iii) identify a special class of correlated compressors based on the idea of random permutations, for which we coin the term PermK. The use of this technique results in the strict improvement on the previous MARINA rate. In the low Hessian variance regime, the improvement can be as large as √n, when d > n, and 1 + √d/n, when n<=d, where n is the number of workers and d is the number of parameters describing the model we are learning.

We introduce meta-factorization, a theory that describes matrix decompositions as solutions of linear matrix equations: the projector and the reconstruction equation. Meta-factorization reconstructs known factorizations, reveals their internal structures, and allows for introducing modifications, as illustrated with SVD, QR, and UTV factorizations. The prospect of meta-factorization also provides insights into computational aspects of generalized matrix inverses and randomized linear algebra algorithms. The relations between the Moore-Penrose pseudoinverse, generalized Nyström method, and the CUR decomposition are revealed here as an illustration. Finally, meta-factorization offers hints on the structure of new factorizations and provides the potential of creating them. 

Mass transfer in multicomponent systems occurs through convection and diffusion. For a viscous Newtonian flow, convection may be modelled using the Navier–Stokes equations, whereas the diffusion of multiple species within a common phase may be described by the generalised Onsager–Stefan–Maxwell equations. In this talk we present a novel finite element formulation which fully couples convection and diffusion with these equations. In the regime of vanishing Reynolds number, we use the principles of linear irreversible dynamics to formulate a saddle point system which leads to a stable formulation and a convergent discretisation. The wide scope of applications for this novel numerical method is illustrated by considering transport of oxygen through the lungs, gas separation processes, mixing of water and methanol and salt transport in electrolytes.

The placenta is the essential organ of maternal-fetal interactions, where nutrient, oxygen, and waste exchange occur. In recent studies, differences in the morphology of the placental chorionic surface vascular network (PCSVN) have been associated with developmental disorders such as autism. This suggests that the PCSVN could potentially serve as a biomarker for the early diagnosis and treatment of autism. Studying PCSVN features in large cohorts requires a reliable and automated mechanism to extract the vascular networks. In this talk, we present a method for PCSVN extraction. Our algorithm builds upon a directional multiscale mathematical framework based on a combination of shearlets and Laplacian eigenmaps and can isolate vessels with high success in high-contrast images such as those produced in CT scans. 

TBA.