CS Paper Radar

The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering

Deniz Elbek, Yiğit Manafi, Zeynep Gürdal, Sinan Yıldırım, Kamer Kaya

cs.DS ·submitted 2026-08-15 19:44 UTC · v1

Abstract

Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, they do not directly address the choice of the next vertex. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with O(n + m) total bucket-maintenance work per trajectory, where n is the number of rows/columns in the matrix and m is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show that it is competitive with the state of the art on the tested small matrices and scales effectively to large sparse matrices.

Closest papers

Nearest neighbours by meaning across the whole index.

Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows

cs.DM cs.DSmath.PR ·2026-08-27 ·Xiaoyu Chen, Eric Vigoda, Xiongxin Yang
highly cited similarity 0.63
Abstract

The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was improved by Bezáková, Štefankovič, Vazirani, and Vigoda (2008) to $O(n^7\log^4 n)$ for $0/1$ matrices, for any fixed approximation and success parameters. We present the first asymptotic improvement over this running time bound, obtaining an $O(n^6\log^5 n)$-time algorithm. As in the previous works, our algorithm extends to arbitrary nonnegative matrices. The analysis of Bezáková et al. yields an $O(n^4)$ relaxation time bound for the JSV Markov chain on perfect and near-perfect matchings with ideal hole weights, under which each hole pattern (the unmatched vertices, if any) is equally likely in the stationary distribution. We introduce a restricted Poincaré inequality for the partition into hole patterns and prove an $O(n^3)$ bound on the corresponding restricted relaxation time. Our proof uses a coupled multicommodity flow argument inspired by a recent transport-flow argument of Chen et al.~(2025) for the Jerrum-Sinclair chain on all matchings.

0.46

How the Dirty Set Moves: Characterizing Schedule Reuse in Incremental Sparse Matrix Multiplication

cs.PF cs.DCcs.MS ·2026-10-14 ·Hunter Horne, Eric Spencer, Alex Henningfield, Arslan Bisharat
similarity 0.62
Abstract · 12 pages, 7 figures, 8 tables

Sparse matrices, in which most entries are zero, are central to scientific simulation, graph analytics and machine learning, and their multiplication with dense inputs is a core parallel kernel. In many applications the matrix stays fixed while only a few input rows change per step, so the result can be updated from those rows alone, which we call the dirty set. Sparse kernels often add a second optimization based on the inspector-executor principle, in which a tiled schedule is prepared once and reused across calls. However, when this reuse remains profitable as the dirty set moves is not well characterized. In this paper, we show that retained tiled execution rarely beats direct CSC in incremental sparse matrix multiplication, although incremental execution itself remains highly profitable. Across 21 SuiteSparse matrices and controlled patterns of motion, a direct column-wise incremental update is 2.1-8.2x faster than the best of eight full-recomputation codes, among them Intel oneMKL and PyTorch. Yet the same direct update outperforms a tiled executor that retains tile preparation and caches assembled schedules in 779 of 837 workloads. Separating reuse into per-tile preparation and cached schedules shows that the benefit comes from preparation; extra cache capacity seldom helps because a tile set rarely returns after a different one has intervened. Tiling is faster only when tiles merge many entries into each output write, a structural property that we predicted before measurement and confirmed on four held-out matrices of the same family. These results show that the structure of the matrix and the motion of the dirty set, rather than the sophistication of the schedule, determine whether reuse is profitable. We anticipate that our methodology and guidelines will help developers decide when to build schedule reuse into incremental sparse runtimes.

0.34

Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

cs.LG stat.ML ·2026-08-21 ·Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg, Jeff Soules, Diana C. Halikias
similarity 0.60
Abstract

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.

0.38

Pattern-Based Matrix Analysis Under Permutations

cs.LG ·2026-11-13 ·Andrei Ermakov
top venue similarity 0.60
Abstract · Accepted at NeurIPS 2026 (The Fortieth Annual Conference on Neural Information Processing Systems)

Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.

0.38

Faster high-accuracy multicommodity flow in dense graphs

cs.DS math.OC ·2026-10-05 ·Chenxin Dai, Alicia Stepin, Colin Tang
publishedhot direction similarity 0.58
Abstract · ITCS27 submission with updates

We give a fast algorithm for solving min-cost $k$-commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1/k$ times the minimum value of the original problem (thus, solving this auxiliary linear program will make at least $1/k$ fraction of progress in the original problem). Low-rank linear programs can be solved quickly using black-box techniques. Thus, our algorithm runs in time $\tilde{O}(\operatorname{poly}(k)(n^{2.5}+m\sqrt{n}))$ on a directed graph with $n$ vertices and $m$ edges. We do not rely on any fast matrix multiplication.

0.36

Dual-Slack Frontier Matching: Parallel Approximate Maximum-Product Matching

cs.DS ·2026-11-12 ·Marc A. Tunnell, Oguz Selvitopi, Xiaoye Sherry Li
similarity 0.58
Abstract

Maximum-product bipartite matching supports scaling and static pivot selection in sparse matrix preprocessing. We present Dual-Slack Frontier Matching (DSFM), a deterministic, shared-memory parallel algorithm for approximate maximum-product matching. Motivated by heavy matchings on small candidate supports, DSFM searches progressively exposed subgraphs ordered by fixed dual slack. Slack-ordered certified completion guarantees a perfect matching whenever one exists, or a maximum-cardinality matching with a Hall certificate otherwise. Every returned perfect matching carries an a posteriori geometric-mean quality bound; accumulated Hall obstructions can tighten this bound and improve the returned scaling. We compare DSFM with Heavy-Weight Perfect Matching (HWPM) and exact MC64 assignment on 598 nonsingular matrices. DSFM attains higher matching quality than HWPM over most quality thresholds. On a set of large instances consisting of 37 matrices, DSFM achieves a $3.53\times$ geometric-mean speedup over MC64, compared to $2.29\times$ for HWPM.

0.32

Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision

cs.DS ·2026-10-19 ·András Czégel
similarity 0.58
Abstract · Submission document to QOBLIB

The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the third part runs a beam search over steps that each make at least one entry zero. On 375 test instances with up to 100 rows, the method proves optimality for 208 instances, and 197 of these proofs also hold for real weights. Of the 190 instances built from few permutation matrices, 187 are solved to proven optimality, 180 of them within one second. Compared with the best exact decompositions known before, the new decompositions are shorter for 278 instances and never longer.

0.25

A Sparse Low-Rank Biclique Decomposition for Graphs

cs.LG ·2026-11-19 ·Antoine Vialle, Sergei Gerasimov, Aref Einizade, Antonio Ortega, Fragkiskos D. Malliaros +1 more
top venuecode/data similarity 0.57
Abstract · Accepted at NeurIPS 2026. 29 pages, including references and appendices

Low-rank plus sparse decompositions, such as robust PCA, typically model the low-rank component as dense and the sparse component as corruption. This viewpoint is poorly suited to graph adjacency matrices, where sparsity is structural and dense low-rank factors destroy the combinatorial and computational properties of the graph. We propose signed biclique decomposition (SBD), a sparse low-rank decomposition for integer-weighted graphs that represents the structured component as a sum of sparse signed binary rank-one factors, together with a sparse signed residual. The resulting representation remains discrete, interpretable, sparse, and compatible with standard linear algebra. We formulate fixed-rank and greedy SBD objectives and derive a gain-based greedy algorithm with theoretical guarantees. Empirically, SBD recovers block structure in noisy graphs, while its factorized representation enables efficient sparse matrix-matrix multiplication (SpMM). On real graphs with strong shared-neighborhood structure, SBD achieves compression factors above $10$ and SpMM speedups up to $6\times$ over cuSPARSE, suggesting a practical alternative to dense low-rank decompositions for graphs. Code is available at https://github.com/IAntoineV/sbd.

0.50