Past Numerical Analysis Group Internal Seminar

Joint work with Jen Pestana.

There are several classes of random function that appear naturally in mathematical physics, probability, number theory, and other areas of mathematics. I will give a brief overview of some of these random functions and explain what they are and why they are important. Finally, I will explain how I use chebfun to study these functions.
 

Stochastic Hamiltonian systems with multiplicative noise are a mathematical model for many physical systems with uncertainty. For example, they can be used to describe synchrotron oscillations of a particle in a storage ring. Just like their deterministic counterparts, stochastic Hamiltonian systems possess several important geometric features; for instance, their phase flows preserve the canonical symplectic form. When simulating these systems numerically, it is therefore advisable that the numerical scheme also preserves such geometric structures. In this talk we propose a variational principle for stochastic Hamiltonian systems and use it to construct stochastic Galerkin variational integrators. We show that such integrators are indeed symplectic, preserve integrals of motion related to Lie group symmetries, demonstrate superior long-time energy behavior compared to nonsymplectic methods, and they include stochastic symplectic Runge-Kutta methods as a special case. We also analyze their convergence properties and present the results of several numerical experiments. 

Consider the problem of identifying an unknown subspace S from data with erasures and with limited memory available. To estimate S, suppose we group the measurements into blocks and iteratively update our estimate of S with each new block.

In the first part of this talk, we will discuss why estimating S by computing the "running average" of span of these blocks fails in general. Based on the lessons learned, we then propose SNIPE for memory-limited PCA with incomplete data, useful also for streaming data applications. SNIPE provably converges (linearly) to the true subspace, in the absence of noise and given sufficient measurements, and shows excellent performance in simulations. This is joint work with Laura Balzano and Mike Wakin.
 

Nested commutators of differential operators appear frequently in the numerical solution of equations of quantum mechanics. These are expensive to compute with and a significant effort is typically made to avoid such commutators. In the case of Magnus-Lanczos methods, which remain the standard approach for solving Schrödinger equations featuring time-varying potentials, however, it is not possible to avoid the nested commutators appearing in the Magnus expansion.

We show that, when working directly with the undiscretised differential operators, these commutators can be simplified and are fairly benign, cost-wise. The caveat is that this direct approach compromises structure -- we end up with differential operators that are no longer skew-Hermitian under discretisation. This leads to loss of unitarity as well as resulting in numerical instability when moderate to large time steps are involved. Instead, we resort to working with symmetrised differential operators whose discretisation naturally results in preservation of structure, conservation of unitarity and stability
 

Multi-index methods are a generalization of multilevel methods in high dimensional problem and are based on taking mixed first-order differences along all dimensions. With these methods, we can accurately and efficiently compute a quadrature or construct an interpolation where the integrand requires some form of high dimensional discretization. Multi-index methods are related to Sparse Grid methods and the Combination Technique and have been applied to multiple sampling methods, i.e., Monte Carlo, Stochastic Collocation and, more recently, Quasi Monte Carlo.

In this talk, we describe and analyse the Multi-Index Monte Carlo (MIMC) and Multi-Index Stochastic Collocation (MISC) methods for computing statistics of the solution of a PDE with random data. Provided sufficient mixed regularity, MIMC and MISC achieve better complexity than their corresponding multilevel methods. We propose optimization procedures to select the most effective mixed differences to include in these multi-index methods. We also observe that in the optimal case, the convergence rate of MIMC and MISC is only dictated by the convergence of the deterministic solver applied to a one-dimensional spatial problem. We finally show the effectiveness of MIMC and MISC in some computational tests, including PDEs with random coefficients and Stochastic Particle Systems.
 

I will discuss some of the relationships between ODE IVPs, usually solved by marching, and ODE BVPs, usually solved by global discretizations.