We extend an adaptive partially matrix-free Hierarchically Semi-Separable (HSS) matrix construction algorithm by Gorman et al. [SIAM J. Sci. Comput. 41(5), 2019] which uses Gaussian sketching operators to a broader class of Johnson--Lindenstrauss (JL) sketching operators. We present theoretical work which justifies this extension. In particular, we extend the earlier concentration bounds to all JL sketching operators and examine this bound for specific classes of such operators including the original Gaussian sketching operators, subsampled randomized Hadamard transform (SRHT) and the sparse Johnson--Lindenstrauss transform (SJLT). We discuss the implementation details of applying SJLT efficiently and demonstrate experimentally that using SJLT instead of Gaussian sketching operators leads to 1.5--2.5x speedups of the HSS construction implementation in the STRUMPACK C++ library. The generalized algorithm allows users to select their own JL sketching operators with theoretical lower bounds on the size of the operators which may lead to faster run time with similar HSS construction accuracy.
翻译:我们将戈尔曼等人[SIAM J. Sci. Comput. 41(5), 2019] 的适应性部分无矩阵半半可分离(HSS)矩阵建设算法推广到更广大的约翰逊-伦登斯特拉斯(JL)绘图操作员类别。我们介绍了为这一扩展提供理由的理论工作。我们将早期的浓度界限扩展至所有JL草图操作员,并检查这些操作员的特定类别,包括原高斯画家、次级抽样随机哈达马德变换(SRHT)和稀疏的约翰逊-伦斯特劳斯变换(SJLT)等。我们讨论了高效应用SJLT的实施细节,并实验性地表明,使用SJLT而不是高斯素描画操作员可导致在STRUMPACK C++图书馆实施HSS的HSS加速速度1.5-2.5x。通用算法允许用户选择自己的JL绘图操作员,在操作员的操作员规模上理论范围较低,可能会以类似HSS的精确度加速运行。