Matrix-free construction of HSS representation using adaptive randomized sampling
Matrix-free construction of HSS representation using adaptive randomized sampling
复制标题
使用自适应随机采样无矩阵构建 HSS 表示
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
X. Li
中科院分区：
文献类型：
--
作者：
C. Gorman;Gustavo Chavez;P. Ghysels;Théo Mary;François;X. Li
我们提出了分层半可分矩阵随机构造的新算法，解决了几个实际问题。HSS构建算法使用部分无矩阵、自适应随机投影方案来确定最大非对角块秩。我们开发了相对和绝对停止准则，以确定足以满足所需精度的随机投影矩阵的最小维数。讨论了两种自适应扩大随机样本矩阵的策略：随机向量的数量重复加倍，随机向量的数量迭代增加一个固定的数量。相对停止准则和绝对停止准则是基于输入矩阵的Hankel块的随机投影的Frobenius范数的概率界。讨论了两种算法的并行实现、计算和通信开销。边界元方法矩阵和量子化学Toeplitz矩阵等一系列应用的并行数值结果显示了所提出算法的有效性、可扩展性和数值鲁棒性。
We present new algorithms for the randomized construction of hierarchically semi-separable matrices, addressing several practical issues. The HSS construction algorithms use a partially matrix-free, adaptive randomized projection scheme to determine the maximum off-diagonal block rank. We develop both relative and absolute stopping criteria to determine the minimum dimension of the random projection matrix that is sufficient for the desired accuracy. Two strategies are discussed to adaptively enlarge the random sample matrix: repeated doubling of the number of random vectors, and iteratively incrementing the number of random vectors by a fixed number. The relative and absolute stopping criteria are based on probabilistic bounds for the Frobenius norm of the random projection of the Hankel blocks of the input matrix. We discuss parallel implementation and computation and communication cost of both variants. Parallel numerical results for a range of applications, including boundary element method matrices and quantum chemistry Toeplitz matrices, show the effectiveness, scalability and numerical robustness of the proposed algorithms.