论文标题
用图色加速的等级结构矩阵的随机压缩
Randomized Compression of Rank-Structured Matrices Accelerated with Graph Coloring
论文作者
论文摘要
提出了用于计算给定等级结构矩阵$ a $ A $（又称A $ H $ -MATRIX）的随机算法。该算法利用随机的单数值分解（RSVD），并在假设迅速将$ a $ a $ a $ a^{*} $的算法可用的假设下运行。该算法分析了层次树，该分层树使用图形着色算法来定义等级结构，以生成一组随机测试向量。然后将矩阵应用于测试向量，在最后一步中，矩阵本身由观察到的输入输出对重建。提出的方法是L. Lin，J。Lu和L. Ying的“脱皮算法”的演变，“从矩阵矢量乘法中快速构建层次矩阵表示”，JCP，230（10），2011年，2011年。对于统一树的情况，新方法实质上降低了原始PeeLith的新方法。更重要的是，新技术会导致许多非均匀树的急剧加速，因为它构建了针对给定树的样品向量。该算法对于涉及一组限制到较低维对物体的点的内核矩阵特别有效，例如在三维中定义在表面上定义的边界积分方程。
A randomized algorithm for computing a data sparse representation of a given rank structured matrix $A$ (a.k.a. an $H$-matrix) is presented. The algorithm draws on the randomized singular value decomposition (RSVD), and operates under the assumption that algorithms for rapidly applying $A$ and $A^{*}$ to vectors are available. The algorithm analyzes the hierarchical tree that defines the rank structure using graph coloring algorithms to generate a set of random test vectors. The matrix is then applied to the test vectors, and in a final step the matrix itself is reconstructed by the observed input-output pairs. The method presented is an evolution of the "peeling algorithm" of L. Lin, J. Lu, and L. Ying, "Fast construction of hierarchical matrix representation from matrix-vector multiplication," JCP, 230(10), 2011. For the case of uniform trees, the new method substantially reduces the pre-factor of the original peeling algorithm. More significantly, the new technique leads to dramatic acceleration for many non-uniform trees since it constructs sample vectors that are optimized for a given tree. The algorithm is particularly effective for kernel matrices involving a set of points restricted to a lower dimensional object than the ambient space, such as a boundary integral equation defined on a surface in three dimensions.
