Quasilinear multiplication in the Cayley-Dickson tower

arXiv:2609.11588 · math.RA, cs.NA, cs.SC, math.NA · Submitted 2026-09-10 · Read on arXiv

math.RA, cs.NA, cs.SC, math.NA

Submitted: 2026-09-10

Updated: 2026-11-19

Comments: 28 pages, 2 tables. v2: title changed from 'Quasilinear multiplication in the real Cayley--Dickson tower'; results generalized from $\mathbb R$ to unital commutative rings with $2$ invertible, with finite-field and tensor-rank corollaries; benchmarks updated. Code: https://git.tanuki-cd.com/algebraity/fastCD

Project page: https://www.tanuki-cd.com

License: http://creativecommons.org/licenses/by/4.0/

The gist: Direct evaluation of the defining product of the Cayley-Dickson algebra A n of rank N:=2 n over a unital commutative ring R in which 2 is invertible requires a quadratic number of arithmetic…

Terminology

Abstract

Direct evaluation of the defining product of the Cayley-Dickson algebra A n of rank N:=2 n over a unital commutative ring R in which 2 is invertible requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra costing O(N N) arithmetic operations in R and O(N) auxiliary storage when the doubling parameters of A n are units whose square roots lie in a fixed commutative coefficient algebra S finitely generated as an R-module and admitting an R-linear map π S to R with π(1) = 1. In particular, over R and every finite field F q of odd characteristic, a quadratic field extension contains a square root of every possible doubling parameter, so the algorithm applies to every Cayley-Dickson tower over these fields, and the tensor rank of multiplication in A n over them is at most (9n-21)2 n+28 when n at least2. When the top doubling parameter is a non-square, as in the standard real tower, the bound is (9n-15)2 n-1+10. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in A n. When R= R with every doubling parameter equal to-1, the real quasilinear schedule uses fewer total arithmetic operations than both direct multiplication and a uniform algorithm of Cariow-Cariowa for n at least4. An implementation for the standard real tower is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method, the quasilinear implementation had the lowest mean time of the three at every tested dimension N at least32, for both single and batched products, and was over 17 times faster than direct multiplication at N=1024.

Sources

Related papers