Repository navigation
Exact Kronecker-power transforms over ℤ/2^k on Apple GPUs, with an application to chromatic number #4581
alford-auld
started this conversation in
Show and tell
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
In the Metal Shading Language, overflow of unsigned integers is defined as wraparound. Arithmetic on$\mathbb{Z}/2^{32}$ and $\mathbb{Z}/2^{64}$ . This post describes a GPU implementation of Kronecker-power transforms that uses this property. It also describes an application where the 2-adic behaviour of the computation determines whether the result is correct.
uintandulongis therefore exact arithmetic inRepository: alford-auld/exact-yates-metal · Report: docs/report.md
Transforms
The kernel applies$M^{\otimes n}$ , for an integer $2 \times 2$ matrix $M$ , to vectors of length $2^n$ . It uses the Yates algorithm: $n$ stages of $2^{n-1}$ butterflies each. Particular choices of $M$ give the following transforms:
[[1, 1], [1, -1]][[1, 0], [1, 1]][[1, 0], [-1, 1]]The stages act on distinct tensor factors and therefore commute. The implementation uses this to group stages across three levels: per-thread registers, SIMD-group shuffles, and threadgroup memory.
Over$\mathbb{Z}/2^k$ , exactness is governed by the Smith normal form of $M$ :
On an Apple M4 (16 GB, MLX 0.32.2), the transform runs at 91–100% of the bandwidth of a device-to-device copy measured at the same working-set size, for$n = 10, \dots, 29$ .
Use of MLX
The kernel is a single templated MSL source compiled through$(M^{\otimes n})^\top = (M^\top)^{\otimes n}$ , each VJP reuses the same kernel with the transposed generator, and no separate backward kernel is needed.
mx.fast.metal_kernel. Matrix entries and tiling parameters are template arguments. Reverse-mode differentiation is registered withmx.custom_function. BecauseSeveral behaviours of MLX 0.32.2 affected the implementation. They are documented under Platform findings in the README.
Application: chromatic number
This uses the inclusion–exclusion method of Björklund, Husfeldt and Koivisto. Let$a$ be the indicator function of independent sets and let $i = \zeta a$ . Define
Then$\chi(G) = \min\lbrace k : c_k > 0 \rbrace$ .
Computed modulo$m$ , a nonzero residue proves that $c_k \neq 0$ . A zero residue proves nothing. The question is therefore when $m$ can divide $c_\chi$ .
To obtain an unconditional result, the implementation computes$c_k$ modulo primes below $2^{31}$ . It then reconstructs $c_k$ by CRT, using the a priori bound
With primes of this size, the unchanged$\mathbb{Z}$ .
uint64transform computes the alternating sum exactly overFor a random graph$G(29, 1/2)$ , the computation needs 6 GiB of subset state, which is the memory limit of the test machine:
The method takes$O^*(2^n)$ time and space for every graph. It is not competitive with branch-and-bound solvers on large sparse instances, and it is limited to about 29 vertices on this hardware.
Caveats
All timings are single runs: the median of a steady-state window, with no estimate of variance. The report states where claims are proved and where they are conjectural.
All reactions