CS Paper Radar

The Mode of Null-A: Compositional Computation of a Generalized Inverse

Barak A. Pearlmutter, Jeffrey Mark Siskind

cs.PL math.NA ·submitted 2026-09-29 20:22 UTC · v1

Abstract

We present a novel algorithm for calculating the preimage of an affine space through a product ${J}={J}_{T-1}\cdots{J}_0$ of matrices ${J}_t$ of special form: finding the largest input space $\mathbf{X}$ such that $\mathbf{x}\in\mathbf{X}$ implies ${J}\mathbf{x}\in \mathbf{Y}$, where $\mathbf{Y}$ is a given output affine space. These special matrices arise in AD, where the Jacobians $J$ describing the linearized computation have precisely this structure: the product of a series of linearized primitive numeric operations. This allows us to use the new algorithm to formulate Null-A mode preimage AD, which finds the affine preimage through the Jacobian or Jacobian transpose of a numeric computation. This is a generalization of the inverse AD problem of solving ${J}\acute{\mathbf{x}}^{\ast}=\acute{\mathbf{y}}^{\ast}$ or ${J}^{T}\grave{\mathbf{y}}^{\ast}=\grave{\mathbf{x}}^{\ast}$. The key is to represent affine spaces in a fashion which lends itself to efficient preimage calculation, in a compositional and quasi-local fashion, through a succession of matrices ${J}_t$. Unlike previous methods, Null-A preimage mode AD allows the ${J}_t$ matrices to be non-square, corresponding to a computer program whose number of active variables swells and shrinks during the computation. When ${J}$ is square and the initial affine space is a single point, this finds the conventional inverse. But in the more general case, having the entire affine space provides freedom which can be leveraged in a problem-specific manner. We apply the method to small problems on-CPU where the $J_t$ are linearized scalar unary or binary numeric functions; and to larger problems on-GPU where the $J_t$ are linearized aggregate array operations like convolution and attention.

Comment
Submitted to ICLR 2027

Closest papers

Nearest neighbours by meaning across the whole index.

AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

cs.AI math.OC ·2026-08-14 ·Kenan Xu, Xiangfeng Wang
similarity 0.54
Abstract · 34 pages

The alternating direction method of multipliers (ADMM), as a landmark algorithm, has attracted tremendous research attention and extensive practical applications over the past two decades. It is well known that, although the two-block ADMM enjoys well-established theoretical convergence guarantees, its direct extension to the three-block case may fail to converge, as demonstrated by existing counterexamples [5]. However, to the best of our knowledge, the case in which the third constraint block is the identity remains unresolved: the existing literature gives neither a general convergence proof nor a counterexample for this subclass. In this paper, we give a negative answer: direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics. Using Codex with GPT-5.6 Sol, we construct an explicit rational counterexample candidate and verify it along a piecewise-affine reduction path; exact checks show that direct three-block ADMM on this instance produces a bounded nonconvergent orbit of period 66. Within the same Codex workflow, we further guide a study of multiplier relaxation and clarify when convergence can be restored at the fixed-instance and class levels: a problem-dependent small dual step can restore convergence, whereas no positive relative step works uniformly over the whole class. Furthermore, we also test the recent Kimi Code with Kimi K3 model without the Codex candidate or project-specific route guidance; along a different path it produces an exact locally attracting period-23 certificate, convertible to an equivalent all-identity instance. The comparison suggests that different research-harness configurations can shape the mathematical objects explored and the certificates pursued.

0.40

Inverse Problem for Super-linearization with Single Observable and Diagonalizable Principal Submatrix

eess.SY math.DS ·2026-11-16 ·Haoyu Yin, Xudong Chen
similarity 0.54
Abstract

Super-linearization is, roughly speaking, embedding an $n$-dimensional nonlinear dynamical system into an $(n + m)$-dimensional linear system. We introduce and address, in this paper, the inverse problem: given a linear system $\dot x= M x$, what type of dynamical systems can be super-linearized to it? We focus on the special case where the dimension reduction is one (i.e., $m = 1$) and the leading $n$-by-$n$ principal submatrix of $M$ is diagonalizable, and provide a solution to the problem.

0.28

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

cs.DS ·2026-11-06 ·Marco Pirazzini, Daniel A. Spielman
similarity 0.53
Abstract · 31 pages, 6 figures

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)$ (Objois and Vladu, 2026), which is slower when high accuracy solutions are desired. Our algorithm employs a surprising application of Laplacian solvers inside an Interior Point Method (IPM). We formulate the problem as a linear optimization problem over a product of power cones, and show that the Newton updates of the IPM can be computed by solving a Laplacian system in a Schur complement after subtracting a rank-2 matrix. We also discuss an implementation of our algorithm, showing that it is practical and it outperforms optimized solvers such as MOSEK by factors of up to $20\times$ on a variety of tasks.

0.31

Worst-Case to Average-Case Reductions for Basic Linear Algebra

cs.DS cs.CC ·2026-11-02 ·Or Zamir
similarity 0.53
Abstract

We study worst-case to average-case reductions for basic linear-algebraic problems over finite fields. A seminal work of Blum, Luby, and Rubinfeld established that any algorithm that successfully multiplies more than $75\%$ of matrix pairs over any finite field, implies an algorithm with essentially the same running time multiplying any pair of matrices. A sequence of follow-ups reduced the needed fraction of successful input pairs to any positive constant. Despite most of the other basic linear algebraic operations being computationally equivalent to matrix multiplication in the worst case, no such worst-case to average-case reductions were known for them. Recently, Vaikuntanathan and Zamir introduced a cryptographic primitive called trapdoor matrices and used them to prove such worst-case to average-case reductions for matrix inversion, solving a linear system, and computing the determinant, all conditioned on common cryptographic assumptions. Our main result is the first unconditional time-preserving worst-case to average-case reduction for matrix inversion. Any algorithm that correctly inverts any constant positive fraction of uniformly random invertible matrices implies a worst-case such algorithm. We also significantly strengthen the conditional reductions based on trapdoored matrices: We establish reductions for deciding invertibility and computing rank at the optimal success thresholds, and qualitatively improve the success threshold needed in the reduction for determinant computation---while previous reductions all required the success probability to be at least $1/2$, we show that any fixed positive average-case success probability suffices for exact worst-case determinant computation over infinitely many finite fields.

0.30

Basis Rigidity of the AES S-box and Generic Rigidity of Inversion under Affine Transformations

cs.CR math.RA ·2026-09-12 ·Zheng Zhang, Na Zhang
unusual similarity 0.52
Abstract

The AES S-box is constructed from finite field inversion followed by a fixed affine transformation. Since inversion possesses intrinsic Frobenius symmetries among its coordinate realizations, we study how these basis symmetries are altered by outer affine transformations. We first develop a deterministic rigidity criterion for transformed inversion and apply it to the AES S-box. This shows that the linear part of the AES S-box affine transformation alone makes the transformed inversion map basis rigid. We then investigate the corresponding generic problem when the outer invertible linear transformation varies. The existence of a nontrivial linear stabilizer is reduced to a conjugacy problem for semilinear candidates arising from two sided linear equivalences of inversion, which we characterize in terms of relative norms and Frobenius orbits. We also determine the dimensions of the associated centralizer algebras exactly. These structural results imply that, for a uniformly chosen outer linear transformation, the probability that the linear stabilizer is nontrivial is bounded by $2^{-Ω(n^2)}$, with sharper finite dimensional bounds obtained from the exact conjugacy condition. Computational experiments independently verify the AES rigidity result, the conjugacy and centralizer formulas, and the finite dimensional estimates in small dimensions.

0.27

Solving Square-Submatrix Equation Systems

cs.DS ·2026-08-13 ·Lorenzo Carfagna, Giovanni Manzini
similarity 0.52
Abstract · 11 pages, 3 figures

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.

0.10

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

cs.DS cs.CCmath.NA ·2026-09-29 ·Jonathan A. Kelner
similarity 0.52
Abstract

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.

0.09

Grassmann: The Coordinate-Independent Linear Algebra Programming Language

cs.PL cs.MS ·2026-10-30 ·Theadora Fields Collin, Gilbert Bernstein, Oded Stein, Saman Amarasinghe
similarity 0.52
Abstract · 147 pages, including references and appendices

Scientists, engineers, and mathematicians often formulate algorithms using coordinate-independent linear algebra because its tools are composable and harder to misuse. For numerical processing, however, users must translate these ideas into coordinate-dependent array code. Most practitioners do so prematurely because tools such as NumPy lack coordinate-independent representations, while existing languages with such constructs do not model enough linear algebra for the situations where they matter. We propose Grassmann, a small language bridging coordinate-independent linear algebra and coordinate-dependent implementations. It uses dependent types, linear types, and partially (pseudo-)invertible computation to model situations arising in exterior algebra and differential geometry. It targets the linear algebra at a point on a manifold, a prerequisite for many specifications in scientific computing and computer graphics. A language for coordinates lets users move between these representations. We give a denotational semantics assigning meaning without coordinates and an operational semantics translating Grassmann to array code under a choice of coordinates. Our main metatheoretic result shows that operational evaluations agree with the denotational semantics under an arbitrary choice of coordinates. This models how practitioners translate linear algebra for computers and suggests an approach to algorithmic optimization at a high level of abstraction. Our optimized implementation generates code for exterior algebra operations with overheads no more than 10%.

0.25