Geometric Audio 3: Gauss Circle Problem for Integer Sized Room Models (part 2)

Recall in the previous post our derivation of the Gauss circle recurrence relation generalized to arbitrary dimensions, scaling, offset, and weights:


where the cost of computing for q: 0 \leq q \leq  K^2 for max-distance K requires O(D K^3) flops. In practice, the summation should be transposed so that q is incremented within the inner loop as to take advantage of vectorization/SIMD memory access patterns.

A second approach for those familiar with DSP utilizes the fact that the summation term in the recurrence relation passes as a form of sparse convolution due to the quadratic-striding memory access patterns of \hat{S}(q-(\Delta_D + \ell_D i), D-1)). To make the convolution operation explicit, we can vectorize w_D^{|i|} into a sparse signal f(m,D) and re-express the summation as follows:


where Z is an indicator variable. Note that in consideration of building f(m,D), a larger boundary scaling term \ell_D increases the signal sparsity. i.e. from a computational perspective, there are regions in the parameter space of (\ell_D, K) where either direct sparse-convolution or the direct evaluation of the recurrence relation  will be faster than an implementation dependent Fast Fourier Transform (FFT) based convolution despite the latter’s lower asymptotic cost of O(D K^2 \log(K)) flops.

With the L_2 distance bound and  Gauss circle problem out of the way, we will continue our investigation of lattice volume bounds in terms of the  L_1 or taxi-cab distance in the next post.

2 thoughts on “Geometric Audio 3: Gauss Circle Problem for Integer Sized Room Models (part 2)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s