Certified-Synchronous Sparsification for GPU Tiles

Many engineered and simulated systems are networks of coupled oscillators. Examples include power-grid generators, neural population models, consensus controllers and laser arrays. In each, a sparse coupling matrix decides whether the units lock into a common rhythm. On a GPU, simulating large batches of such networks comes down to repeated sparse matrix products, for instance to sweep fault scenarios or estimate the critical coupling. Those products run slowly because the nonzeros are scattered. Fast kernels such as SMaT recover speed by reordering rows so the nonzeros fall into small dense tiles that matrix-multiply hardware can process. Physical graphs are very sparse, though, and many tiles end up holding a single edge.

This note proposes to edit the coupling graph itself so that it occupies fewer tiles, while keeping a mathematical guarantee that the network still synchronizes. Two facts make this possible. First, synchronization theory gives a cheap, checkable sufficient condition for phase locking that depends on the whole graph, not just its densest parts. Second, on tiled hardware an edge placed inside a tile that is already being computed costs nothing extra. The claim is that we can drop the expensive isolated edges and add free edges inside occupied tiles, trading one for the other under the certificate. The result should be a sparser memory footprint, faster batched simulation, and in some cases a lower synchronization threshold than the original graph.

Core Claim

Gap 1 in the research file worries that hardware-friendly permutations damage synchronizability, and that worry rests on a mistake. Reordering rows and columns together, which is what tile-packing does to a coupling matrix, only relabels nodes. It leaves the Laplacian spectrum, path lengths and degree distribution unchanged. The same mistake runs through the supposed contradiction in Gap 4. Topological Control of Synchronization Patterns: Trading Symmetry for Stability shows that the most stable topology is asymmetric. The hardware, by contrast, demands regularity only in the memory layout after relabeling, not in the graph itself.

The real coupling between the two fields appears only when edges are added or removed to make tiles denser. Our claim is that this edge editing should be governed by a synchronization certificate, not by spectral proxies or magnitudes. We also claim that the cost model of tiled hardware, where in-tile edges are free and lone edges in a tile are expensive, creates a Pareto frontier between tile count and critical coupling that nobody has measured.

The certificate is assembled from two results in the file. Dörfler et al. show that coupling stays restorative only while every edge's phase difference stays below $\pi/2$; past that point the sine coupling flips sign and pushes the units apart. Chertkov shows that the threshold is set by how the vector of natural frequencies $\omega$ projects through the Laplacian pseudo-inverse $L^\dagger$. Combining them gives the standard edge-flow test. A phase-locked state with all edge differences within $\gamma<\pi/2$ is guaranteed when

$$\left\| B^\top L^\dagger \omega \right\|_\infty \le \sin\gamma ,$$

where $L$ is the weighted Laplacian with coupling $K$ folded into the edge weights, $B$ is the incidence matrix with rows weighted by edge weight, and the infinity norm takes the worst edge. Like the bound in Synchronization and transient stability in power networks and non-uniform Kuramoto oscillators, this condition is sufficient but conservative. We treat that conservatism as something to measure, not to assume away.

The editing problem then picks a node relabeling $P$ and an edited weighted edge set $E'$. It minimizes $T(P,E')$, the number of occupied $16\times 8$ tiles in the SMaT layout. It does so subject to the certificate holding with margin $\sin\gamma$ for every frequency scenario in a set $\Omega$, either sampled from a distribution or chosen adversarially.

Research Program

The method runs in three stages.

The first stage relabels nodes for free. We use SMaT's Jaccard-similarity row reordering from High Performance Unstructured SpMM Computation Using Tensor Cores, applied symmetrically so that it remains a relabeling.

The second stage scores every edge on two axes. One axis is its tile cost: does removing it empty a tile? The other is its certificate impact: how much does removing it, or adding an in-tile edge, change the worst edge flow? We never form $L^\dagger$, whose $O(N^3)$ cost the file flags as an open scalability problem. Instead we compute $x=L^\dagger\omega$ for each scenario with a warm-started sparse Laplacian solve. A single edge edit changes $L$ by a rank-one term, so its effect on $x$ follows from one extra solve and a Sherman–Morrison update.

The third stage edits greedily. It removes edges that empty tiles while slack remains. When slack runs low, it adds or upweights edges inside already-occupied tiles, which costs no extra hardware work, choosing the edges that most reduce the worst edge flow. It then re-relabels only occasionally. The edits act on the topology of the coupling graph, which is closer to Asymmetry-induced synchronization in oscillator networks than to weight shrinkage.

The work has two regimes. In the design regime, the topology is a free choice, as for oscillator arrays, consensus controllers or reservoir-style recurrent networks. There the deliverable is the cheapest certified topology together with the frontier between tile count and critical coupling. In the surrogate regime, a fixed physical network is being simulated. There the edited graph must also keep the trajectories close to those of the original, so free in-tile additions are restricted and we report trajectory error alongside the certificate. Chaotic units such as Lorenz oscillators do not fit the Kuramoto test. For them we replace it with a constraint on the Laplacian eigenratio $\lambda_N/\lambda_2$, the quantity used in the master-stability analysis of Topological Control of Synchronization Patterns: Trading Symmetry for Stability.

This differs from the closest prior work in what it constrains and what it costs. Sparse Spiking Neural Network: Exploiting Heterogeneity in Timescales for Pruning Recurrent SNN prunes recurrent spiking networks while preserving Lyapunov stability. It ignores memory layout, measures no wall-clock time, and does not use phase-locking conditions. Connectivity Matters: Neural Network Pruning Through the Lens of Effective Sparsity checks reachability in feedforward graphs, not dynamical thresholds. SMaT optimizes layout but treats the matrix as fixed. The decentralized-optimization line, such as A Unified Theory of Decentralized SGD with Changing Topology and Local Updates, uses spectral mixing gaps for algorithmic consensus over network links, not for phase locking or on-chip cost.

Baselines

The naive reference points are dense cuBLAS and cuSPARSE run on the unedited coupling matrix, using batched multiplication over $B$ frequency scenarios. These set the floor that any sparse method must clear.

The strongest existing method is SMaT applied to the unedited graph after its own reordering. It is the strongest competitor because it already extracts tile-level speed from unstructured patterns without changing the dynamics at all. Okanovic et al. report on an A100 that SMaT is on average 2.6x faster than the next-best library (DASP) and up to 125x faster than cuSPARSE across nine SuiteSparse matrices with 766K to 10.4M nonzeros, and that it beats dense cuBLAS at sparsity as low as 78%. We will run SMaT and our edited graphs through the same SMaT kernel on the same GPU, with identical batch sizes. Our editing time will be reported and amortized honestly over the number of simulation steps. Beating SMaT means a lower wall-clock time per batched step at an equal measured synchronization outcome: the same fraction of scenarios locking and a critical coupling within 5%. Edit time must be included once amortized over a realistic simulation length. No reported result was found on Lacuna for any method that sparsifies coupling graphs for hardware while preserving synchronization, so there is no prior number for the full task.

Three ablations isolate the key ingredients. The first is λ2-constrained editing, which uses the same greedy procedure but keeps the algebraic connectivity $\lambda_2$ above its original value instead of using the edge-flow certificate. It tests whether the frequency-aware $L^\dagger\omega$ projection matters, as Chertkov's result predicts. The second is hardware-oblivious certified editing, which uses the certificate but scores edges by flow alone, without tile cost. It tests whether tile awareness is what buys the speed. The third is drop-only editing, which forbids free in-tile additions. It tests whether the free-edge mechanism, and with it the asymmetry-induced gains, contribute anything.

Why not just…?

Why not just run SMaT on the original graph and accept the result? This is the main threat. If physical coupling graphs already pack well after Jaccard reordering, editing buys little. The file's own evidence cuts both ways. SMaT's gains are reported on scientific matrices, and Okanovic et al. reduced the spread of blocks per row on mip1 by 8.4x. Low-degree graphs, however, may leave many tiles nearly empty even after reordering. The first experiment measures tile fill for SMaT on the unedited graph. If median fill is already high, we will report that and narrow the claim to the design regime.

Why not just enforce 2:4 or 4:8 structured sparsity? The SR-STE results in Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch (ResNet-50 at 77.0% under 2:4 against a 77.3% dense baseline) concern matrices that are about 50% dense. Coupling graphs are typically more than 99% sparse, so the pattern would be stored as mostly padding. It would also cap each node's local connections in a way that can cut the long-range edges that hold synchronization together. We will include a 2:4 run on one moderately dense synthetic graph to show this concretely.

Why not just keep λ2 above a threshold? It is cheap and familiar, as in the robot connectivity work of Realm: Real-Time Line-of-Sight Maintenance in Multi-Robot Navigation with Unknown Obstacles. However, Chertkov shows that the threshold depends on where the divergent oscillators sit relative to $L^\dagger$, and Relations between average distance, heterogeneity and network synchronizability shows that single spectral or centrality summaries mispredict synchronizability on scale-free graphs. The λ2 ablation, run with adversarial ω placed at peripheral nodes, decides this directly.

Why not just treat the matrix as dense? At the sparsity of physical networks, dense arithmetic wastes nearly all of its work, and SMaT already beats cuBLAS at 78% sparsity. The dense baseline is reported for completeness rather than as a serious competitor.

Proposed Experiments

We will use three graph sources. The first is symmetrized patterns from the SuiteSparse collection in the same size range SMaT evaluated. The second is synthetic graphs produced with the random interchanging procedure of Zhao et al., which varies average path length and degree heterogeneity independently. The third is small symmetric clusters matching the 6-node optoelectronic setting of Sorrentino et al., where breaking symmetry dropped the eigenratio from 4 to 1. Frequency scenarios will be drawn both from Gaussian distributions and adversarially, aligned with the dominant directions of $L^\dagger$. For chaotic units we use networks of Lorenz oscillators, following the regime mapped by Zhang et al.

Each configuration reports occupied tiles, stored nonzeros, and A100 wall-clock time per batched step. It also reports the certificate-predicted critical coupling, the simulated critical coupling (found by sweeping $K$ and measuring the order parameter), and the fraction of scenarios that lock. In the surrogate regime it adds phase-trajectory error against the original graph.

Three decisive checks follow. The first asks whether certified editing reaches lower step time than SMaT on unedited graphs at matched simulated synchronization, which determines whether the idea is worth anything. The second asks whether λ2-constrained editing loses synchronization under adversarial frequencies where the certificate does not, which determines whether the frequency-aware certificate is necessary. The third asks whether free in-tile additions lower the simulated critical coupling below the original graph's while reducing tile count. That would show that the claimed tension between asymmetry-driven stability and hardware regularity is largely an artifact of conflating graph structure with memory layout. As a secondary analysis, comparing certificate-predicted and simulated thresholds along the frontier will quantify how conservative the sufficient bound is in practice, the open problem flagged for Dörfler and Bullo's condition.