Scientific Computing and Numerics (SCAN) Seminar

Marissa GeeJohn RyanCornell University
Optimal Path-Planning in the Presence of Random Breakdowns / Automatic Analytic Expansions for Kernel Matrix Approximation

Monday, December 6, 2021 - 1:30pm
Gates G13

Title: Optimal Path-Planning in the Presence of Random Breakdowns
Abstract: Path-planning is a well-studied problem in continuous optimal control, but existing methods of accounting for undesirable terrain and vehicle breakdowns are largely heuristic. In this talk, we will present a path-planning model based on a single performance metric that accurately and systematically accounts for the potential (spatially inhomogeneous) cost of breakdowns and repairs. We will assume that these breakdowns happen stochastically with a known (and potentially spatially inhomogenous) rate, in which case our model is an example of a broader class of control problems known as piecewise-deterministic Markov processes (PDMPs). We will use the framework of PDMPs to present a governing system of Hamilton-Jacobi-Bellman PDEs which can be solved to recover the optimal policy for all starting locations. Finally, we will discuss an efficient iterative numerical method for solving this system that makes use of existing fast methods for HJB equations, as well as hybrid value-policy iterations, and will illustrate its convergence through computational experiments. 

Title: Automatic Analytic Expansions for Kernel Matrix Approximation
Abstract: A common limitation of kernel methods are computations involving the kernel matrix that naively scale quadratically (e.g., constructing the kernel matrix and matrix-vector multiplication) or cubically (solving linear systems) with the size of the data set N. We present the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications (MVMs) for datasets in moderate dimensions with quasilinear complexity. Typically, analytically grounded fast multiplication methods (e.g. FMM, FGT) require specialized development for specific kernels. In contrast, our scheme is based on auto-differentiation and automated symbolic computations that leverage the analytical structure of the underlying kernel. This allows the FKT to be easily applied to a broad class of kernels, including Gaussian, Matern, and Rational Quadratic covariance functions and physically motivated Green's functions, including those of the Laplace and Helmholtz equations. See preprint: