INV-ASKIT: A Parallel Fast Direct Solver for Kernel Matrices
INV-ASKIT: A Parallel Fast Direct Solver for Kernel Matrices
复制标题
INV-ASKIT：核矩阵的并行快速直接求解器
DOI：
10.1109/ipdps.2016.12
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
Chenhan D. Yu;William B. March;Bo Xiao;G. Biros
我们提出了一个并行算法计算的近似因式分解的N × N核矩阵。一旦构造了这个分解（用N log 2 N功），我们就可以用这个矩阵用N log N功求解线性系统。核矩阵表示度量空间中点的成对相互作用。它们出现在机器学习、近似理论和计算物理学中。核矩阵通常是稠密的（矩阵乘法与N成二次方）和病态的（求解可能需要数百次Krylov迭代）。因此，矩阵乘法和因子分解的快速算法对于可扩展性至关重要。最近，我们介绍了ASKIT，一种新的方法，它类似于N体方法，用于近似核矩阵。这里我们介绍INV-IASKIT，一个基于ASKIT的分解方案。我们描述了新的方法，得到的复杂性估计，并进行实证研究，其准确性和可扩展性。我们使用共享和分布式内存并行技术，在真实世界的数据集上报告了结果，包括“COVTYPE”（54维中的0.5M点），“SUSY”（8维中的4.5M点）和“MNIST”（784维中的2 M点）。在我们最大的一次运行中，我们在4,096个Sandy-Bridge核上近似因式分解了一个大小为32 M × 32 M的稠密矩阵（由64维中的点生成）。据我们所知，这些结果将现有技术提高了几个数量级。
We present a parallel algorithm for computing the approximate factorization of an N-by-N kernel matrix. Once this factorization has been constructed (with N log2 N work), we can solve linear systems with this matrix with N log N work. Kernel matrices represent pairwise interactions of points in metric spaces. They appear in machine learning, approximation theory, and computational physics. Kernel matrices are typically dense (matrix multiplication scales quadratically with N) and ill-conditioned (solves can require100s of Krylov iterations). Thus, fast algorithms for matrix multiplication and factorization are critical for scalability. Recently we introduced ASKIT, a new method, which resembles N-body methods, for approximating a kernel matrix. Here we introduce INV-IASKIT, a factorization scheme based on ASKIT. We describe the new method, derive complexity estimates, and conduct an empirical study of its accuracy and scalability. We report results on real-world datasets including "COVTYPE" (0.5M points in 54dimensions), "SUSY" (4.5M points in 8 dimensions) and "MNIST"(2M points in 784 dimensions) using shared and distributed memory parallelism. In our largest run we approximately factorize a dense matrix of size 32M × 32M (generated from points in 64 dimensions) on 4,096 Sandy-Bridge cores. To our knowledge these results improve the state of the art by several orders of magnitude.