Past Numerical Analysis Group Internal Seminar

 Wide Neural Networks are well known for their Gaussian Process behaviour. Based upon this fact, an initialisation scheme for the weights and biases of a network preserving some geometrical properties of the input data is presented — The edge-of-chaos. This talk will introduce such a scheme before briefly mentioning a recent contribution related to the edge-of-chaos dynamics of wide randomly initialized low-rank feedforward networks. Formulae for the optimal weight and bias variances are extended from the full-rank to low-rank setting and are shown to follow from multiplicative scaling. The principle second order effect, the variance of the input-output Jacobian, is derived and shown to increase as the rank to width ratio decreases. These results inform practitioners how to randomly initialize feedforward networks with a reduced number of learnable parameters while in the same ambient dimension, allowing reductions in the computational cost and memory constraints of the associated network.

Placeholder entry; date+time TBC. 

Abstract for talk: In this talk, we present a systematic discretization of the Bernstein-Gelfand-Gelfand (BGG) diagrams and complexes over cubical meshes of arbitrary dimension via the use of tensor-product structures of one-dimensional piecewise-polynomial spaces, such as spline and finite element spaces. We demonstrate the construction of the Hessian, the elasticity, and div-div complexes as examples for our construction.

In this talk, we introduce Newton-MR variants for solving nonconvex optimization problems. Unlike the overwhelming majority of Newton-type methods, which rely on conjugate gradient method as the primary workhorse for their respective sub-problems, Newton-MR employs minimum residual (MINRES) method. With certain useful monotonicity properties of MINRES as well as its inherent ability to detect non-positive curvature directions as soon as they arise, we show that our algorithms come with desirable properties including the optimal first and second-order worst-case complexities. Numerical examples demonstrate the performance of our proposed algorithms.

We propose a nematic model for polyatomic gas, intending to study anisotropic phenomena. Such phenomena stem from the orientational degree of freedom associated with the rod-like molecules composing the gas. We adopt as a primer the Curitss-Boltzmann equation. The main difference with respect to Curtiss theory of hard convex body fluids is the fact that the model here presented takes into account the emergence of a nematic ordering. We will also derive from a kinetic point of view an energy functional similar to the Oseen-Frank energy. The application of the Noll-Coleman procedure to derive new expressions for the stress tensor and the couple-stress tensor will lead to a model capable of taking into account anisotropic effects caused by the emergence of a nematic ordering. In the near future, we hope to adopt finite-element discretisations together with multi-scale methods to simulate the integro-differential equation arising from our model.

Coupled differential equations generally present an important algebraic structure.
For example in the incompressible Navier-Stokes equations, the velocity is affected only by the selenoidal part of the applied force.
This structure can be translated naturally by the notion of complex.
One idea is then to exploit this complex structure at the discrete level in the creation of numerical methods.

The goal of the presentation is to expose the notion of complex by motivating its uses. 
We will present in more detail the creation of a scheme for the Navier-Stokes equations and study its properties.
 

The recent advancements in additive manufacturing have enabled the creation of lattice structures with intricate small-scale details. This has led to the need for new techniques in the field of topology optimization that can handle a vast number of design variables. Despite the efforts to develop multi-scale topology optimization techniques, their high computational cost has limited their application. To overcome this challenge, a new technique called dehomogenization has shown promising results in terms of performance and computational efficiency for optimizing compliance problems.

In this talk, we extend the application of the dehomogenization method to stress minimization problems, which are crucial in structural design. The method involves homogenizing the macroscopic response of a proposed family of microstructures. Next, the macroscopic structure is optimized using gradient-based methods while orienting the cells according to the principal stress components. The final step involves dehomogenization of the structure. The proposed methodology also considers singularities in the orientation field by incorporating singular functions in the dehomogenization process. The validity of the methodology is demonstrated through several numerical examples.

At the heart of all quasi-Newton methods is an update rule that enables us to gradually improve the Hessian approximation using the already available gradient evaluations. Theoretical results show that the global performance of optimization algorithms can be improved with higher-order derivatives. This motivates an investigation of generalizations of quasi-Newton update rules to obtain for example third derivatives (which are tensors) from Hessian evaluations. Our generalization is based on the observation that quasi-Newton updates are least-change updates satisfying the secant equation, with different methods using different norms to measure the size of the change. We present a full characterization for least-change updates in weighted Frobenius norms (satisfying an analogue of the secant equation) for derivatives of arbitrary order. Moreover, we establish convergence of the approximations to the true derivative under standard assumptions and explore the quality of the generated approximations in numerical experiments.

Sketch-and-precondition techniques are popular for solving large overdetermined least squares (LS) problems. This is when a right preconditioner is constructed from a randomized 'sketch' of the matrix. In this talk, we will see that the sketch-and-precondition technique is not numerically stable for ill-conditioned LS problems. We propose a modifciation: using an unpreconditioned iterative LS solver on the preconditioned matrix. Provided the condition number of A is smaller than the reciprocal of the unit round-off, we show that this modification ensures that the computed solution has a comparable backward error to the iterative LS solver applied to a well-conditioned matrix. Using smoothed analysis, we model floating-point rounding errors to provide a convincing argument that our modification is expected to compute a backward stable solution even for arbitrarily ill-conditioned LS problems.

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.