Clifford Givens Rotations: A Backward-Stable Native SVD for Multivectors

Geometric (Clifford) algebra represents rotations, reflections and stretches as single algebraic objects called multivectors. A multivector is a weighted sum of scalars, vectors, oriented planes and higher-dimensional pieces, and these objects multiply through one product. Shirokov recently proved that every multivector has a singular value decomposition (SVD) $M = U\Sigma V^\dagger$ and a polar decomposition written entirely in the algebra's own operations. Nobody can yet compute these factorizations inside the algebra, however. The proofs pass through matrix representations, and Shirokov states outright that the numerical stability of these decompositions "has not yet been evaluated." This note proposes the missing algorithm together with a proof of how it behaves under rounding.

The key observation is simple. Take a basis element $e_A$ of the algebra that squares to $-1$ and multiply by the two-term element $c + s\,e_A$. This multiplication does not scramble all $2^n$ coefficients. It splits them into disjoint pairs and applies an ordinary planar rotation to each pair, so it is a "Clifford Givens rotation." A Jacobi-style SVD built from these rotations therefore inherits the classical rounding-error analysis of Givens and Jacobi methods almost unchanged. It also delivers something the matrix detour does not guarantee: the input perturbation that explains the rounding errors is itself a multivector of the same algebra, and the computed factors sit within a few units of roundoff of the algebra's unitary group.

Core Claim

We will analyse the algorithm with backward error analysis. This approach asks for the smallest change to the input that would make the computed output exact, rather than asking how far the output is from the truth. We claim that a one-sided Jacobi SVD built from Clifford Givens rotations is backward stable in the algebra's native norm, $\|M\| = \sqrt{\mathrm{Sc}(MM^\dagger)}$, where $\mathrm{Sc}$ extracts the scalar part. In this setting "backward stable" means three things. The computed factors reconstruct a nearby multivector. That nearby multivector differs from $M$ by an element of the algebra of relative size $c(n)\,u$, where $u$ is unit roundoff. The computed $\widehat U, \widehat V$ violate $UU^\dagger = 1$ only at the same order.

The mechanism rests on one fact. Let $e_A$ be a basis blade with $e_A^2 = -1$ and let $c^2 + s^2 = 1$. Then

$$R = c + s\,e_A, \qquad RR^\dagger = c^2 - s^2 e_A^2 = 1 ,$$

so $R$ is exactly unitary whenever its two numbers are. Right-multiplying $M$ by $R$ sends each coefficient pair $(m_C, m_{C\oplus A})$ to a signed rotation of itself, where $C\oplus A$ denotes the blade index obtained by multiplying $e_C$ by $e_A$. Standard Givens analysis then gives the following bound. Here $\gamma_k$ is the usual rounding constant, roughly $ku$, and $\Delta M$ is a genuine multivector:

$$\mathrm{fl}(MR) = (M + \Delta M)\,R, \qquad \|\Delta M\| \le \gamma_{c}\,\|M\|, \quad c = O(1).$$

Unitary right-multiplication preserves the native norm, so these per-step perturbations add up across sweeps exactly as in matrix Jacobi.

The result is worth having for three reasons. It gives the first constructive native SVD. It answers Shirokov's stability question with a proof rather than a test. It also runs into a real issue in backward error analysis: a general Clifford product reuses every input coefficient in every output coefficient. That kind of reuse is exactly what Bean: A Language for Backward Error Analysis forbids through strict linearity. Two-term rotations avoid the problem by construction.

Relation to Prior Work

Shirokov's papers supply the mathematics we build on. On Singular Value Decomposition and Polar Decomposition in Geometric Algebras and On SVD and Polar Decomposition in Real and Complexified Clifford Algebras define the conjugation $\dagger$, the unitary group $G\mathcal G_{p,q}$ and the small canonical subspace $K$ that contains $\Sigma$. For example, $K$ is 2-dimensional inside the 16-dimensional space-time algebra $\mathcal G_{1,3}$. Both papers prove existence only, and we make it constructive.

On Rank of Multivectors in Geometric Algebras defines rank through the characteristic polynomial of $M^\dagger M$, computed with the Faddeev–LeVerrier recursion. That paper motivates part of this work. Computing rank from polynomial coefficients is the textbook example of a numerically fragile computation, and we test it directly against rank read off the native singular values.

The structured backward error literature supplies our error measure. Backward errors for eigenproblem of two kinds of structured matrices shows that restricting perturbations to a structure class gives tighter, more meaningful bounds. We use the same idea with a different structure: the perturbation must be a multivector, optionally one confined to the grade subspace or subalgebra that $M$ occupies. Backward error analysis of the Lanczos bidiagonalization with reorthogonalization acts as a constraint on what we can promise. For multi-stage methods, one often obtains only mixed forward–backward stability. That is the fallback statement if the accumulated rotors do not admit a clean backward bound.

Bean is related work that we partly extend. It synthesizes backward error bounds compositionally but supports only scalar and vector primitives with componentwise, unstructured perturbations. Our lemma is a hand-derived instance of the structured, multivector-typed rule that Bean lacks.

The randomized least-squares papers (Fast randomized least‐squares solvers can be just as accurate and stable as classical direct solvers, Randomized Iterative Solver as Iterative Refinement: A Simple Fix Towards Backward Stability) supply the evaluation methodology, not the method. We sweep the condition number up to $10^{16}$ and report backward error, forward error and residual separately, as they do.

Research Program

The algorithm is a one-sided Jacobi iteration. It repeatedly right-multiplies $M$ by Clifford Givens rotations, chosen so that the Hermitian multivector $M^\dagger M$ loses its components outside $K$. $M^\dagger M$ is tracked implicitly and never formed, which avoids squaring the conditioning. A left factor is then read off at the end, as in matrix one-sided Jacobi.

Conjugating a Hermitian multivector by $e^{\theta e_A}$ leaves unchanged the components that commute with $e_A$. It rotates each anticommuting component $Q$ against its partner $e_A Q$. So for a large off-$K$ component $Q$, we choose a generator $e_A$ that anticommutes with $Q$ and maps it into $K$, and we pick the angle in closed form to transfer that weight into $K$.

The main technical risk is convergence. Unlike matrix Jacobi, one rotation can also disturb other anticommuting components. Proving that the off-$K$ norm decreases monotonically, or finding a pivot ordering under which it does, is the first theoretical task. We will attack it using the correspondence between basis blades and signed-permutation operators on the spinor space. The fallback is a hybrid in which Newton–Schulz polar iteration first brings $M$ close to Hermitian form and Jacobi then finishes.

Three analytical results are targeted. The first is the per-rotation structured backward error lemma above, with explicit constants. The second is a sweep-level bound of the form $\|\Delta M\|/\|M\| \le c\,k\,u$ after $k$ rotations, along with an orthogonality defect of order $\|\widehat U\widehat U^\dagger - 1\| = O(ku)$. The third is a computable first-order structured backward error for any candidate factorization, obtained by linearizing onto the tangent space of $G\mathcal G_{p,q}\times K\times G\mathcal G_{p,q}$ and solving a small least-squares problem, in the spirit of the projection formulas of Li et al. This third quantity is the common yardstick used to score every method below, native or not.

Implementation will cover real non-degenerate algebras up to $n=8$ and their complexifications. This range spans all eight Cartan–Bott classes, from real through doubled and complex to quaternionic matrix types. Degenerate signatures such as projective geometric algebra are excluded, because Shirokov's theorems do not cover them.

Baselines

The naive reference point uses the explicit formulas. For $n\le 4$, we compute rank and characteristic data through Shirokov's Faddeev–LeVerrier expressions in double precision, and we obtain singular values as the roots of the characteristic polynomial of $M^\dagger M$. This is the only existing native computational route. Its failure on ill-conditioned inputs is the expected result and an easy win, so beating it proves little by itself.

The strongest competitor is the matrix detour done carefully. We map $M$ to its matrix representation using an orthonormal representation basis, so the map preserves norms up to a constant. We then run LAPACK's backward-stable SVD. Quaternionic classes have no quaternionic LAPACK routine, so there we use the standard complex embedding. We then map the factors back and project them onto the image of the algebra and onto $G\mathcal G_{p,q}$. The projection is a polar re-orthonormalization inside the algebra. This competitor gets the benefit of decades of engineering, and on simple real and complex classes we expect it to tie us. It is run on identical inputs in the same precision. It is scored by the same native structured backward error, orthogonality defect and reconstruction residual, and its runtime is measured on the same hardware, both single-instance and batched.

A second native competitor is the transliterated Newton–Schulz polar iteration, $X\leftarrow \tfrac12 X(3 - X^\dagger X)$, computed with full Clifford products. It is native, simple and fast on GPUs. It needs no pivoting and so directly tests whether the Givens structure matters. Its iteration count is tuned to the same stopping tolerance.

The ablation that isolates our key ingredient replaces the two-term Clifford Givens rotation with the same rotor applied through a generic dense Clifford product. The arithmetic is equal in exact math but loses the disjoint-pair structure. If this change leaves the backward error unaffected, the lemma is not what drives stability.

Beating the strongest baseline means one of two things. The first is an orthogonality defect and structured backward error at least an order of magnitude smaller in the quaternionic and doubled classes, with parity elsewhere. The second, weaker outcome is equal accuracy with factors that need no post-hoc projection. No reported result was found on Lacuna for the accuracy of any multivector SVD, native or via matrices. The closest reported numbers concern a different problem: SIRR reaches backward error of order $O(n^2u)$, matching Householder QR on least squares (Randomized Iterative Solver as Iterative Refinement). So the baseline figures here must be produced by this study.

Why not just…?

Why not just flatten to matrices and call LAPACK? This is the serious threat, and we treat it as the null hypothesis rather than dismissing it. For signature classes whose matrix image is the full real or complex matrix algebra, every matrix perturbation is a multivector perturbation. The detour is then already structured-backward-stable, and we predict a tie there. The open case is the quaternionic and doubled classes. There, singular values of the complex embedding appear in exact pairs, so LAPACK's choice of singular vectors within each pair is arbitrary, and the computed factors generally do not lie in the image of the algebra. The projection experiment decides whether projecting back costs accuracy near clustered singular values. If it does not, we will report that the native method offers structure and signature-independent code but no stability advantage.

Why not just use Newton–Schulz, which is already native? It needs only Clifford products and converges quickly near the group, so it may be the practical winner for polar factors. However, it does not produce $\Sigma$ in $K$ or reveal rank. It also uses dense products whose rounding cannot be attributed to a small multivector perturbation of the input without extra conditioning factors. It runs as a full baseline, and if it matches Jacobi on polar accuracy, the note narrows its claim to the SVD and rank.

Why not settle for forward error, or run the algorithm through Bean? Forward error is bounded by the condition number times the backward error. At condition numbers near $10^{16}$ it says nothing about solver quality, which is the lesson of Fast randomized least‐squares solvers can be just as accurate and stable as classical direct solvers. Bean would treat a multivector as an unstructured array. Its strict linearity also rejects the coefficient reuse inside a Clifford product, so it cannot state the structured bound we need. We will nonetheless run the rotation kernel alone, which is linear in each coefficient pair, through Bean as a sanity check on our constants.

Proposed Experiments

The test suite is synthetic because the file reports no numerical benchmark for native decompositions. It covers signatures $(3,0)$, $(1,3)$, $(4,1)$, $(2,2)$, $(0,3)$, $(0,2)$, $(6,0)$ and $(4,4)$ plus complexifications, which touches every periodicity class. Inputs are built as $U\Sigma V^\dagger$ from random unitary multivectors. Singular spectra are prescribed with condition numbers from 1 to $10^{16}$ and include exactly repeated and clustered values. Additional variants confine $M$ to the even subalgebra or to a single grade.

The metrics are the linearized structured backward error, the orthogonality defect of the computed factors, the relative forward error of $\Sigma$, and grade leakage of the reconstruction outside the subspace containing $M$. Wall-clock time is measured single-instance and batched over $10^5$ small multivectors, which is the regime of multivector networks such as Geometric Algebra Transformer.

Three decisive checks follow. First, Clifford-Givens Jacobi must keep structured backward error within a small multiple of $u$ times the rotation count at every condition number and in every signature class; otherwise the core claim fails. Second, the LAPACK round trip in quaternionic classes either shows an orthogonality defect or post-projection backward error well above $O(u)$ near paired singular values, or it does not. That comparison decides whether native computation buys stability or only convenience. Third, for $n\le4$, we plant multivectors of known rank and add perturbations of size $10u$ to $10^{-8}$. We then compare the misclassification rate of Faddeev–LeVerrier rank with that of $\epsilon$-rank read from native singular values, using LAPACK $\epsilon$-rank as the reference. This test determines whether Shirokov's rank definition needs a numerically sound replacement in practice.