An N log N Parallel Fast Direct Solver for Kernel Matrices
An N log N Parallel Fast Direct Solver for Kernel Matrices
复制标题
核矩阵的 N log N 并行快速直接求解器
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
Chenhan D. Yu;William B. March;G. Biros
核矩阵出现在机器学习和非参数统计中。给定d维中的N个点和需要O（d）工作来评估的核函数，我们提出了一个O（dN log N）工作算法来近似分解正则化核矩阵，这是学习任务训练阶段的一个常见计算瓶颈。因此，我们可以用O（N log N）的时间复杂度来求解一个线性系统。我们的算法只需要核评估，并不要求核矩阵承认一个有效的全球低秩近似。相反，我们的因式分解仅在适当的行和列排序下保留非对角块的低秩属性。我们还提出了一个混合的方法，当分解是昂贵的，结合了部分因式分解与迭代方法。作为一个亮点，我们能够在2分钟内在3，072个x86“Haswell”内核上近似分解一个密集的11M × 11M内核矩阵，并在1分钟内使用4，352个“Knights Landing”内核分解一个4.5M × 4.5M矩阵。
Kernel matrices appear in machine learning and non-parametric statistics. Given N points in d dimensions and a kernel function that requires O(d) work to evaluate, we present an O(dN log N)-work algorithm for the approximate factorization of a regularized kernel matrix, a common computational bottleneck in the training phase of a learning task. With this factorization, solving a linear system with a kernel matrix can be done with O(N log N) work. Our algorithm only requires kernel evaluations and does not require that the kernel matrix admits an efficient global low rank approximation. Instead, our factorization only assumeslow-rank properties for the off-diagonal blocks under anappropriate row and column ordering. We also present a hybrid method that, when the factorization is prohibitively expensive, combines a partial factorization with iterative methods. As a highlight, we are able to approximately factorize a dense 11M-by-11M kernel matrixin 2 minutes on 3,072 x86 "Haswell" cores and a 4.5M-by-4.5M matrix in 1 minute using 4,352 "Knights Landing" cores.