CS Paper Radar

Expressing NumPy Broadcasting via Verb Rank in J

Marcin Żołek

cs.PL cs.MS ·submitted 2026-09-13 11:17 UTC · v2

Abstract

The array programming paradigm applies operations to entire arrays rather than individual elements, eliminating explicit loops and abstracting many low-level details of computation. Two influential approaches have shaped array programming: NumPy's broadcasting and Kenneth Iverson's array-oriented notation, with the latter first introduced in APL and later developed in the J language. Although NumPy's array programming model was influenced by Iverson's work, the two systems formalize array operations differently: NumPy primarily through array shapes and broadcasting, and J through verb rank. This paper establishes a formal correspondence between NumPy broadcasting and J rank and presents an implementation of NumPy broadcasting in J. The results provide a formal connection between two influential approaches to array-oriented computation and show how they address the common problem of applying operations to arrays with differing shapes without explicit loops.

Closest papers

Nearest neighbours by meaning across the whole index.

Vectorizer: Vectorizing NumPy Programs with Shape-Guided Rewrite

cs.CL cs.SE ·2026-09-08 ·Jingqian Liu, Xiaoyu Liu, Yuepeng Wang
similarity 0.64
Abstract

NumPy is a widely used Python library for numerical scientific computing, known for its declarative APIs and its optimized implementations. However, writing efficient NumPy programs, which often entails using vectorized array operations instead of explicit Python loops, may not be straightforward. This can be difficult for programmers who are accustomed to imperative array traversal, especially when vectorized API invocations require careful reasoning about shapes, broadcasting, and advanced indexing. This paper presents a rewrite-based approach for vectorizing Numpy programs with explicit loops over array data. Our approach vectorizes loops from the inside out, using array shapes and dataflow analysis to guide a source-to-source transformation that replaces loop bodies with vectorized statements. Following a set of rewrite rules that are correct by construction, our approach is consistently fast. We have implemented the approach as a tool called Vectorizer and evaluated it on 150 benchmarks collected from prior work and Stack Overflow. The evaluation shows that Vectorizer vectorizes 142 of the 150 benchmarks directly and 2 more after minor changes to the original benchmarks, with only 0.53 seconds on average to rewrite each one. The resulting programs are, on average, 74.83x faster than the original loop-based implementations.

0.29

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.58
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

The Mathematical Evolution of Addressing: From Yushchenko's Address Programming Language to A Mathematics of Arrays How Addressing Evolved into a Mathematical Theory of Indexing, Array Computation, and Machine Realization

cs.GL cs.PL ·2026-09-20 ·Lenore Mullin, Gaetan Hains
similarity 0.57
Abstract

This article argues that a central development in the history of computing is the mathematical evolution of addressing. During the three decades separating Kateryna Yushchenko's Address Programming Language (1958) from Lenore Mullin's A Mathematics of Arrays (1988), addressing evolved from a machine-level mechanism for locating data into a formal theory of indexing, reduction, and machine realization, passing through Kenneth Iverson's algebra of arrays and Philip Abrams' recognition of shape as an architectural resource. Mullin's theory establishes indexing itself, via the function ψ, as the primitive from which array operations compose, reduce to a Denotational Normal Form, transform into an Operational Normal Form, and realize on hardware through dimension lifting. Historical claims are sourced against primary material, with inferences flagged as such; mathematical claims are stated as identities; performance claims are marked validated, theoretically established, or provisional. The result links programming languages, array mathematics, and computer architecture in one account.

0.23

Rank-metric intersecting codes

cs.IT math.CO ·2026-11-03 ·Martino Borello, Martin Scotti, Lune Vila
similarity 0.55
Abstract · 18 pages

Intersecting codes are codes in which any two nonzero codewords share a common nonzero coordinate, and they have been extensively studied due to their applications in communication theory, cryptography, and combinatorics. Recently, geometric interpretations have provided new insights into intersecting codes, both in the Hamming metric and, more recently, in the rank metric for linear codes. In this paper, we introduce and study matrix rank-metric intersecting codes. By defining the support of a matrix as its row space, we extend the notion of intersecting codes to the matrix rank-metric setting. Using the slice space associated with the generator tensor of a rank-metric code, we derive a geometric characterization that is equivalent to the intersecting property. This characterization generalizes the known results for linear rank-metric intersecting codes and highlights both analogies and differences with the linear case. In particular, it yields bounds on the parameters of intersecting codes, one of which is sharp and differs from the one in the linear case, together with first constructions. We then consider codes that are closed under multiplication, i.e. matrix algebras. In this setting, the intersecting property can be read off from the algebraic structure, namely the Jacobson radical and the socle. This provides a simple and flexible way to construct many intersecting codes, including codes that do not satisfy the classical sufficient condition on the minimum distance.

0.08

Representing Tensors as Compositions for Efficient Computation on Sparse and Structured Data

cs.LG cs.MScs.PL ·2026-11-07 ·Valérian Rey, Praneth Paruchuri
code/data similarity 0.50
Abstract · 15 pages, 6 figures

We propose a new mathematical formalism in which all kinds of tensors and of operations on those tensors are represented as simple function compositions. Tensors are functions from indices to values. An element-wise operation (e.g. an activation function) is a composition with a function applied to values; re-indexing (e.g. reshape, transposition) is a composition with a function applied to indices; and a reduction is a composition with both an index function, mapping each index to several indices, and a reduction operation (e.g. product, sum, max). Combined with tensor stacking, these compositions can represent most interesting kinds of tensors (e.g. dense, jagged, all kinds of sparsity patterns, matrix factorizations), as well as lazy versions of almost every operation available in modern tensor computation frameworks, including einsums between tensors of any kind. Identities between compositions can then be used to rewrite such expressions into equivalent ones, without evaluating them. For instance, the product of two sparse matrices can be rewritten so that only products between non-zero values are computed, turning a sparse problem into a dense one. Using this algebra as the intermediate representation of a tensor computation engine would shift the focus from defining operations on tensors (e.g. einsum between sparse tensors) to defining an algebra on index functions. This should reduce the codebase complexity from $\mathcal{O}(mn^2)$, with $m$ the number of binary operations between tensors and $n$ the number of tensor types, to $\mathcal{O}(m + k^2)$, with $k$ the number of types of index functions. A draft implementation of a tensor computation framework based on this algebra is publicly available.

0.21

A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication

cs.DS cs.CCcs.SC ·2026-09-26 ·Joshua Stapleton, Andrew Perminov
code/data similarity 0.49
Abstract · 7 pages. Certificate and verification code: https://github.com/Joshua-Stapleton/51-addition-alt-basis-3x3-rank23

We give a rank-23 algorithm for $3\times3$ matrix multiplication using 51 additions and subtractions in alternative bases. The input and output conversions require five further additions, giving 56 additions in ordinary coordinates. The construction combines linear-program reduction with a search over sparse basis changes, and the resulting programs are distributed as a machine-checkable certificate. We verify correctness by exact coefficient expansion and distinguish the kernel cost from the cost of a complete multiplication.

0.47

Cyclotron: A Recurrence Language for Expressing Interprocessor Communication

cs.DC ·2026-10-14 ·Shiv Sundram, Akhilesh Balasingam, Nathan Zhang, Kunle Olukotun, Fredrik Kjolstad
similarity 0.48
Abstract

We present Cyclotron, a compiler that expresses streaming dataflow algorithms using recurrence equations, which are then compiled to distributed topologies of interlinked processors. Our compiler lowers a language of recurrences over logical iteration spaces into per-processor programs of sends, receives, and computations. In these recurrences, data accesses are not limited to external accesses to memory; data can live separately on the iteration space itself, allowing internal points to communicate values directly with other points. Users specify this communication directly in the recurrence language, which allows them to express various communication patterns such as a nearest-neighbor systolic exchange, a one-to-all broadcast, a bidirectional split ring, or an asymmetric and piecewise broadcast pattern, which are often not supported by standard distributed linear algebra libraries. These recurrences describe the algorithm and communication independently of how they map onto the hardware. A programmer then chooses which dimensions execute across processors and which execute over time, without rewriting the entire program. Users only specify data dependencies across the iteration space, and the compiler safely generates a program, per process, with correct placement of both communication and computational operators according to the chosen space--time mapping. We evaluate distributed matrix multiplication, TRSM, Cholesky, and fused Cholesky--TRSM on up to 16 CPU nodes and 16 GPUs, comparing against ScaLAPACK, SLATE, and cuSolverMp. Cyclotron is competitive with and often outperforms these hand-optimized libraries; for Cholesky, the best communication strategy changes with problem size and architecture.

0.25

RPyForth: Exposing a Call-Shared Data Stack to a Meta-Tracing JIT Compiler

cs.PL ·2026-09-20 ·Yusuke Izawa, Kota Hakamada
similarity 0.47
Abstract · 33 pages, 15 figures

Forth is a concatenative language whose words share one data stack across calls, with a depth and call effects that need not be known before execution. That leaves a meta-tracing JIT compiler with no stack location it can name: a cell is reached through the stack pointer, so its accesses stay in the compiled code, and declaring every cell of the stack array instead ties what the compiler carries to the capacity the array reserves rather than to the depth a program uses. We answer with a fixed-width window over the top of the stack, a shared spill holding every deeper cell, and a decoding function that joins the two, on top of which call-entry normalization and adaptive entry are policies. Decoding shows that all of them preserve the logical stack and that a trace exit rebuilds data-stack state bounded by the window's width, not by the stack's depth. RPyForth realizes this in an RPython interpreter covering Forth's Core word set, with two scalar fields and eight frame positions and no static stack-effect analysis, and RPyFactor realizes the same window for a subset of Factor. Exposing the window to the compiler, rather than merely caching cells in it, is what pays. With the layout and the call policy held fixed, annotating the window's fields makes eighteen Shootout kernels 1.44-1.45x faster and six Appbench applications about 1.60x faster on two x86-64 machines, and 1.42-1.56x in RPyFactor. How the window is shaped and whether calls normalize it matter much less, varying by program with no setting winning everywhere. As a complete system, RPyForth is faster than gforth-fast and SwiftForth on both suites and reaches 1.90-2.36x the speed of VFX Forth on the kernels, while the applications, whose stacks are deeper and whose calls are far more frequent, remain its weak point at 0.68-0.76x. All timings measure repeated execution of an already-loaded program.

0.30