Giga-scale Kernel Matrix Vector Multiplication on GPU

Robert Hu, Dino Sejdinovic, Joan Alexis Glaunès

Abstract

Kernel Matrix-Vector Multiplication (KMVM) is a fundamental operation in machine learning and scientific computing, yet its $O(n^2)$ complexity severely limits scalability. We present $F^3M$ (Faster-Fast and Free Memory Method), an approximation algorithm designed to scale KMVM to billions of data points on a single GPU. By integrating low-level CUDA optimizations with adaptive interpolation and dimensionality relaxation, $F^3M$ achieves near-linear scaling, performing a billion-point multiplication in under two minutes. This represents a significant leap over existing exact and approximate methods, enabling giga-scale kernel methods on standard high-performance hardware.

Introduction

Kernel Matrix-Vector Multiplication (KMVM) is the computational engine behind Gaussian Processes, Kernel Ridge Regression, and various physics simulations. However, it suffers from a "quadratic curse": for $n$ data points, both time and memory complexity scale at $O(n^2)$. While modern GPU-accelerated libraries like KeOps can handle millions of points using exact methods, they become practically infeasible at the billion-point scale, where a single multiplication could take weeks.

Previous approximation methods, such as the Fast Multipole Method (FMM) or Fast and Free Memory (FFM), were often restricted to very low dimensions ($D \le 3$) or struggled with memory management and stability when ported to GPUs. $F^3M$ aims to break this "billion-point barrier" for "tall and skinny" data (high $n$, low $D$), providing a scalable solution for modern large-scale datasets.

The $F^3M$ Framework

$F^3M$ represents the culmination of several decades of research into hierarchical approximation methods. As illustrated in the evolution timeline below, it builds upon the 1988 Fast Multipole Method by incorporating kernel-agnostic interpolation and modern GPU parallelization.

Evolution of the $F^3M$ algorithm from classical FMM and FFM frameworks.

Unlike traditional FMM, which is tied to specific kernels via analytic expansions, $F^3M$ utilizes Lagrange interpolation. This makes the method "kernel agnostic," allowing it to handle any kernel that is sufficiently smooth at a distance without requiring new mathematical derivations for each kernel type.

A major hurdle in GPU-based geometric methods is data organization. Standard library sorting algorithms can be memory-intensive, leading to Out-of-Memory (OOM) errors when processing billions of points. $F^3M$ bypasses this bottleneck with a custom, linear-time, in-place grouping strategy. By utilizing atomicAdd operations, the algorithm assigns points to geometric boxes without the overhead of a full global sort, which is essential for reaching the $n=10^9$ scale.

Adaptive Approximations and Geometric Partitioning

The efficiency of $F^3M$ is further bolstered by several adaptive mechanisms. The algorithm dynamically evaluates the "smoothness" of kernel interactions; if an interaction is smooth enough, it uses fewer interpolation nodes. Additionally, the "adaptive far-field" logic adjusts node density based on the separation between point clusters.

Hierarchical geometric partitioning and adaptive interpolation node selection in $F^3M$.

For clusters containing very few points, $F^3M$ identifies these as "small fields" and switches to direct computation. This avoids the overhead of interpolation where it offers no computational benefit. Furthermore, by employing Sparse Grids (Smolyak grids) and improved geometric partitioning, the authors extended the effective range of the algorithm from $D \le 3$ to $D \le 7$.

Experimental Evaluation

The authors evaluated $F^3M$ on a mix of synthetic and massive real-world datasets, including the Open Street Map (OSM) dataset containing 1.08 billion points.

Performance Results

  • Billion-Point Scale: $F^3M$ computed a full KMVM for $10^9$ points in 125.9 seconds on a single NVIDIA V100 GPU. The core multiplication logic often runs in under a minute.
  • Massive Speedups: Compared to the state-of-the-art exact GPU solver (KeOps), $F^3M$ is estimated to be over 8000x faster at the billion-point scale.
  • Downstream Integration: When used as a kernel solver for the FALKON library, $F^3M$ improved training speeds by 1.5x to 5.5x with less than a 1% drop in accuracy.
  • Linear Scaling: Experiments empirically confirmed that $F^3M$ maintains near-linear time and memory complexity, a critical requirement for giga-scale applications.

Conclusion

$F^3M$ successfully breaks the billion-point barrier for KMVM on a single GPU. By combining geometric approximation techniques with deep hardware optimization, it provides a near-linear scaling solution for large-scale kernel methods. While challenges remain for high-dimensional data ($D > 10$) due to the exponential growth of geometric boxes, $F^3M$ sets a new standard for efficiency in giga-scale machine learning and scientific computing.

Summary updated

Abstract

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 \textit{Faster-Fast and Free Memory Method} ($\fthreem$) to address these scaling issues of KMVM for tall~($10^8\sim 10^9$) and skinny~($D\leq7$) data. Extensive experiments demonstrate that $\fthreem$ has empirical \emph{linear time and memory} complexity with a relative error of order $10^{-3}$ and can compute a full KMVM for a billion points \emph{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, \emph{improving speed 1.5-5.5 times} at the cost of $<1\%$ drop in accuracy. We further demonstrate competitive results on \emph{Gaussian Process regression} coupled with significant speedups on a variety of real-world datasets.
BibTeX
@inproceedings{hu2022giga,
  author = {Robert Hu and Dino Sejdinovic and Joan Alexis Glaunès},
  title = {{Giga-scale Kernel Matrix Vector Multiplication on GPU}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=Y513uEBq6y},
}
Figure