+++ title = “How htpy Computes” section = “mathematics” +++

How htpy Computes

htpy computes Ext groups over the Steenrod algebra by constructing minimal free resolutions. This page gives an overview of the computational pipeline.

Minimal resolutions

To compute $\operatorname{Ext}_A(M, \mathbb{F}_p)$, htpy constructs a minimal free resolution

$$\cdots \to F_2 \xrightarrow{d_2} F_1 \xrightarrow{d_1} F_0 \xrightarrow{\varepsilon} M \to 0$$

where each $F_s$ is a free module over the Steenrod algebra. “Minimal” means that the differentials have no linear (degree 0) component, which ensures that the resolution is as small as possible.

The dimension of the degree-$t$ part of $F_s$ equals $\dim \operatorname{Ext}_A^{s,t}(M, \mathbb{F}_p)$. So constructing the resolution directly gives the $E_2$ page.

The algorithm

The resolution is built inductively. At each homological degree $s$, htpy:

1. Row reduces the matrix representing $d_s$ to compute the kernel (the $s$-cycles).
2. Extends to surjection by adding new generators for $F_{s+1}$ to cover the kernel.
3. Computes the quasi-inverse $q_s$ satisfying $q_s \circ d_s = \mathrm{id}$ on the image, which is used for chain map lifting.

The key computational bottleneck is linear algebra over $\mathbb{F}_p$ — specifically, row reduction of large matrices representing the Steenrod algebra action.

Linear algebra

htpy uses bit-packed vector representations for efficient $\mathbb{F}_p$ arithmetic:

• At $p = 2$: each vector is a sequence of bits packed into 64-bit limbs. Row reduction uses the Method of Four Russians (M4RI), which processes $k$ rows at a time using lookup tables. With NEON SIMD on ARM, this achieves 1–17 $\mu$s for typical resolution matrices (50–2000 rows).

• At odd primes: elements of $\mathbb{F}_p$ are packed into $\lceil \log_2 p \rceil$ bits per entry. Row reduction uses an adapted M4RI with $k$-scaling optimized for each prime. At $p = 3$, performance is 4.1–4.8$\times$ slower than $p = 2$ due to the larger field arithmetic.

Motivic resolutions

For the motivic Steenrod algebra $A_{\mathrm{mot}}$, the resolution carries an additional weight grading. htpy resolves one weight at a time within each $(s, t)$ step, with a fast-path that skips degrees where all modules have dimension zero (saving 70–95% of row reductions at large $t$).

The motivic resolution uses a wavefront scheduler for parallelism: each $(s, t)$ step depends on $(s, t-1)$ and $(s-1, t)$, forming a diagonal wavefront that can be parallelized across weight values. On a 96-core machine, this gives a 3.8$\times$ speedup for the motivic sphere at $s = 15$, $t = 60$.

Products

The product structure on Ext (the Yoneda product) is computed by composing chain maps along the resolution. For the sphere spectrum, the products with standard generators $h_0, h_1, h_2, \ldots$ give the structlines displayed in the viewer.

Concretely, to compute the product $h_i \cdot x$ for $x \in \operatorname{Ext}^{s,t}$, htpy:

1. Represents $h_i$ as a chain map $\tilde{h}i : F\bullet \to F_\bullet[1, 2^i]$.
2. Evaluates $\tilde{h}_i$ on the generator representing $x$.
3. Reads off the result in $\operatorname{Ext}^{s+1, t+2^i}$.

The chain map is constructed once and cached for reuse across all products.

Massey products

For Massey products $\langle \alpha, \beta, \gamma \rangle$ where $\alpha\beta = 0$ and $\beta\gamma = 0$:

1. Lift $\alpha, \beta, \gamma$ to chain-level cocycles.
2. Construct null homotopies $a$ and $b$ satisfying $d(a) = \alpha\beta$ and $d(b) = \beta\gamma$ via the quasi-inverse.
3. The Massey product is represented by $a\gamma + \alpha b$ at the chain level, with indeterminacy from the choices of $a$ and $b$.

htpy computes both 3-fold and 4-fold Massey products, as well as matric Massey products (where $\alpha, \beta, \gamma$ are matrices of Ext elements).

From algebra to the web

The computation pipeline connects to the web viewer as follows:

1. A module definition (JSON) specifies the module $M$ over the Steenrod algebra.
2. The resolution engine (htpy-resolution) computes the minimal resolution and extracts Ext groups, differentials, and products.
3. The result is serialized into htpy’s v2 archive format — a JSON structure containing the spectral sequence data.
4. The web server (htpy-web) serves the data to the browser, where the viewer renders it as an interactive chart.

For archive modules, steps 1–3 are done ahead of time and the pre-computed data is embedded in the binary. For playground modules, the resolution is computed on the fly when you import a module definition.