Linear-time CUR approximation of BEM matrices

Alan Ayala 1 Xavier Claeys 1, 2 Laura Grigori 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris, LJLL - Laboratoire Jacques-Louis Lions
Abstract : In this paper we propose linear-time CUR approximation algorithms for admissible matrices obtained from the hierarchical form of Boundary Element matrices. We propose a new approach called geometric sampling to obtain indices of most significant rows and columns using information from the domains where the problem is posed. Our strategy is tailored to Boundary Element Methods (BEM) since it uses directly and explicitly the cluster tree containing information from the problem geometry. Our CUR algorithm has precision comparable with low-rank approximations created with the truncated QR factorization with column pivoting (QRCP) and the Adaptive Cross Approximation (ACA) with full pivoting, which are quadratic-cost methods. When compared to the well-known linear-time algorithm ACA with partial pivoting, we show that our algorithm improves, in general, the convergence error and overcomes some cases where ACA fails. We provide a general relative error bound for CUR approximations created with geometrical sampling. Finally, we evaluate the performance of our algorithms on traditional BEM problems defined over different geometries.
Complete list of metadatas

Cited literature [78 references]  Display  Hide  Download

https://hal.inria.fr/hal-01893036
Contributor : Ayala Alan <>
Submitted on : Thursday, October 11, 2018 - 7:20:47 AM
Last modification on : Friday, September 20, 2019 - 4:34:04 PM
Long-term archiving on : Saturday, January 12, 2019 - 12:44:53 PM

File

RR-9208.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01893036, version 1

Citation

Alan Ayala, Xavier Claeys, Laura Grigori. Linear-time CUR approximation of BEM matrices. [Research Report] RR-9208, INRIA PARIS. 2018. ⟨hal-01893036⟩

Share

Metrics

Record views

121

Files downloads

138