Accelerating Parallel Hierarchical Matrix-Vector Products via Data-Driven Sampling
Accelerating Parallel Hierarchical Matrix-Vector Products via Data-Driven Sampling
复制标题
DOI：
10.1109/ipdps47924.2020.00082
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Lucas Erlandson;Difeng Cai;Yuanzhe Xi;Edmond Chow
中科院分区：
文献类型：
--
作者：
Lucas Erlandson;Difeng Cai;Yuanzhe Xi;Edmond Chow
分层矩阵是可伸缩的矩阵表示，特别适用于矩阵条目由在点对之间评估的平滑核函数定义的情况。在本文中，我们提出了一种新的方案，以缓解许多分层矩阵方法中存在的计算瓶颈。对于一般的核函数，一种流行的构造分层矩阵的方法是通过内插，因为与计算昂贵的代数技术相比，它的效率很高。然而，基于内插的方法往往会导致更大的阶数，并且不能很好地扩展到更高的维度。我们提出了一种新的数据驱动方法来解决这些问题。该方法通过对点的全局分布使用代理来实现降序。代理是使用分层数据驱动采样生成的。由于等级较低，所以构建成本、内存需求和矩阵向量乘积成本都降低了。使用最新的维度独立抽样，新方法使解决更高维度的问题成为可能。我们还讨论了分层矩阵构造和矩阵向量乘积的动态变化，它能够将内存使用量减少一个数量级。这是通过推迟某些中间矩阵的生成，直到它们被使用，及时地生成它们来实现的。我们提供的结果证明了我们的改进的有效性，既有单独的，也有相互结合的。对于3D中涉及320,000个点的问题，我们的数据驱动方法将内存使用量从使用最先进方法的58.75GiB(如果存储得密集，则为762.9 GiB)降低到18.60GiB。与我们的动态方法相结合，我们能够将总内存使用量减少到543.74 MiB。
Hierarchical matrices are scalable matrix representations particularly suited to the case where the matrix entries are defined by a smooth kernel function evaluated between pairs of points. In this paper, we present a new scheme to alleviate the computational bottlenecks present in many hierarchical matrix methods. For general kernel functions, a popular approach to construct hierarchical matrices is through interpolation, due to its efficiency compared to computationally expensive algebraic techniques. However, interpolation-based methods often lead to larger ranks, and do not scale well to higher dimensions. We propose a new data-driven method to resolve these issues. The new method is able to accomplish the rank reduction by using a surrogate for the global distribution of points. The surrogate is generated using a hierarchical data-driven sampling. As a result of the lower rank, the construction cost, memory requirements, and matrix-vector product costs decrease. Using state-of-theart dimension independent sampling, the new method makes it possible to tackle problems in higher dimensions. We also discuss an on-the-fly variation of hierarchical matrix construction and matrix-vector products that is able to reduce memory usage by an order of magnitude. This is accomplished by postponing the generation of certain intermediate matrices until they are used, generating them just in time. We provide results demonstrating the effectiveness of our improvements, both individually and in conjunction with each other. For a problem involving 320,000 points in 3D, our data-driven approach reduces the memory usage from 58.75 GiB using state-of-the-art methods (762.9 GiB if stored dense) to 18.60 GiB. In combination with our on-thefly approach, we are able to reduce the total memory usage to 543.74 MiB.