When solving a large linear system $Ax = b$, finding eigenvalues, or computing matrix transformations, standard textbook approaches assume you must first construct and store the matrix $A$. However, as problem sizes scale, storing $A$ explicitly becomes a massive bottleneck. For a dense matrix, memory consumption scales quadratically ($O(N^2)$) with the number of variables, quickly hitting a "memory wall" where hardware runs out of RAM long before it runs out of compute cycles.
The core intuition behind overcoming this bottleneck is a simple but powerful realization: iterative algorithms do not actually need to see a matrix; they only need to see what the matrix does to a vector.
Whether using Krylov subspace methods (such as Conjugate Gradient or GMRES), multigrid solvers, or iterative eigensolvers, the algorithm interacts with the system exclusively through matrix-vector multiplications (MVMs), $v \mapsto Av$. If we can compute the resulting vector directly from the underlying data, physics, or differential operators without ever assembling $A$, we can bypass the memory wall entirely. This shifts the computational bottleneck from memory bandwidth to raw arithmetic throughput—a trade-off that modern parallel hardware is optimized to exploit.
Eliminating Assembly in PDEs and Fluid Dynamics
In computational fluid dynamics (CFD) and finite element methods (FEM), explicitly assembling a global Jacobian or stiffness matrix is incredibly expensive. This is especially true for high-order discretizations, where the coupling between degrees of freedom causes the number of nonzero entries to explode.
To avoid this, matrix-free Newton-Krylov methods approximate the action of a Jacobian matrix on a vector using finite differences. As demonstrated by William Gropp et al. in parallel implicit CFD frameworks, the product of the Jacobian $J$ and a vector $v$ can be evaluated as:
$$Jv \approx \frac{F(x + \epsilon v) - F(x)}{\epsilon}$$
This approach, detailed in Globalized Newton-Krylov-Schwarz Algorithms and Software for Parallel Implicit CFD, allows for higher-order accuracy without the memory overhead of full matrix assembly.
For high-order spatial discretizations like Discontinuous Galerkin or high-order FEM, the reliance on fully assembled matrices severely limits scalability. Ben S. Southworth et al. developed robust preconditioning frameworks that operate in a matrix-free manner by applying operators directly rather than constructing large system matrices (Fast Solution of Fully Implicit Runge-Kutta and Discontinuous Galerkin in Time for Numerical PDEs, Part I: the Linear Setting). Similarly, Alexey Voronin et al. showed that adopting matrix-free or operator-sum techniques is essential to reduce the computational footprint and improve scalability as the polynomial degree grows in Stokes equations (Monolithic Multigrid Preconditioners for High-Order Discretizations of Stokes Equations).
This strategy is exceptionally well-suited for graphics processing units (GPUs), which favor high arithmetic intensity over heavy memory access. Andrew E. Loeb et al. implemented "assembly-free" FEM algorithms for heat transfer simulations on GPUs (Analysis of heterogeneous computing approaches to simulating heat transfer in heterogeneous material). By computing matrix-vector products on the fly during iterative solver steps, they bypassed the memory bottlenecks of large-scale sparse matrices, enabling millions of degrees of freedom to be simulated on consumer-grade hardware.
Geometric and algebraic multigrid methods also leverage this principle. Instead of storing a global sparse matrix, solvers can utilize compact local stencils to calculate values on the fly. This approach has been successfully applied across various domains:
- Seismic Imaging: Eran Treister et al. designed a matrix-free geometric multigrid method using compact stencils for the elastic Helmholtz equation, bypassing memory constraints in massive 3D wave simulations (LFA-tuned matrix-free multigrid method for the elastic Helmholtz equation).
- Engineering Solvers: Carlo Janna et al. introduced a matrix-free implementation for algebraic multigrid (AMG) prolongation, treating core operations as specialized sparse matrix-matrix products to minimize communication overhead in parallel environments (Parallel Energy-Minimization Prolongation for Algebraic Multigrid).
- Fluid-Structure Interaction: Rachel Yovel et al. utilized a matrix-free approach for rapid recomputation of operators and efficient vector-operator products in immersed boundary methods (A SIMPLE-based preconditioned solver for the direct-forcing immersed boundary method).
Bypassing the Kernel Matrix in Machine Learning
In machine learning, non-linear kernel methods—such as Gaussian Processes (GPs) and Kernel Ridge Regression (KRR)—suffer from a strict $O(N^2)$ memory bottleneck. Training requires a Gram (or covariance) matrix $K$ that stores the pairwise similarities between all $N$ data points.
By relying exclusively on matrix-vector multiplications, we can train these models without ever storing the full matrix $K$. Geoff Pleiss et al. combined contour integral quadrature with a multi-shift iterative solver to compute matrix square roots ($K^{1/2}b$) and their inverses ($K^{-1/2}b$) times a vector (Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization). Because the algorithm relies solely on MVMs, the memory requirement drops from $O(N^2)$ to $O(N)$, allowing Gaussian Processes to scale to tens of thousands of dimensions.
To scale even further, Andres Potapczynski et al. paired matrix-free conjugate gradient solvers with low-precision (16-bit) arithmetic (Low-Precision Arithmetic for Fast Gaussian Processes). This combination allowed exact GP training on millions of data points on a single GPU by calculating covariance elements on the fly.
Standard Kernel Method:
[Data X] ---> Compute & Store Full Matrix K (O(N^2) Memory) ---> Solver
Matrix-Free Kernel Method:
[Data X] ---> Iterative Solver ---> Request Kv
|
v
Compute elements of Kv on the fly (O(N) Memory)
Alternatively, row-based iterative updates can be used to evaluate the kernel function on demand. Aaditya Ramdas demonstrated that applying Kaczmarz-style row-based updates to kernel ridge regression allows models to be trained with linear space complexity relative to the number of samples, performing updates based on individual kernel evaluations (Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?).
Exploiting mathematical structure within the kernel function can accelerate these on-the-fly multiplications. Franziska Nestler et al. combined ANOVA kernels (which decompose high-dimensional data into low-dimensional groups) with the Non-equispaced Fast Fourier Transform (NFFT) to calculate matrix-vector products on the fly, achieving near-linear scaling and avoiding memory exhaustion (Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication).
For non-linear canonical correlation analysis, Viivi Uurtio et al. bypassed the kernel matrix entirely by requiring projection directions to have "preimages" in the original data space, reducing both memory and time complexity to linear relative to the sample size (Large-Scale Sparse Kernel Canonical Correlation Analysis). This philosophy of implicit operator application also extends to deep learning optimization; Mohammadreza Soltani et al. maintained computational efficiency when training polynomial neural networks by treating the adjoint operator implicitly within subspace iterations rather than constructing large-scale weight matrices (Towards Provable Learning of Polynomial Neural Networks Using Low-Rank Matrix Estimation).
High-Dimensional Physics and Matrix Transformations
In quantum mechanics, the state space grows exponentially with the number of particles, making explicit Hamiltonian matrices impossible to store. However, the action of a Hamiltonian operator can be computed directly on a state vector using mapping algorithms.
Alexej I. Streltsov et al. used this matrix-free approach to simulate the long-time quantum dynamics of thousands of bosons in periodic traps, avoiding the memory bottlenecks typically caused by exponential state-space growth (Accurate multi-boson long-time dynamics in triple-well periodic traps). Similarly, Ben Nebgen utilized direct operator application to vectors to achieve large-scale Hamiltonian diagonalization, enabling the simulation of molecular systems with millions of basis functions for vibronic coupling (Excited states of chromophores and vibronic interactions). When calculating electronic excited states via the particle-particle random phase approximation, Jianfeng Lu et al. combined a Jacobi-Davidson eigensolver with compressed integral formats to rely exclusively on matrix-vector multiplications, reducing storage requirements and scaling eigenvalue calculations efficiently (A cubic scaling algorithm for excited states calculations in particle-particle random phase approximation).
The strategy of replacing dense matrix operations with structured vector operations applies even to abstract matrix transformations and random matrix theory:
- Stochastic Galerkin Systems: Paul G. Constantine et al. reframed massive stochastic linear systems through the lens of numerical quadrature (A Factorization of the Spectral Galerkin System for Parameterized Matrix Equations: Derivation and Applications). By utilizing the action of the original matrix at specific quadrature points, they performed iterative operations without explicitly forming or storing the full coupled matrix.
- Random Orthogonal Ensembles: Simulating iterative algorithms on high-dimensional random matrices typically exhausts memory. Yue Lu et al. developed the "Householder Dice" algorithm, which replaces dense matrix-vector multiplications with a sequence of vector-vector operations (Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles). The memory footprint scales linearly with the product of the dimension and the iteration count, rather than quadratically with the matrix size.
- Singular Value Decomposition (SVD): When computing the SVD of a sequence of matrix products and quotients, forming the complete product explicitly can introduce massive numerical cancellation and high computational costs. Gene H. Golub et al. introduced an algorithm that avoids forming the complete product (Computing the SVD of a General Matrix Product/Quotient). Instead, it computes specific rows or elements of intermediate products strictly on demand to apply the necessary unitary transformations.
By focusing entirely on the mathematical action of an operator rather than its static storage, matrix-free computation transforms memory-bound limitations into compute-bound opportunities across scientific computing and machine learning.
Key Foundational Work
A Parallel Geometric Multigrid Method for Finite Elements on Octree Meshes (2010) — contributed 2 concept elements to this direction.
Globalized Newton-Krylov-Schwarz Algorithms and Software for Parallel Implicit CFD (2000) — contributed 1 concept elements to this direction.
Computing the SVD of a General Matrix Product/Quotient (2000) — contributed 1 concept elements to this direction.