Lattice H-Matrices on Distributed-Memory Systems
Lattice H-Matrices on Distributed-Memory Systems
复制标题
DOI：
10.1109/ipdps.2018.00049
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Akihiro Ida
中科院分区：
文献类型：
--
作者：
Akihiro Ida
低秩近似方法，如层次（H）矩阵和块低秩（BLR）矩阵，可以近似来自科学积分方程的稠密矩阵，以减少计算成本和内存使用。在分布式内存系统中，为了有效地使用大量的MPI进程，必须平衡计算负载，并在MPI处理器之间建立有效的通信模式。不幸的是，H矩阵的复杂结构使我们无法满足这些要求。简化矩阵结构是解决这个问题的一种可能的方法，而BLR矩阵中的格结构是这种方法最方便的结构之一。然而，作为一种权衡，内存使用从使用O（N log N）的H矩阵增加到使用O（N^1.5）的BLR矩阵。在这项研究中，我们提出了一种新的方法称为“格H-矩阵。"?简而言之，格H-矩阵是通过利用H-矩阵作为在BLR-矩阵中观察到的格结构块中的子矩阵来构造的。通过将格块分配给MPI进程，我们可以利用复杂的现有并行算法来处理稠密矩阵。我们演示了如何定义格块大小，并确认格H-矩阵的内存复杂度仍然是O（N log N）时，使用适当的块大小取决于MPI处理器的数量。因此，格H-矩阵保持了H-矩阵和BLR-矩阵的优点。我们研究了格H-矩阵在算术函数中的效率，如H-矩阵生成和H-矩阵向量乘法，在分布式存储系统上的大规模问题。在电场分析的数值实验中，我们证实了即使我们使用大量的过程，在晶格H矩阵的情况下，也保持了相对良好的负载平衡。格H矩阵的实现表现出并行加速，达到高达约4,000 MPI进程。它被证实，实施格子H-矩阵版本是显着快于正常的H-矩阵版本的大量过程。
Low-rank approximation methods, such as hierarchical (H) matrices and block low-rank (BLR) matrices, can approximate dense matrices that come from scientific integral equations to reduce computational costs and memory usage. When considering the efficient use of a massive number of MPI processes on distributed-memory systems, we must balance the computational load and construct an efficient communication pattern among MPI processors. Unfortunately, the complicated structure of H-matrices prevents us from meeting these requirements. Simplifying the matrix structure is one possible approach to solve this problem, and the lattice structures found in BLR-matrices are one of the most convenient structures for this approach. However, as a trade-off, the memory usage increases from H-matrices, which use O(N log N), to BLR-matrices, which use O(N^1.5). In this study, we propose a new method called "lattice H-matrices."?In short, the lattice H-matrices are constructed by utilising H-matrices as submatrices in blocks of lattice structures observed in BLR-matrices. By assigning the lattice blocks to MPI processes, we can utilise sophisticated existing parallel algorithms for dense matrices. We demonstrate how the lattice block size should be defined and confirm that the memory complexity of the lattice H-matrices remains O(N log N) when using appropriate block sizes depending on the number of MPI processors. Accordingly, the lattice H-matrices maintain the advantages of both H-matrices and BLR-matrices. We examine the efficiency of lattice H-matrices in arithmetic functions, such as H-matrix generation and H-matrix-vector multiplication, in large-scale problems on distributed-memory systems. In numerical experiments of electric field analyses, we confirmed that a relatively good load balance is maintained in the case of lattice H-matrices even if we use a large number of processes. The implementation of the lattice H-matrices exhibits a parallel speed-up that reaches as high as about 4,000 MPI processes. It is confirmed that the implementation of lattice H-matrix version is significantly faster than of normal H-matrix version for a large number of processes.