Title: Sketching algorithms for the Galerkin finite element method
Authors: Nick Polydorides - University of Edinburgh (United Kingdom) [presenting]
Abstract: Some methodologies are discussed for sampling the Galerkin system of equations arising during the numerical solution of elliptic partial differential equations on high-dimensional models. We show that the assembly of the coefficients matrix and right-hand side vector in the resulting linear Galerkin system can be formulated as a high-dimensional sum of sparse, low-rank matrices which we attempt to approximate by sampling. It turns out that the optimal sampling distribution involves the parameters of the PDE and some geometric properties of the numerical model. To reduce the computational complexity in solving the sketched system we explore two approaches: projecting the Galerkin equations onto a low-dimensional subspace as well as casting the problem as a least squares problem. For both cases we provide error bounds based on the optimal sampling distributions and sampling budgets, and illustrate the performance of the algorithms using numerical experiments.