# Giga-scale Kernel Matrix Vector Multiplication on GPU

arXiv: https://arxiv.org/abs/2202.01085 · HTML: https://mlsanity.com/paper/2202.01085/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 2 Feb 2022.

## Builds on (most cited first, 10 of 10)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Mitigating the Curse of Dimensionality: Sparse Grid Characteristics Method for Optimal Feedback Control and HJB Equations](https://mlsanity.com/paper/1507.04769/) (2015)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)

## Built on by (most cited first, 1 of 1)

- [Fast Gaussian process inference by exact Mat'ern kernel decomposition](https://mlsanity.com/paper/2508.01864/) (2025)

## Abstract (arXiv)

Kernel matrix-vector multiplication (KMVM) is a foundational operation in machine learning and scientific computing. However, as KMVM tends to scale quadratically in both memory and time, applications are often limited by these computational constraints. In this paper, we propose a novel approximation procedure coined textitFaster-Fast and Free Memory Method (fthreem) to address these scaling issues of KMVM for tall~(108~ 109) and skinny~(D≤7) data. Extensive experiments demonstrate that fthreem has empirical linear time and memory complexity with a relative error of order 10-3 and can compute a full KMVM for a billion points in under a minute on a high-end GPU, leading to a significant speed-up in comparison to existing CPU methods. We demonstrate the utility of our procedure by applying it as a drop-in for the state-of-the-art GPU-based linear solver FALKON, improving speed 1.5-5.5 times at the cost of <1% drop in accuracy. We further demonstrate competitive results on Gaussian Process regression coupled with significant speedups on a variety of real-world datasets.