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

John Snyder

MSR-TR-2006-53 |

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,k1), (i,j,k2), …,(i,j,kNij) which share a common pair of indices (i,j) in the triple, and which vary only in the third (completion) index km and its corresponding coefficient dm = Γijkm where m ∈ \1,2,…,Nij$. The collection is done using a greedy method that successively chooses the index pair (i,j) maximizing the number Nij of different km 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.