论文标题
一个新的嵌套交叉近似
A new Nested Cross Approximation
论文作者
论文摘要
在本文中，我们提出了用于构建H2矩阵的新嵌套交叉近似（NNCA）。它与现有的NCAS〜 \ CITE {BEBENDORF2012 -CONTRUCTING，ZHAO2019Fast}在选择枢轴的技术中，这是近似值的关键部分。我们选择枢轴的技术纯粹是代数，仅涉及一棵树遍历。我们通过开发快速的H2矩阵矢量产品来证明其适用性，该产品使用NNCA进行适当的低级近似值。我们说明了基于NNCA的H2矩阵矢量产品的时序曲线和准确性。我们还提供了基于NNCA的H2矩阵矢量产品与现有基于NCA的H2矩阵矢量产品的比较。一个关键的观察是，NNCA的性能要比现有的NCA更好。此外，使用基于NNCA的H2矩阵矢量产物，我们加速i）在3D和II）中求解一个积分方程，II）支持向量机（SVM）。本着可重复的计算科学的精神，本文中开发的算法的实现可在\ url {https://github.com/safran-lab/nnca}提供。
In this article, we present a new Nested Cross Approximation (NNCA) for constructing H2 matrices. It differs from the existing NCAs~\cite{bebendorf2012constructing, zhao2019fast} in the technique of choosing pivots, a key part of the approximation. Our technique of choosing pivots is purely algebraic and involves only a single tree traversal. We demonstrate its applicability by developing a fast H2 matrix-vector product, that uses NNCA for the appropriate low-rank approximations. We illustrate the timing profiles and the accuracy of NNCA based H2 matrix-vector product. We also provide a comparison of NNCA based H2 matrix-vector product with the existing NCA based H2 matrix-vector products. A key observation is that NNCA performs better than the existing NCAs. In addition, using the NNCA based H2 matrix-vector product, we accelerate i) solving an integral equation in 3D and ii) Support Vector Machine (SVM). In the spirit of reproducible computational science, the implementation of the algorithm developed in this article is made available at \url{https://github.com/SAFRAN-LAB/NNCA}.
