Integer Lattice in N-Dimensional Sphere: Count of Points With Integer Coordinates Using Parallel Programming (Part I)

How many integer-coordinate points are located within an n-dimensional sphere centered at the origin with an arbitrary floating point radius r? There is no analytic solution, so only an algorithm would do and it would probably have to be parallel (using MPI). Brute force approach is to partition the n-dimensional cube of side 2r amongst p processors and let every processor evaluate every single point of the subcube assigned to it (by evaluate I mean check if the point is within the sphere.) Such algorithm would be scalable but most likely hopelessly slow anyway, even under modest dimensionalities and radii. What if the number of processors is not even? Alternative is to traverse every point in n-dimensional space such that every one of its coordinates is between -r and r and dole it out to a waiting vacant processor for evaluation – while this does involve stochasticity, it is essentially still a brute force approach.

Thus before getting to parallelization with MPI, the question is, what is an efficient sequential algorithm to find the count of integer-coordinate points within n-dimensional sphere centered at the origin? It’s certainly not to go point by point and check if the sum of square of every coordinate is less than the sum of square of radius.

Here is my solution. I’ve searched literature on this problem for some time and wasn’t able to find any code-based description or anything even moderately resembling this solution. Mostly people speak of Gauss’s approach to approximating this number.

From the outset, you build a tableau as below:

N_dimensional_sphere_integer_coordinate_count_illustration_01

This tableau is used to efficiently compute the number of integer-coordinate points inside an n-dimensional sphere centered at the origin

For any given radius r, it makes no sense to evaluate a point whose coordinate is greater than r, so that is why in the tableau above, the maximal number of potential coordinates is from 0 to 6. The dimensionality n is 32 so every row would have to sum up to 32 for columns from 0 to 6, because every dimension has to have some kind of coordinate. Next, the number of dimensions can be broken down (partitioned) into constituent parts, using integer partition algorithm. For example, n = 32 can be broken down as 31+1, 30 + 1 + 1, 30 + 2, etc. These numbers can then be shuffled between the coordinate columns. For example, you can break down 32 to 28 + 1 + 1 + 1 + 1. Thus you say that 28 dimensions will have same coordinate (let’s say 0 as above). Then some other dimension will have a distinct coordinate like 1 or  2 or  3 or 4 (1 for each, that’s why 32 = 28 + 1 + 1 + 1 + 1). But then you can say that 28 dimensions will have a coordinate of 6 while 1 will have a coordinate of 0, one will have coordinate 2, then 3, then 4.

So for every integer partition of your dimension count (32 above) you need to know the number of distinct shufflings available between all potential coordinates (0 to r, which is 6 above.) Using the example above, it’s simple:

32! / (28! 1! 1! 1! 1!)  = 32 * 31 * 30 * 29 = 863,040.

In addition, you need to remember that for every non-zero coordinate in the point, you can have two signs. So you need to sum up the non-zero coordinate counts to get number s and then raise 2 to the power of s. Then you need to multiple the count of combinations by 2^s. But actually, even before you do that, you want to ensure that sum of squares of coordinates doesn’t exceed square of radius. Only then you should calculate the combination count and multiply by 2^s count.

One final thing. Every n-dimensional sphere will have an n-dimensional cube inside it which will be fully contained within such sphere. Thus every point inside that cube will be inside the sphere and we don’t need to verify this fact. It’s pretty simple to compute the side of the cube from the following:

n * m^2 = r^2, where m is the half of cube side.

m = r / sqrt(n);

So the volume of the cube contained inside the sphere is

(2*m + 1) ^ n, where n is the count of dimensions. We add 1 to 2*m because 0 is also counted as a point. We multiple m by 2 because the cube is symmetrical around the axis.

Here is an example. Let’s say dimension count n is 4 and the radius is 5. Then the count of integer points inside is 3121. How did we get there? Attached is the algorithm output in pdf, just so that you can get a sense for computation. The total is 2496. because the volume of the inner cube is not included. The inner cube will have a side of 5/sqrt(4) = 2. So the volume of the inner cube is (2*2+1)^4 = 625. Adding 2496 and 625 gives 3121 which is the correct number of points in n-dimensional sphere of radius 5 and dimension 4.

Below is the c algorithm and output in pdf. The code doesn’t require any additional libraries. Compilation command

gcc followed by -lm for math module.

Over the course of next few posts, I will separately show the integer partition algorithm, permutations without repetitions in lexicographic order, and efficient computation of permutation count all in c. In addition, this algorithm will be followed by its MPI version which will dole out the combinations to individual processors for computation.

n_dimensional_hypersphere_integer_lattice_point_count_in_c

n_dimensional_sphere_lattice_point_count_output

Advertisements

~ by Monsi.Terdex on April 5, 2013.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: