Sparse linear algebra runs badly on GPUs. When the zeros fall in no particular pattern, the hardware spends its time on scattered memory reads, index lookups, and threads waiting on each other, and these costs often exceed the arithmetic the sparsity was supposed to save. Electric power distribution grids are an exception that has been underused. They are almost always operated as trees ("radial" feeders) rooted at a substation. A tree has two properties that general sparse matrices lack. Eliminating variables from the leaves inward creates no new nonzeros. The dependency structure is also known exactly before any numbers arrive. Together, these two properties remove most of what makes sparse factorization slow on a GPU.
We propose a GPU direct solver for the linear systems inside distribution-grid computations: Newton power-flow steps, interior-point steps for optimal power flow (choosing generator and device setpoints at minimum cost subject to voltage limits), and the differentiable power-flow layers used to train neural surrogates. The solver factors the block-tree matrix with a tree-contraction schedule. It "rakes" leaves into their parents and "compresses" long chains by odd–even reduction, so the number of sequential stages grows logarithmically with feeder size rather than with feeder depth. It batches thousands of load scenarios so that the same tree node across scenarios sits in contiguous memory. When tie switches close and create loops, it handles the few resulting loops as low-rank corrections whose vectors live on tree paths, so no re-analysis is needed. Our core claim has three parts: radiality gives a sparsity structure that needs no preprocessing, it can be re-derived in linear time after any switching event, and on realistic feeders it beats both generic GPU sparse solvers and the factorization-free iterative schemes the field currently relies on.
What prior work established and what it leaves open
The tree structure is already central to power-systems theory. Geometry of Power Flows and Optimization in Distribution Networks shows that the absence of loops makes convex relaxations of optimal power flow exact. Aolaritei et al. approximate the power-flow Jacobian determinant as a product of branch terms, giving linear-time stability monitoring. Both papers motivate our work by showing that trees make problems analytically easy. Neither addresses how to execute the resulting linear algebra on parallel hardware.
The closest computational work comes in three forms, and each leaves a specific gap.
The first is factorization-free decomposition. Ryu et al.'s GPU distributed OPF and its linearized precursor split the feeder into per-component ADMM subproblems that reduce to closed-form matrix-vector products. ADMM is an iterative scheme that solves many small local problems and repeatedly averages them toward agreement. This GPU formulation avoids divergent branching on the hardware. The price is convergence speed: it needs 15,817 iterations on the 8500-bus feeder. Our proposal does the opposite. It factors the tree exactly, so each outer step is a direct solve rather than one of thousands of consensus rounds.
The second is parallel elimination on chains. Schwan et al. reorder block-tridiagonal systems by nested dissection, which brings the parallel depth down to $\log_2 N$ stages. They report more than 2x speedup over NVIDIA's cuDSS and 100–500x over QDLDL. Their method supplies our compress step. It covers only chains, however, and real feeders branch irregularly with varying numbers of children per node. Generalizing odd–even reduction to arbitrary trees through rake-and-compress contraction is the step their paper leaves open.
The third is topology changes handled through low-rank updates. Nguyen et al.'s Penalty+SLFS applies Sherman–Morrison–Woodbury rank-$k$ corrections to an admittance-matrix inverse when switches change. We reuse this idea. The difference lies in what the correction is applied to and how its vectors are stored. We apply it to a tree factor rather than to an inverse. We also exploit the fact that each chord's correction vector is supported on the tree path between the chord's endpoints, which gives it a predictable memory layout rather than an arbitrary gather.
On the sparsity side, SMaT shows that reordering unstructured matrices into dense blocks recovers Tensor Core throughput. SMaT reports up to 125x over cuSPARSE and beats dense cuBLAS at sparsity as low as 78%. Its Jaccard-similarity row permutation is a heavy preprocessing step, though, and the research file flags such preprocessing as prohibitive under dynamic patterns. Radial feeders change topology often, as Yeh et al. and online voltage control under unknown topology emphasize. In this regime, a structure that can be re-derived in linear time from the switch states is the property that matters.
Core Claim
For a feeder with $N$ buses, block size $b$ (three phases times the per-bus variable count), and $k$ closed tie switches, the solver costs:
$$ T_{\text{solve}} = O\!\left(\log N \cdot b^3\right) \text{ parallel stages, plus } O\!\left(k\, \log N \cdot b^3 + k^3\right) \text{ for loop corrections.} $$
The first term follows the rake/compress argument: a constant fraction of nodes is eliminated per round on a bounded-degree tree. The second term counts $k$ extra tree solves and one $k\times k$ dense system. Re-deriving the schedule after branch exchange takes $O(N)$ sequential work, which is trivial next to SMaT-style reordering. We expect a measurable crossover against batched dense LU at small $N$ and against cuDSS at large $N$. The proposal succeeds only if, on the 906- and 8500-bus feeders, the tree solver is faster per batched solve than every baseline below at matched accuracy.
Research Program
We will build the solver in three layers.
The first layer is a schedule builder. It takes switch states, produces the radial spanning tree and the chord set, and assigns each node to a rake or compress round. It runs on the CPU in linear time, or on the GPU via Euler tours.
The second layer is a numerical kernel. It executes each round as batched small dense block operations: block Cholesky or LDLᵀ for the symmetric KKT systems, and LU for the unsymmetric power-flow Jacobian. Memory is laid out scenario-major per tree node so that warps read contiguously. For larger blocks, we will test whether packing across scenarios into Tensor Core tile shapes helps, and we will report honestly if it does not.
The third layer is a chord correction step that applies the path-supported Woodbury update.
We then embed the solver in three workloads. The first is batched Newton power flow over load scenarios. The second is a primal-dual interior-point solver for the linearized distribution OPF that Ryu et al. solve by ADMM, which gives an apples-to-apples comparison. The third is the fixed-point power-flow layer inside Penalty+SLFS training.
For meshed configurations we do not claim convex exactness. A Hybrid Transmission Grid Architecture notes that exactness fails on cycles. The meshed experiments therefore concern only the speed of the linear algebra inside local Newton-type methods.
The analysis component characterizes how the run time depends on four properties of the feeder: depth, branching irregularity, block size, and number of chords. These properties determine when the method should be used.
Baselines
The naive reference point is batched dense LU or Cholesky in cuBLAS on the full block matrix. It has no indexing overhead at all, and on the 13-, 37-, and 123-bus feeders it may well win. We run it at the same batch sizes on the same GPU. Beating it means a faster per-scenario solve at a stated feeder size, and we will report the crossover size rather than hiding it.
The strongest generic competitor is NVIDIA cuDSS, a sparse direct solver that performs symbolic analysis once and then reuses it for numeric refactorization. Schwan et al. report more than 2x over cuDSS on chain-structured systems. For branching feeders, no reported result was found on Lacuna. To keep the comparison fair, cuDSS gets the same fixed sparsity pattern, its best available reordering, analysis excluded from timing when the topology is static, and batched or uniform-batch mode where supported. QDLDL serves as the CPU reference.
The strongest application-level competitor is Ryu et al.'s solver-free GPU ADMM. On the 8500-bus feeder it reports about 668 seconds of wall-clock time against over 44,000 seconds for a 16-CPU implementation, a 50x speedup (Ryu et al.). We run their published setup on the same feeders and GPU with the same primal-residual tolerance. Beating it means lower wall-clock time to equal objective and constraint-violation accuracy.
For topology changes, the competitor is Penalty+SLFS's Woodbury approach on an explicit inverse, as reported by Nguyen et al.: 780–1121x faster inference than IPOPT and a 1.5% optimality gap at 8500 buses. We swap only the linear-algebra layer and require an unchanged gap.
Two ablations isolate the key ingredients. The first replaces rake/compress with plain level scheduling, which gives depth-many sequential stages, and isolates the contraction step. The second replaces chord correction with full re-analysis plus refactorization in cuDSS, and isolates the loop handling.
Why not just…?
Why not just use the classic forward–backward sweep that distribution engineers already run on radial feeders? This is the most serious alternative. The sweep is already a tree algorithm, so for plain power flow on a strictly radial feeder it may match us. It solves only the power-flow equations, though. It does not provide the KKT solves an interior-point method needs, it does not give the Jacobian sensitivities a differentiable surrogate needs, and it handles loops only through approximate compensation. Its sequential depth also equals the depth of the feeder. We include a GPU level-scheduled sweep as a baseline on the power-flow workload. If it matches us there, we will narrow our claim to the OPF and training workloads.
Why not just hand the matrix to cuDSS? A tree has zero fill under any leaf-first ordering, so a generic solver loses nothing in arithmetic. The open question is whether it schedules the many tiny supernodes of a deep, irregular tree well and whether it batches them across scenarios. Schwan et al.'s more-than-2x margin on chains suggests it does not, but that evidence comes from chains, not branching trees. The cuDSS comparison and the level-scheduling ablation settle the question directly. A loss to cuDSS on the 8500-bus feeder would falsify the proposal.
Why not just pad to dense and use cuBLAS? At 8500 buses with three phases, the dense matrix has roughly 25,000 rows and is more than 99.9% zeros, far past the 78% threshold where SMaT finds that dense loses. Batching thousands of such matrices is infeasible in memory. For small feeders this argument does not hold, and the dense baseline determines where our method should not be used.
Proposed Experiments
We use the IEEE 13-, 37-, 123-, 240-, 906-, and 8500-bus feeders. Each is evaluated in its radial configuration and in meshed configurations with 1 to 10 closed tie switches, under 1,000–200,000 load scenarios, matching the 200,000-sample regime of Penalty+SLFS. Measurements are taken on one A100-class and one consumer GPU. We report per-solve latency, throughput in solves per second, end-to-end time to tolerance for linearized OPF, and the training time per epoch for Penalty+SLFS with its optimality gap and violation level unchanged.
Three checks decide the outcome. The first is whether the tree solver beats cuDSS on the 8500-bus feeder in batched mode. The second is whether interior-point OPF with our solver reaches Ryu et al.'s accuracy faster than their 668 seconds on the same hardware. The third is whether chord correction keeps the advantage up to about $k=10$ loops before the $k^3$ term and the extra path solves erase it. We will report the measured crossover against dense LU and the depth sensitivity from the ablation, since these define where radiality actually removes sparsity overhead.
References
- Geometry of Power Flows and Optimization in Distribution Networks
- Hierarchical and Distributed Monitoring of Voltage Stability in Distribution Networks
- A GPU-Accelerated Distributed Algorithm for Optimal Power Flow in Distribution Systems
- A GPU-based Distributed Algorithm for Linearized Optimal Power Flow in Distribution Systems
- GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices
- Scalable Self-Supervised Learning for Multiphase AC-OPF in Distribution Systems with Topology Reconfiguration
- High Performance Unstructured SpMM Computation Using Tensor Cores
- Robust online voltage control with an unknown grid topology
- A Hybrid Transmission Grid Architecture Enabling Efficient Optimal Power Flow