A sketched finite element method for elliptic models
A sketched finite element method for elliptic models
复制标题
椭圆模型的有限元草图方法
DOI：
10.1016/j.cma.2020.112933
复制
发表时间：
2020
影响因子：
7.2
通讯作者：
Lung R
中科院分区：
文献类型：
--
作者：
Lung R
我们考虑在高维模型上实现椭圆型偏微分方程解的有限元方法。出于在实时模拟和预测中的应用，我们提出了一种算法，该算法包括将有限元解投影到低维子空间，并使用随机采样来绘制约化方程。我们表明，基于与离散拉普拉斯算子相关的高矩阵的杠杆分数的抽样分布可以获得近乎最优的性能和显著的加速比。我们用高概率满足容错规范所需的样本数来表示算法的复杂性，并给出了草图解与高维解之间距离的一个上界。我们的分析表明，投影不仅降低了问题的维度，而且使减少的系统对草图误差的影响得到了规律化。我们的数值模拟表明，速度提高了两个数量级，但预测精度略有下降。
We consider a sketched implementation of the finite element method for elliptic partial differential equations on high-dimensional models. Motivated by applications in real-time simulation and prediction we propose an algorithm that involves projecting the finite element solution onto a low-dimensional subspace and sketching the reduced equations using randomised sampling. We show that a sampling distribution based on the leverage scores of a tall matrix associated with the discrete Laplacian operator, can achieve nearly optimal performance and a significant speedup. We derive an expression of the complexity of the algorithm in terms of the number of samples that are necessary to meet an error tolerance specification with high probability, and an upper bound for the distance between the sketched and the high-dimensional solutions. Our analysis shows that the projection not only reduces the dimension of the problem but also regularises the reduced system against sketching error. Our numerical simulations suggest speed improvements of two orders of magnitude in exchange for a small loss in the accuracy of the prediction.