标题： 基于稀疏符号草图的可并行化随机草图和预处理线性回归算法 显示英文标题

标题： GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches

摘要： 大量理论和数值结果已经确立了“草图与预处理”范式作为一种在标准计算环境中解决大规模线性回归问题的强大方法。也许令人惊讶的是，在理解“草图与预处理”在图形处理单元（GPU）系统上的表现方面所做的工作少得多。我们通过在单GPU和多GPU系统上基于稀疏符号草图的“草图与预处理”实现的基准测试来填补这一空白。在此过程中，我们描述了一种新颖的、易于并行化的基于拒绝抽样的生成稀疏符号草图的方法。我们的方法特别适合于GPU，并且可以轻松适应各种计算环境。总体而言，我们的数值实验表明，使用稀疏符号草图的“草图与预处理”尤其适合于GPU，并可能适用于黑盒最小二乘求解器。 显示英文摘要

摘要： A litany of theoretical and numerical results have established the sketch-and-precondition paradigm as a powerful approach to solving large linear regression problems in standard computing environments. Perhaps surprisingly, much less work has been done on understanding how sketch-and-precondition performs on graphics processing unit (GPU) systems. We address this gap by benchmarking an implementation of sketch-and-precondition based on sparse sign-sketches on single and multi-GPU systems. In doing so, we describe a novel, easily parallelized, rejection-sampling based method for generating sparse sign sketches. Our approach, which is particularly well-suited for GPUs, is easily adapted to a variety of computing environments. Taken as a whole, our numerical experiments indicate that sketch-and-precondition with sparse sign sketches is particularly well-suited for GPUs, and may be suitable for use in black-box least-squares solvers.