How Stable Are Basis-Free Clifford Algebra Formulas in Floating Point?

Geometric (Clifford) algebra is an algebra in which vectors, planes, volumes and rotations are all elements, called multivectors, that multiply with one another. A recent body of work shows how to compute determinants, characteristic polynomials, inverses, rank and even singular value decompositions of multivectors "natively," using only multivector products and sign-flipping operations, without first converting the multivector into its equivalent matrix. All of these results are exact and symbolic. Nobody has asked what happens when they run in ordinary 64-bit arithmetic.

That question matters because the main engine behind the native formulas has a poor record. The engine is a multivector version of the Faddeev–LeVerrier recurrence, which builds the characteristic polynomial from traces of powers. In computer vision, practitioners who tried the matrix version of that recurrence on polynomial solvers found it "failed due to numerical precision issues." This proposal measures the floating-point behavior of the native formulas and explains it. It also builds a native algorithm that is stable by construction: a Jacobi-style diagonalization driven by exact rotor exponentials. Three things are tested this way: native determinants, native numerical rank, and eigenvalues of action matrices taken from real vision solvers.

Core Claim

The trace-projection equivalence proved in On computing the determinant, other characteristic polynomial coefficients, and inverse in Clifford algebras of arbitrary dimension has a consequence the symbolic literature has not drawn. The equivalence says that the scalar part of a multivector equals the normalized trace of its matrix image. It follows that the basis-free Faddeev–LeVerrier recurrence performs essentially the same additions and subtractions of power traces as the matrix recurrence. It should therefore inherit the same catastrophic cancellation that Making minimal solvers fast observed. We predict that its errors track those of the matrix recurrence up to the extra rounding introduced by multivector products.

Two native routes should behave differently. The first is the family of determinant formulas that multiply the element by its structural conjugates, for dimensions $n \le 5$. These are multiplicative products rather than differences of large sums, and we expect them to stay near the accuracy of a matrix LU-based determinant.

The second route is a native Jacobi method, which we propose to build. It repeatedly rotates a self-adjoint multivector by one-parameter unitary rotors until it lies in the low-dimensional "diagonal" subspace whose existence On SVD and Polar Decomposition in Real and Complexified Clifford Algebras proved. We expect it to match LAPACK accuracy within a small constant. It also keeps every factor inside the correct algebraic structure: unitary factors stay exactly unitary up to rounding, and self-adjoint elements stay self-adjoint.

The rank definition in On Rank of Multivectors in Geometric Algebras reads rank off the highest nonzero characteristic coefficient of $M^\dagger M$, where $M^\dagger$ is the native Hermitian conjugate. Numerically this carries a concrete penalty. Forming $M^\dagger M$ squares the singular values, so with unit roundoff $u \approx 10^{-16}$, any singular value below roughly

$$\sigma \lesssim \sqrt{u}\,\sigma_{\max} \approx 10^{-8}\,\sigma_{\max}$$

is indistinguishable from zero. Here $\sigma_{\max}$ is the largest singular value. The bound comes from rounding error of size $u\,\sigma_{\max}^2$ in the entries of $M^\dagger M$. Coefficient-based rank also accumulates further cancellation on top of this floor. Native Jacobi applied directly to $M$ avoids the squaring.

Research Program

The work has three parts.

Floating-point error analysis. We model rounding in the multivector geometric product. We then derive forward error bounds for three methods: the basis-free Faddeev–LeVerrier recurrence, its closed forms in terms of Bell polynomials (explicit combinatorial expansions of the recurrence), and the conjugate-product determinant built from the special conjugations $\Delta_j$ of On computing the determinant, other characteristic polynomial coefficients, and inverse in Clifford algebras of arbitrary dimension. The goal is to show formally that the recurrence's error is governed by the same ratio of power sums to coefficients as in the matrix case, and to identify when the conjugate products avoid it.

Native Jacobi algorithm. For a basis blade $B$ whose square is $\pm 1$, the rotor $e^{\theta B}$ is exactly $\cos\theta + B\sin\theta$ or $\cosh\theta + B\sinh\theta$. Each step therefore costs a few multivector products and one angle computation. We define an "off-diagonal" norm: the size of the component lying outside the diagonal subspace $K$ from the native SVD theorem. Each Jacobi step picks a generator and angle to annihilate one off-diagonal pair. We will prove or disprove convergence of cyclic sweeps. The indefinite-signature cases, where some rotors are hyperbolic, are the genuinely open part.

We then build native polar decomposition and SVD on top of the Jacobi method. This is the constructive algorithm that On SVD and Polar Decomposition in Real and Complexified Clifford Algebras lists as open. It also gives a thresholded native numerical rank that replaces the exact test of Theorem 4 in On Rank of Multivectors in Geometric Algebras.

Transfer to vision solvers. A real matrix of size $2^k \times 2^k$ is a multivector in $\mathcal{C}\ell(k,k)$. So action matrices from Gröbner-basis minimal solvers, padded with a zero block (which only multiplies the characteristic polynomial by a power of $\lambda$), can be fed to every native method. This part is a test harness, not a proposed faster solver. It asks whether native multivector arithmetic reproduces Bujnak et al.'s failure, and whether a native method avoids it, on the exact matrices where the failure was reported.

The existing work sits in two separate camps. The symbolic results of Basis-Free Formulas for Characteristic Polynomial Coefficients in Geometric Algebras and Noncommutative Vieta theorem in Clifford geometric algebras were verified only with exact integer multivectors. The vision literature diagnosed the instability of the Faddeev–LeVerrier recurrence only for matrices. This project puts the two in one numerical experiment.

Baselines

Naive reference: basis-free Faddeev–LeVerrier in plain double precision. This is the recurrence of On computing the determinant, other characteristic polynomial coefficients, and inverse in Clifford algebras of arbitrary dimension run exactly as written. It is the "do nothing" option a user of these formulas would adopt today. Beating it is necessary but not impressive. The informative outcome is whether its errors coincide with matrix Faddeev–LeVerrier applied to the matrix image of the same multivector, which we run alongside it.

Strongest competitor for the characteristic polynomial: the Danilevsky algorithm. Danilevsky reduces a matrix to companion form by similarity transforms, and roots are then isolated by Sturm sequences, as in Making minimal solvers fast. It is the method the vision community validated as robust exactly where Faddeev–LeVerrier broke. The reported numbers are about 21–22 µs versus 176.3 µs for a standard Gröbner-basis solver on the 6-point focal-length problem, and 46.2 µs versus 127.4 µs on P4P+f (absolute pose with unknown focal length). These are runtimes only. There is no reported accuracy figure on Lacuna for the Faddeev–LeVerrier failure, so we will produce both error distributions ourselves.

Strongest competitor for inverses, rank and SVD: LAPACK on the matrix representation. This means converting the multivector to its matrix image and using LU for determinants and inverses, symmetric eigensolvers for self-adjoint elements, and SVD for rank. It has decades of backward-error analysis behind it.

All methods run on identical multivectors in double precision, on the same CPU, with no per-method tuning except the rank threshold. That threshold is set by the same rule for every method: a relative tolerance chosen on a held-out calibration set. Ground truth is computed in 100-digit arithmetic with mpmath.

"Beating" the naive reference means orders-of-magnitude lower error at high condition number. "Matching" LAPACK means median relative error within a factor of 10 across condition numbers from $10^0$ to $10^{12}$, while keeping unitarity defects $\|W^\dagger W - 1\|$ comparable.

Ablation isolating the key ingredient. The same Jacobi sweep is run with Taylor-approximated rotors instead of the exact closed-form exponentials. A second variant runs on $M^\dagger M$ rather than $M$. These separate the contribution of exact rotors from the contribution of avoiding the squaring.

Why not just…?

Why not just convert to a matrix and call LAPACK? This is a real threat, and at $n \le 6$, where the matrices are at most $8 \times 8$ complex, LAPACK will likely be as accurate and at least as fast. We do not claim otherwise. The proposal's value there is twofold. First, it is a stability verdict on formulas already published and in use. Second, it provides a native algorithm whose outputs are structurally exact in any signature without case-by-case matrix types, a property Basis-Free Formulas for Characteristic Polynomial Coefficients in Geometric Algebras emphasizes. If native Jacobi is worse than LAPACK by more than a constant factor, we will report that the native route should be used only symbolically.

Why not just run Faddeev–LeVerrier in extended precision or with compensated summation? This is cheap, and it may rescue moderate cases. We include double-double and compensated variants as baselines. Our prediction is that extra precision only delays the failure. The cancellation grows with the spread of eigenvalue magnitudes, so any fixed precision fails at some condition number. The error-versus-condition curves will show whether the failure threshold simply shifts by the added digits.

Why not just use Danilevsky on the matrix image for everything? For characteristic polynomials of action matrices, Danilevsky is the target to match, not to dethrone. It does not give inverses, polar factors or rank directly, however, and its own stability depends on pivoting. Experiment three compares the two head to head on the matrices where it was validated.

Proposed Experiments

Experiment 1: stability atlas. We generate multivectors for $n = 2$ to $8$ across all signatures $(p,q)$ with prescribed condition number. Each is built by pulling back $U\Sigma V^\dagger$ with random unitary factors and log-spaced singular values. We then measure three things:

  • relative error of the determinant and of all characteristic coefficients;
  • the inverse residual $\|UU^{-1} - 1\|$;
  • the unitarity defect of the computed polar factors.

The methods compared are every native method and every baseline. The decisive check is whether basis-free and matrix Faddeev–LeVerrier errors coincide within the rounding introduced by multivector products, as the trace-projection argument predicts. A second check is whether conjugate-product determinants stay flat where the recurrence blows up.

Experiment 2: numerical rank. We take multivectors of known rank, add a single gap between singular values placed from $10^{-2}$ to $10^{-14}$ relative to the largest, and add noise below the gap. We compare three rank estimators: coefficient-based rank from Theorem 4, native Jacobi SVD, and LAPACK SVD. The $\sqrt{u}$ floor predicts that the coefficient method misreports rank for gaps below about $10^{-8}$ while the SVD-based methods continue. If the coefficient method fails well above $10^{-8}$, cancellation dominates the squaring penalty.

We also run all three on the ill-conditioned moment and Hankel matrices whose monomial-basis conditioning The Moment-SOS hierarchy: Applications and related topics documents. These are embedded in $\mathcal{C}\ell(k,k)$.

Experiment 3: action matrices from vision solvers. We follow the synthetic-cube protocol of Making minimal solvers fast: 10,000 instances of random 3D points in a cube, randomized poses and focal lengths, and Gaussian noise. We build Gröbner action matrices for the 6-point focal-length and P4P+f problems. On each, we run five methods: matrix Faddeev–LeVerrier, basis-free Faddeev–LeVerrier, Danilevsky with Sturm sequences, LAPACK eig, and native Jacobi. Where the action matrix is non-symmetric, native Jacobi runs on a symmetrized companion that we will specify. We report:

  • the distribution of $\log_{10}$ relative error of the recovered focal length and pose;
  • the fraction of instances failing a $10^{-6}$ error threshold;
  • runtime.

Decisive outcomes. The project succeeds if two things hold. First, native Faddeev–LeVerrier reproduces Bujnak et al.'s failure quantitatively. Second, native Jacobi stays within a factor of 10 of LAPACK and Danilevsky error across the whole condition range, including indefinite signatures.

The project's central algorithmic claim fails if either of two things happens. Cyclic sweeps with hyperbolic rotors might diverge in indefinite signatures. Or native Jacobi errors might grow faster with condition number than LAPACK errors. In either case, the stability atlas and the error analysis would remain the main contribution.