A generalized FFT for Clifford algebras (Q1774318)

The real Clifford algebra \(\mathbb{R}_{p,q}\) can be identified as a simple quotient of the group algebra of a certain supersolvable group \(\mathbb{G}_{p,q}\). A theory of generalized Fourier transforms (GFTs) applies to the latter [e.g. \textit{D. Maslen} and \textit{D. Rockmore}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 183--237 (1997; Zbl 0892.20008)]. The GFT is an isomorphism from the group algebra to a subalgebra of a complex matrix algebra. The dual purposes of this paper are: (i) to identify concretely such a GFT for Clifford algebras and (ii) to produce an algorithm for computing the real matrix representation \(P_{p,q}\) in \(O(d\log d)\) operations, where \(d=p+q\) is the dimension of the Clifford algebra. The fast algorithm relies on a certain \(\mathbb{Z}_2\)-grading of \(\mathbb{R}_{p,q}\) that splits each element into odd and even parts. This splitting commutes with \(P_{p,q}\) and the fast algorithm is then built on iterating this relation. Timing results for a GluCat implementation are reported, comparing this algorithm to naive approaches.