### Inv-ASKIT: A Parallel Fast Diret Solver for Kernel Matrices

**2016-02-03**

1602.01376 | cs.NA

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 \log^2 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
require 100s of Krylov iterations). Thus, fast algorithms for matrix
multiplication and factorization are critical for scalability.
Recently we introduced ASKIT, a new method for approximating a kernel matrix
that resembles N-body methods. Here we introduce INV-ASKIT, 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.5$M points in 54
dimensions), "SUSY" ($4.5$M 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 $\times$ 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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2016-09-28**

1609.09154 | cs.DC

Non-negative matrix factorization (NMF) is the problem of determining two
non-negative low rank fact… show more

**2018-10-29**

1810.12283 | cs.LG

Gaussian processes (GPs) with derivatives are useful in many applications,
including Bayesian optimi… show more

**2018-07-05**

1807.02125 | stat.ML

We introduce a kernel approximation strategy that enables computation of the
Gaussian process log ma… show more

**2018-09-28**

1809.11165 | cs.LG

Despite advances in scalable models, the inference tools used for Gaussian
processes (GPs) have yet … show more

**2019-03-06**

1903.02343 | math.NA

In this work, we consider two types of large-scale quadratic matrix
equations: Continuous-time algeb… show more

**2018-12-18**

1812.07152 | cs.DC

We present MatRox, a novel model-based algorithm and implementation of
Hierarchically Semi-Separable… show more

**2019-01-23**

1901.07993 | cs.NA

We present three methods for distributed memory parallel inverse
factorization of block-sparse Hermi… show more

**2015-10-26**

1510.07363 | math.NA

Inversion of sparse matrices with standard direct solve schemes is robust,
but computationally expen… show more

**2017-06-09**

1706.02803 | cs.LG

Kernel $k$-means clustering can correctly identify and extract a far more
varied collection of clust… show more

**2019-02-05**

1902.01829 | cs.DS

Hierarchical matrices are space and time efficient representations of dense
matrices that exploit th… show more

**2019-03-06**

1903.02153 | cs.MS

This paper presents PBBFMM3D: a parallel black-box fast multipole method that
accelerates kernel mat… show more

**2014-02-16**

1402.3849 | cs.CV

Kernel-based clustering algorithms have the ability to capture the non-linear
structure in real worl… show more

**2018-08-14**

1808.04580 | cs.LG

The graph Laplacian is a standard tool in data science, machine learning, and
image processing. The … show more

**2018-10-09**

1810.04125 | cs.NA

We present new algorithms for the randomized construction of hierarchically
semi-separable matrices,… show more

**2019-06-11**

1906.04705 | cs.LG

Least-mean squares (LMS) solvers such as Linear / Ridge / Lasso-Regression,
SVD and Elastic-Net not … show more