A sketched finite element method for elliptic models
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-dimensio...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2020
|
| _version_ | 1797082428103196672 |
|---|---|
| author | Lung, R Wu, Y Kamilis, D Polydorides, N |
| author_facet | Lung, R Wu, Y Kamilis, D Polydorides, N |
| author_sort | Lung, R |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:27:59Z |
| format | Journal article |
| id | oxford-uuid:929d63a7-fc21-4dea-bd2d-6a57693f3e7d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:27:59Z |
| publishDate | 2020 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:929d63a7-fc21-4dea-bd2d-6a57693f3e7d2022-03-26T23:26:50ZA sketched finite element method for elliptic modelsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:929d63a7-fc21-4dea-bd2d-6a57693f3e7dEnglishSymplectic ElementsElsevier 2020Lung, RWu, YKamilis, DPolydorides, NWe 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. |
| spellingShingle | Lung, R Wu, Y Kamilis, D Polydorides, N A sketched finite element method for elliptic models |
| title | A sketched finite element method for elliptic models |
| title_full | A sketched finite element method for elliptic models |
| title_fullStr | A sketched finite element method for elliptic models |
| title_full_unstemmed | A sketched finite element method for elliptic models |
| title_short | A sketched finite element method for elliptic models |
| title_sort | sketched finite element method for elliptic models |
| work_keys_str_mv | AT lungr asketchedfiniteelementmethodforellipticmodels AT wuy asketchedfiniteelementmethodforellipticmodels AT kamilisd asketchedfiniteelementmethodforellipticmodels AT polydoridesn asketchedfiniteelementmethodforellipticmodels AT lungr sketchedfiniteelementmethodforellipticmodels AT wuy sketchedfiniteelementmethodforellipticmodels AT kamilisd sketchedfiniteelementmethodforellipticmodels AT polydoridesn sketchedfiniteelementmethodforellipticmodels |