Quasilinear multiplication in the Cayley-Dickson tower
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
- The Octonions
- Traffic flow prediction using Deep Sedenion Networks
- Numerion: A Multi-Hypercomplex Model for Time Series Forecasting
- A Mnemonic Matrix Rule for (Split) Octonionic Multiplication and its Extension to the Cayley--Dickson Tower
- The twisted group algebra structure of the Cayley-Dickson algebra