A randomised finite element method for elliptic partial differential equations

Yue Wu, Dimitris Kamilis, Nick Polydorides

Published 2019-03-18Version 1

We consider a randomised implementation of the finite element method (FEM) for elliptic partial differential equations on high-dimensional models. This is motivated by the need to expedite the assembly of the associated stiffness matrices as indeed the solution of the resulting linear systems at the many-query context, where the numerical solution is sought for many different parameters. Our approach involves converting the symmetric positive definite FEM system into an over-determined least squares problem, and then projecting the solution onto a low-dimensional subspace. The low-dimensional system can be sketched as a product of two high-dimensional matrices, using some parameter-dependent non-uniform sampling distributions. In this context, we investigate how these distributions relate to those based on statistical leverage scores, and show that the adopted projection enables near optimal sampling. Further we derive a set of bounds for the error components affecting the quality of the proposed solution. Our algorithm is tested on numerical simulations for the elliptic diffusion boundary value problem with Dirichlet and Neumann conditions. Our results show that the randomised FEM approach has on average a ten-fold improvement on the computational times compared to the classical deterministic framework at the expense of a moderately small error.