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.
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.
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