No 3D Matrices: A Unified Tensor-Product View of Matrix-Free Cartesian PDE Solvers
Yong Yi Bay Kathleen A. Yearick · 2026
Read No 3D Matrices: A Unified Tensor-Product View of Matrix-Free Cartesian PDE Solvers by Yong Yi Bay Kathleen A. Yearick (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25148.txt.
Introduction
Every three dimensional PDE solver on a Cartesian grid hides the same trick, used by production fluid dynamics codes for fifty years and rarely stated in textbooks. Yong Yi Bay and Kathleen A. Yearick write the manual for it: the three dimensional operator is never built, factored, or stored at all.
Derivative matrices, compact line solves, mass inversions, splitting substeps, and fast Poisson transforms all factor along the coordinate axes. Each collapses into repeated one dimensional banded kernels run along grid lines. The authors derive the Kronecker product algebra that makes the collapse exact, across finite differences, Galerkin and spline methods, collocation, and direct solvers. Three production tricks turn it into speed. A reshaping exposes each sweep as one batched kernel. Sum factorisation rescues high order methods. A pencil layout keeps data contiguous across a cluster. Cost stays linear in the number of unknowns.
Catalog record
| CREATOR | Yong Yi Bay Kathleen A. Yearick |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25148
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
No 3D Matrices: A Unified Tensor-Product View of Matrix-Free Cartesian PDE Solvers Yong Yi Bay Kathleen A. Yearick Abstract Every Cartesian three-dimensional PDE solver hides a structural secret that production CFD codes have used for half a century and that graduate-level textbooks rarely state plainly. The derivative matrices, the compact Padé line solves, the Galerkin mass inversions, the alternating-direction-implicit substeps, and even the fast Poisson and Helmholtz diagonalization transforms all factor along the coordinate axes and collapse into repeated one-dimensional banded kernels executed along the grid lines. The three-dimensional operator exists only on paper; it is never assembled, factored, or stored. This paper is the manual for that collapse. We derive the Kronecker-product algebra that makes it exact, carry it cleanly through central differences, compact schemes, tensor-product Galerkin, B-spline and isogeometric methods, collocation, ADI time stepping, and direct Poisson and Helmholtz solves, and bring into the open the three production tricks that turn the reduction into hardware-conscious floating-point throughput on real machines: the multi-right-hand-side reshape that exposes a sweep as one batched line kernel (a dense BLAS-3 GEMM when the line factor is dense or element-local, a banded or stencil kernel when it is not), the sum factorization that rescues high-order Galerkin from the 𝒪 ( p 2 d ) \mathcal{O}(p^{2d}) quadrature trap, and the pencil decomposition that keeps every direction contiguous across an MPI cluster. For fixed stencil width or fixed polynomial degree, the compute cost stays 𝒪 ( N ) \mathcal{O}(N) in the total number of unknowns N = N x N y N z N=N_{x}N_{y}N_{z} ; the operator storage drops to 𝒪 ( N x + N y + N z ) \mathcal{O}(N_{x}+N_{y}+N_{z}) up to bandwidth constants; direct separable Poisson and Helmholtz solvers add the expected transform cost; the line kernels are embarrassingly parallel. These facts are familiar to practitioners but rarely assembled in one place; this paper collects them and shows how to use them. Keywords: Kronecker product; tensor-product methods; matrix-free operators; sum factorization; fast diagonalization; alternating-direction implicit (ADI) methods; high-order and spectral-element methods; batched (BLAS-3) line kernels. 1 Introduction Imagine a student sitting down to solve the heat equation on a box with 200 points per side. The Laplacian inside an implicit time step would be an 8{,}000{,}000\times 8{,}000{,}000 matrix if it were written monolithically. Dense storage would require roughly 5.1\times 10^{14} bytes, about half a petabyte in double precision. Even the seven-point sparse matrix has about 5.6\times 10^{7} nonzeros, already close to a gigabyte before any solver fill-in or preconditioner storage, and a direct factorization of that object would still occupy a serious workstation for the better part of a night. This sounds like a hard problem. It is not. Production Cartesian solvers do not build that object. They exploit one identity, which a few pages of Kronecker algebra will make exact. With D_{xx} , D_{yy} , and D_{zz} the three one-dimensional second-derivative matrices (each of size 200 , tridiagonal, a few kilobytes total), \Delta_{h}\;=\;I_{z}\otimes I_{y}\otimes D_{xx}\;+\;I_{z}\otimes D_{yy}\otimes I_{x}\;+\;D_{zz}\otimes I_{y}\otimes I_{x}. The 8{,}000{,}000\times 8{,}000{,}000 matrix on the left is the sum of three Kronecker products of the three small matrices on the right. We never build the object on the left. Applying \Delta_{h} to a field is three sweeps along the three families of grid lines, each sweep a batch of 200 -entry tridiagonal matvecs. A factored implicit method, such as ADI, replaces the coupled solve by the corresponding sequence of one-dimensional banded solves; a separable Poisson or Helmholtz solve uses the same directional structure through fast diagonalization. The algorithm lives inside the one-dimensional pieces. This is the picture behind every serious Cartesian solver, and the one Fig. 1 draws for the eye. x -sweep N_{y}N_{z} independent x -lines apply D_{x} to each line y -sweep N_{x}N_{z} independent y -lines apply D_{y} to each line z -sweep N_{x}N_{y} independent z -lines apply D_{z} to each line Figure 1: The whole paper in one picture. A Cartesian three-dimensional operator is executed as a collection of independent one-dimensional line operations. For an x -derivative, the same small banded matrix D_{x} is applied to each x -line of the grid, giving N_{y}N_{z} independent line kernels (left). The y - and z -derivatives reuse the same rule with the direction relabeled (center, right). No three-dimensional matrix is ever assembled: the kernel is one-dimensional, and the dimension only counts how many lines that kernel must visit. The idea is old in the best possible way. It has lived in direct-numerical-simulation solvers ( Bewley et al. 2001 ; Kim & Moin 1985 ) , in FFT Poisson packages ( Costa 2018 ) , and in spectral-element infrastructure for incompressible flow and acoustics ( Deville et al. 2002 ) for decades. It is also the design logic behind pencil-decomposition libraries such as 2DECOMP&FFT ( Li & Laizet 2010 ; Rolfo et al. 2023 ) . What has been missing is a single place where the argument is written down cleanly, once, for every discretization the reader is likely to care about, where the scope of the reduction is stated honestly, and where the production tricks that turn the argument into running floating-point code are ushered into the open. The bookkeeping that makes the picture exact is the Kronecker product, which Van Loan memorably called “ubiquitous” ( Van Loan 2000 ) and which Strang uses as the running thread of computational linear algebra ( Strang 2007 ) . Two identities do most of the work: the mixed-product rule (A\otimes B)(C\otimes D)=AC\otimes BD , and the inverse rule (A\otimes B)^{-1}=A^{-1}\otimes B^{-1} . The first composes directional operators without ever forming their product. The second explains why a tensor-product mass matrix or compact line factor can be inverted by independent one-dimensional solves. Every subsequent section of this paper is a variation on those two identities plus the column-major vectorization rule. The counting that makes the picture fast is even simpler. A one-dimensional banded matrix-vector product with bandwidth w_{x} costs \mathcal{O}(w_{x}N_{x}) . A three-dimensional x -sweep is N_{y}N_{z} such products, hence \mathcal{O}(w_{x}N_{x}N_{y}N_{z})=\mathcal{O}(w_{x}N) . For fixed stencil width or fixed polynomial degree this is simply \mathcal{O}(N) . Banded line solves have the same linear count, up to bandwidth constants, and fast transforms add their usual logarithmic factor. The full operator is large only if it is assembled; the line kernels are never large. Task Tensor-product form How it runs Derivative sweep I_{z}\otimes I_{y}\otimes D_{x} and relabelings independent banded line applies, \mathcal{O}(N) for fixed bandwidth Compact derivative (I_{z}\otimes I_{y}\otimes A_{x})v=(I_{z}\otimes I_{y}\otimes R_{x})u banded right-hand side plus banded line solve Tensor-product mass inverse (M_{z}\otimes M_{y}\otimes M_{x})^{-1} three families of 1D mass solves ADI substep I-r(I_{z}\otimes I_{y}\otimes D_{xx}) one directional batch of line solves Fast Poisson solve diagonalized Kronecker sum transforms by direction, scalar division, inverse transforms Table 1: The recurring pattern. The algebra names the operator; the implementation visits one-dimensional lines. The field storage is still \mathcal{O}(N) , but the operator storage is only the set of one-dimensional factors, typically \mathcal{O}(N_{x}+N_{y}+N_{z}) up to bandwidth constants. That combination, a Kronecker factorization for the algebra and a linewise count for the arithmetic, runs the whole paper. Section 2 makes both visible on a 4\times 3 grid small enough to hold on one page, and