Code Generation and Factoring for Fast Evaluation of Low-order Spherical Harmonic Products and Squares

We present a method for fast evaluation of spherical harmonic (SH) products or, more generally, any binary product of vectors yielding a vector, where the product is governed by a fixed, sparse, symmetric, order 3 tensor, denoted Γ_ijk. The method is given the nonzero entries of Γ as input (they can be computed analytically or by numerical integration for the SH basis) and makes use of an offline code generator to perform the necessary array indexing using constants rather than variables. Factoring is performed by collecting the tensor’s nonzero components, represented by index triples (i,j,k), into groups (i,j,k₁), (i,j,k₂), …,(i,j,k_Nij) which share a common pair of indices (i,j) in the triple, and which vary only in the third (completion) index k_m and its corresponding coefficient d_m = Γ_ijkm where m ∈ \1,2,…,N_ij$. The collection is done using a greedy method that successively chooses the index pair (i,j) maximizing the number N_ij of different k_m needed to complete the tensor’s nonzero index triples. The greedy method then continues to the next best initial pair, generates its contribution, and so on, until all nonzero triples have been accounted for. The combination of “greedy pair” factoring and generating constant array indices produces code that is significantly faster than naïve evaluation methods.