PaperlayerView exact revision on arXiv

Source-linked AI summary

Quasilinear multiplication in the real Cayley--Dickson tower

Harrison Lemley

arXiv:2609.11588v1math.RAcs.NAcs.SCmath.NA

TL;DR

Direct evaluation of Cayley–Dickson multiplication has quadratic arithmetic complexity. The paper reorganizes the recursive product around the alternating product on imaginary elements, using two half-size evaluations and linear-time recombination. In the reported benchmarks, the quasilinear implementation had the lowest mean time of the three methods at every tested N≥32 for single and batched products.

  • Problem

    Direct recursive evaluation of Cayley–Dickson multiplication has quadratic arithmetic complexity in N.

    Source: §1 · p. 1

  • Method

    The algorithm reduces multiplication to the alternating product on imaginary elements, then uses two half-size evaluations and linear-time recombination over one fixed coefficient extension.

    Source: §1 · p. 2, §2 · p. 5

  • Results

    At every tested N≥32, quasilinear multiplication had the lowest mean time of the three methods for both single and batched products.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The construction admits a matrix-free sequential implementation using O(N) auxiliary storage.

    Source: §1 · p. 3

    The benchmark results describe optimized matrix-free implementations on the tested platform and do not show that Cariow–Cariowa is generally slower.

    Source: §5.2 · p. 17

Abstract

from arXiv · show

Direct evaluation of the defining product in the real Cayley--Dickson algebra $A_n$, of dimension $N=2^n$, has quadratic arithmetic complexity. This paper gives a uniform algorithm for multiplication using $O(N\log N)$ real arithmetic operations and $O(N)$ auxiliary storage. The algorithm reduces multiplication to the alternating product on the imaginary subspace, then evaluates that product by a two-call recursion over one fixed quadratic coefficient extension. For $n\ge1$, the resulting bilinear algorithm uses at most $(9n-15)2^{n-1}+10$ input-dependent real multiplications, and for $n\ge3$, the specified arithmetic schedule uses $(34n-83)2^{n-1}+50$ real operations in total. Under this counting convention, the quasilinear schedule uses fewer operations than direct multiplication for $N\ge16$ and than the uniform Cariow--Cariowa method for $N\ge32$. The algorithm is implemented in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface, and its results are checked against an independent implementation of the defining recursion. 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\ge32$, for both single and batched products, and was roughly $16$ times faster than direct multiplication at $N=1024$.

1. Introduction

Direct Cayley–Dickson multiplication has quadratic arithmetic complexity, and this paper reorganizes the classical recursive structure into a uniform quasilinear algorithm. Its implementation had the lowest mean time of the three methods at every tested N≥32, for both single and batched products.

1. Introduction

  • Direct recursive evaluation requires N^2 real multiplications, while the uniform Cariow–Cariowa method retains quadratic arithmetic complexity.The paper presents its uniform quasilinear upper bound as previously unpublished to the author’s knowledge.Source: §1 · pp. 1–2
  • The recursive algebraic structure is classical and is not claimed as this paper’s contribution, up to coordinate changes and normalizations [BH95, Lemma 3.17, Lemma 4.4, and Theorem 4.6].The cited isomorphisms relate the Brown–Hopkins iteration to the Cayley–Dickson process after scalar extension to C.Source: §1 · p. 2
  • The algorithm uses two half-size evaluations and linear-time recombination over one fixed coefficient extension to obtain uniform quasilinear multiplication.It reduces the real-input root call to one complex evaluation and recovers full multiplication by scalar arithmetic and inner products.Source: §1 · p. 2
  • The construction admits a matrix-free sequential implementation using O(N) auxiliary storage.The theorem’s bilinear bound is stated for n≥1, but its value is not included in the supplied passage.Source: §1 · p. 3
  • At every tested N≥32, quasilinear multiplication had the lowest mean time of the three methods for both single and batched products.Direct and Cariow–Cariowa multiplication were faster at some lower dimensions.Source: §1 · p. 3

2. Scalar and imaginary parts of Cayley–Dickson multiplication

The section separates Cayley–Dickson multiplication into scalar and imaginary parts so that only the alternating product requires recursive evaluation. The remaining terms use O(N) real arithmetic operations.

2. Scalar and imaginary parts of Cayley–Dickson multiplication

  • The standard basis identifies A_n with R^(2^n), and real scalars act as central multiples of the unit.The same basis gives the Euclidean inner product and norm.Source: §2 · p. 3
  • The product ×n is bilinear and alternating, so u ×n u = 0.Source: §2 · pp. 4–5
  • Only the alternating product ×n requires a recursive Cayley–Dickson calculation; the remaining terms require O(N) real arithmetic operations.This reduction follows from the scalar–imaginary decomposition of full multiplication.Source: §2 · p. 5

3. A two-call recursion

The section expresses the alternating product through two recursive evaluations over a fixed quadratic coefficient extension. A real-input specialization and a recursive algorithm then recover full Cayley–Dickson multiplication.

3. A two-call recursion

  • For X = (u, γ + s), with u, s ∈ V and γ ∈ R, and Y = (v, δ + t), the displayed quantities are D := u ×n−1 v − s ×n−1 t and H := u ×n−1 t + s ×n−1 v.Source: §3 · p. 5
  • The trace-zero commutator recursion is attributed to Brown–Hopkins; this paper contributes the uniform quasilinear arithmetic schedule built from that structure [BH95, Lemmas 3.17 and 4.4, and Theorem 4.6].Source: §3 · p. 6

3.1. A fixed quadratic coefficient extension.

  • The recursion uses the fixed coefficient field C = R(ι), extends ×n complex-bilinearly, and can implement complex scalar multiplication with three real products.Source: §3.1 · pp. 6–7

3.2. The two-call formula and the specialization to real coefficients.

  • Each complex recursive evaluation uses two evaluations at the next lower level, while the one-call reduction applies at real-input roots but not general complex nodes.Source: §3.2 · pp. 7–8

3.3. The recursive algorithm.

  • Algorithm 3.5 splits scalar and imaginary parts using the Cayley–Dickson involution, computes the kernel recursively, and correctly reconstructs full multiplication for every n.Source: §3.3 · p. 9

4. Arithmetic complexity and tensor rank

The section establishes O(N log N) real arithmetic cost, O(N) auxiliary storage, and an O(N log N) real bilinear-complexity bound for the algorithm. It also compares the specified schedule’s operation counts with direct multiplication and the uniform Cariow–Cariowa method.

4.1. Arithmetic complexity.

  • O(N log N) real arithmetic operations suffice to multiply elements of A_n for n≥1.The stated arithmetic model counts real additions, subtractions, and multiplications at unit cost.Source: §4.1 · pp. 9–10

4.2. Bilinear complexity.

  • At most (9n − 15)2^(n−1) + 10 real bilinear multiplications suffice for n≥1, giving O(N log N) tensor rank.The schedule yields a real bilinear decomposition; its count excludes fixed-constant multiplications.Source: §4.2 · pp. 11–12

4.3. Auxiliary storage.

  • Algorithm 3.5 uses O(N) auxiliary real coefficients in a matrix-free sequential evaluation.Depth-first evaluation of the two half-size calls keeps temporary storage linear; no multiplication table or dense matrix is constructed.Source: §4.3 · p. 12

4.4. Comparison of arithmetic counts.

  • The schedule uses fewer input-dependent multiplications than direct multiplication from N = 8 and fewer total operations from N = 16; both counts are smaller than uniform Cariow–Cariowa from N = 32.Direct multiplication uses N^2 real multiplications.Source: §4.4 · pp. 12, 14

5. Implementation and benchmarks

The section describes fastCD’s implementations and benchmark protocol, then compares their measured performance and dimension-specific AUTO choices. Quasilinear multiplication is fastest at every tested dimension N ≥ 32, but the reported rankings are specific to these implementations and this platform.

5.1. Implementation and benchmark protocol.

  • fastCD provides C11 routines and a NumPy-backed Python interface, with implementations of the quasilinear algorithm, defining recursion, and uniform Cariow–Cariowa method.All three methods support single and batched products, and users can specify a method or use AUTO.Source: §5 · p. 14, §5.1 · p. 15

5. Implementation and benchmarks

  • Table 1 reports input-dependent multiplications (M), additions and subtractions (A), and total operations (T), including fixed-scalar multiplications.The table gives arithmetic counts for the specified schedules; its caption does not provide their numerical values.Source: Table 1 · p. 15

5.1. Implementation and benchmark protocol.

  • Benchmarks used 10,000 random input pairs at N = 2 through 1024, measured single and batched products, and checked outputs against an independent defining-recursion implementation.Measurements ran on one Intel Xeon Gold 6148 core; timing excluded input generation, numerical verification, and Python object overhead.Source: §5.1 · pp. 15–16

5.2. Performance and automatic algorithm selection.

  • At every tested N ≥ 32, quasilinear multiplication has the lowest mean time for single and batched products; at N = 1024, it is approximately 16 times faster than direct multiplication.Table 2 reports mean nanoseconds per product averaged across 24 subprocess blocks.Source: §5.2 · p. 16, Table 2 · p. 16
  • Operation counts do not alone determine running time on this platform, and these implementation results should not be read as showing Cariow–Cariowa is generally slower.At N = 1024, direct multiplication uses about 1.9 times the operations of Cariow–Cariowa, yet the Cariow–Cariowa implementation is about 1.5 times slower.Source: §5.2 · p. 17
  • AUTO selects algorithms by dimension and product mode: quasilinear for most cases, with direct or Cariow–Cariowa selected at specified smaller dimensions.For single products, direct is selected at N = 4, 8, and 16; for batches, direct at N = 8 and Cariow–Cariowa at N = 16.Source: §5.2 · p. 17

6. Outlook and future work

The outlook presents the two-call alternating-product recursion as a uniform quasilinear method with an explicit bilinear upper bound and linear workspace. It identifies open algorithmic questions and practical evaluations still needed.

6. Outlook and future work

  • The method gives a uniform O(N log N) bilinear upper bound and a linear-workspace implementation throughout the standard real Cayley–Dickson tower.The paper presents no optimality claim or matching lower bound.Source: §6 · p. 17
  • Whether the logarithmic overhead can be reduced and how to combine the recursion with specialized low-dimensional base cases remain open questions.Source: §6 · p. 17
  • Forward-error analysis, cache-aware scheduling, accelerator implementations, broader benchmarks, and application integration are identified as future practical work.These could clarify numerical behavior, change observed crossover points, broaden performance evidence, and test whether isolated multiplication gains translate to end-to-end improvements.Source: §6 · p. 17

7. Statements and disclosures

The statements describe the TANUKI-CD research program, disclose generative-AI assistance in developing the paper, and assign responsibility for its contents to the author.

7.1. The TANUKI-CD program.

  • TANUKI-CD is the author-created research program through which this work is presented, with its objectives, methodology, code, research directions, and papers collected on its website.Source: §7.1 · pp. 17–18

7.2. Use of generative AI.

  • The author reports using GPT-5.6 Sol, GPT-6 Astra, and Claude Fable 5 and 5.1 for literature review, drafting, proof development, and computational testing.The models also assisted with identifying open problems, analyzing papers, and suggesting lemmas and proof arguments.Source: §7.2 · p. 18

7.3. Statement of responsibility.

  • The author states that all results were independently verified and accepts responsibility for the paper’s mathematical claims, arguments, citations, and computations.Source: §7.3 · p. 18
Loading 2609.11588v1…