Open Source
Quasilinear multiplication in the Cayley-Dickson tower
arXiv cs.NA0 views
arXiv:2609.11588v4 Announce Type: replace-cross Abstract: Direct evaluation of the defining product of the Cayley-Dickson algebra $A_n$ of rank $N:=2^n$ requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm that computes multiplication in $A_n$ using $O(N\log N)$ arithmetic operations and $O(N)$ auxiliary storage over any unital commutative ring $R$ with $2\in R^\times$, with doubling parameters that are units with square roots in a fixed finite commutative $R$-algebra admitting an $R$-linear surjection onto $R$ preserving the identity. This covers every Cayley-Dickson tower over $\mathbb{R}$ and over finite fields of odd characteristic, where the tensor rank of multiplication in $A_n$ is at most $(36n-69)2^{n-3}+10$ for $n\ge4$. To the author's knowledge, this is the first uniform subquadratic algorithm for multiplication in $A_n$. In single-core benchmarks over $\mathbb{R}$, an open-source implementation in the library fastCD is over $17$ times faster than direct multiplication at $N=1024$.
Source:https://arxiv.org/abs/2609.11588PreviousFast Gauss Sums via Flash AttentionNextOpen Response Explorer: a Structured Collaborative Writing System for Peer-Informed Open-Response Assignments
Related posts
How to Test a Resistor, Diode, LED and Capacitor with a Multimeter (Before You Blame Your Code)
0dev.to Beginners
Omni-modal decomposition autoencoders learn full-stack wearable disentangled representations
0arXiv eess.SP
Spectral Vision Transformer for Efficient Tokenization with Limited Data
0arXiv eess.SP
Gaussian Quasi-Likelihood Estimation for Nonsynchronously Observed L\'evy processes
0arXiv stat.TH
Triple Overlap in Pipelined Krylov Methods on Multi-GPU Systems
0arXiv cs.DC
Rhythm-TTS: High-Fidelity Shortcut Latent Modeling and Probabilistic Rhythm Generation for Zero-Shot Text-to-Speech
0arXiv cs.SD