Solving Acoustic Boundary Integral Equations Using High Performance Tile Low-Rank LU Factorization
| Autor: | Kadir Akbudak, Hakan Bagci, Rui Chen, Hatem Ltaief, Noha Al-Harthi, David E. Keyes, Rabab Alomairy |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discretization
Computer science Computation 020206 networking & telecommunications 010103 numerical & computational mathematics 02 engineering and technology Solver System of linear equations 01 natural sciences LU decomposition law.invention Computational science Runtime system Matrix (mathematics) law Robustness (computer science) 0202 electrical engineering electronic engineering information engineering 0101 mathematics Data compression |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030507428 |
| Popis: | We design and develop a new high performance implementation of a fast direct LU-based solver using low-rank approximations on massively parallel systems. The LU factorization is the most time-consuming step in solving systems of linear equations in the context of analyzing acoustic scattering from large 3D objects. The matrix equation is obtained by discretizing the boundary integral of the exterior Helmholtz problem using a higher-order Nystrom scheme. The main idea is to exploit the inherent data sparsity of the matrix operator by performing local tile-centric approximations while still capturing the most significant information. In particular, the proposed LU-based solver leverages the Tile Low-Rank (TLR) data compression format as implemented in the Hierarchical Computations on Manycore Architectures (HiCMA) library to decrease the complexity of “classical” dense direct solvers from cubic to quadratic order. We taskify the underlying boundary integral kernels to expose fine-grained computations. We then employ the dynamic runtime system StarPU to orchestrate the scheduling of computational tasks on shared and distributed-memory systems. The resulting asynchronous execution permits to compensate for the load imbalance due to the heterogeneous ranks, while mitigating the overhead of data motion. We assess the robustness of our TLR LU-based solver and study the qualitative impact when using different numerical accuracies. The new TLR LU factorization outperforms the state-of-the-art dense factorizations by up to an order of magnitude on various parallel systems, for analysis of scattering from large-scale 3D synthetic and real geometries. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|