Orateur
Guillaume Sylvand
(Airbus Group)
Description
For the numerical simulation of wave propagation in acoustics, Airbus Group Innovations relies on integral
equations solved with the Boundary Elements Method. The advantages of this approach are well known: mainly
accuracy, and simpler (surfacic) mesh. The main algorithm drawback is the need to cope with a dense matrix
whose size can be quite large for wave propagation problems, where the mesh step is governed by the wavelength
of the physical problem treated (in frequency domain).
Since the late 90's, fast methods have been introduced to deal with these limitations. First, the Fast Multipole Method (FMM) allowed to compute fast matrix-vector products (in O(n log2(n)) instead of O(n2) for the standard algorithm), and hence to design fast solvers using iterative methods. Lately, H-Matrix methods have gained wide acceptance by introducing fast direct solvers, allowing to solve systems in O(n log2(n)) - or less - without the hassle of using iterative solvers (unknown convergence rate and difficulty to find a goodpreconditionner).
H-Matrix [1] is a lossy, hierarchical storage scheme for matrices that, along with an associated arithmetic, provides a rich enough set of approximate operations to perform the matrix addition, multiplication, factorization (e.g. LU or LDLT ) and inversion. It relies on two core ideas : (a) nested clustering of the degrees of freedom, and of their products; and (b) adaptative compression of these clusters. Several choices exist in the literature for these two ingredients, the most common being Binary Space Partitioning for the clustering and Adaptative Cross Approximation for the compression.
Together, they allow for the construction of a fast direct solver [2], which is especially important for BEM applications as it gracefully handles a large number of Right-Hand Sides (RHS). They also provide a kernel-independent fast solver, allowing one to use the method for dierent physics.
Airbus Group Innovations has recently implemented the H-Matrix arithmetic and successfully applied it to a wide range of industrial applications in electromagnetism and acoustics. Furthermore, these algorithms are hard to eciently parallelize, as the very scarce literature on the subject shows [3]. We developed a parallel solver that goes beyond the aforementioned reference, using innovative techniques on top of a state-of-the-art runtime system StarPU [4][5]. This enables the solving of very large problems, with a very good eciency. In this presentation, we show some results on the accuracy of this method on several challenging applications, and its fast solving time and ecient use of resources.
References
[1] W. Hackbusch, A Sparse Matrix Arithmetic Based on H-Matrices. Part I: Introduction to H-Matrices, Computing, Volume 62, Issue 2 (1999)..
[2] L. Grasedyck, W. Hackbusch, Construction and Arithmetics of H-Matrices, Computing, Volume 70, Issue 4 (2003).
[3] R. Kriemann, Parallel H-Matrix Arithmetics on Shared Memory Systems, Computing, Volume 74, Issue 3 (2005).
[4] B. Lize, Resolution directe rapide pour les elements nis de frontiere en electromagnetisme et acoustique : H-Matrices. Parallelisme et applications industrielles, PhD thesis, Paris 13, 2014.
[5] C. Augonnet, S. Thibault, R. Namyst, and P.-A. Wacrenier, StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures, Concurrency and Computation: Practice and Experience, Special Issue: Euro-Par 2009, vol. 23, pp. 187198, Feb. 2011.
Since the late 90's, fast methods have been introduced to deal with these limitations. First, the Fast Multipole Method (FMM) allowed to compute fast matrix-vector products (in O(n log2(n)) instead of O(n2) for the standard algorithm), and hence to design fast solvers using iterative methods. Lately, H-Matrix methods have gained wide acceptance by introducing fast direct solvers, allowing to solve systems in O(n log2(n)) - or less - without the hassle of using iterative solvers (unknown convergence rate and difficulty to find a goodpreconditionner).
H-Matrix [1] is a lossy, hierarchical storage scheme for matrices that, along with an associated arithmetic, provides a rich enough set of approximate operations to perform the matrix addition, multiplication, factorization (e.g. LU or LDLT ) and inversion. It relies on two core ideas : (a) nested clustering of the degrees of freedom, and of their products; and (b) adaptative compression of these clusters. Several choices exist in the literature for these two ingredients, the most common being Binary Space Partitioning for the clustering and Adaptative Cross Approximation for the compression.
Together, they allow for the construction of a fast direct solver [2], which is especially important for BEM applications as it gracefully handles a large number of Right-Hand Sides (RHS). They also provide a kernel-independent fast solver, allowing one to use the method for dierent physics.
Airbus Group Innovations has recently implemented the H-Matrix arithmetic and successfully applied it to a wide range of industrial applications in electromagnetism and acoustics. Furthermore, these algorithms are hard to eciently parallelize, as the very scarce literature on the subject shows [3]. We developed a parallel solver that goes beyond the aforementioned reference, using innovative techniques on top of a state-of-the-art runtime system StarPU [4][5]. This enables the solving of very large problems, with a very good eciency. In this presentation, we show some results on the accuracy of this method on several challenging applications, and its fast solving time and ecient use of resources.
References
[1] W. Hackbusch, A Sparse Matrix Arithmetic Based on H-Matrices. Part I: Introduction to H-Matrices, Computing, Volume 62, Issue 2 (1999)..
[2] L. Grasedyck, W. Hackbusch, Construction and Arithmetics of H-Matrices, Computing, Volume 70, Issue 4 (2003).
[3] R. Kriemann, Parallel H-Matrix Arithmetics on Shared Memory Systems, Computing, Volume 74, Issue 3 (2005).
[4] B. Lize, Resolution directe rapide pour les elements nis de frontiere en electromagnetisme et acoustique : H-Matrices. Parallelisme et applications industrielles, PhD thesis, Paris 13, 2014.
[5] C. Augonnet, S. Thibault, R. Namyst, and P.-A. Wacrenier, StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures, Concurrency and Computation: Practice and Experience, Special Issue: Euro-Par 2009, vol. 23, pp. 187198, Feb. 2011.
