Calculating the projection of a vector on a set with CUDA

Many times it is necessary to calculate the projection of a vector v on a set of vectors S.
By “projection”, we mean calculating the element of S whose Euclidean distance is the least from v.
This can be done with CUDA Thrust by the following approach:

Assume that the vector v is

[0 1 12 18 20 3 10 8 5 15]

Suppose to arrange the elements of S in a matrix as

[ 1 11 12 17 12 10 18 20 15 20 ]
[ 6 8 18 13 18 20 3 18 19 6 ]
[ 19 8 6 10 8 16 14 11 12 1 ]
[ 12 9 12 17 10 16 1 4 4 16 ]
[ 1 3 12 12 15 6 9 8 19 20 ]
[ 12 3 14 7 9 1 2 3 9 0 ]
[ 10 9 12 14 1 1 17 8 4 3 ]
[ 20 20 2 18 13 14 12 12 3 5 ]
[ 16 12 18 5 4 5 8 2 13 13 ]
[ 2 3 1 19 11 0 11 15 10 9 ]
[ 0 4 4 12 2 12 3 14 5 13 ]
[ 0 3 7 15 8 17 11 15 14 6 ]
[ 17 11 16 3 12 16 20 19 16 16 ]
[ 12 0 3 10 15 6 12 11 17 10 ]
[ 19 6 16 20 1 20 4 9 12 6 ]
[ 19 1 4 16 9 20 12 1 17 5 ]
[ 11 2 19 11 3 10 17 6 9 6 ]
[ 14 20 4 15 7 20 0 1 18 12 ]
[ 20 1 1 17 2 20 6 4 17 8 ]
[ 18 12 20 15 3 19 13 0 10 17 ]

Then a possible approach using CUDA Thrust is the following:

1. Create a sequence of indices [ 0 1 2 3 4 5 6 7 8 9 ] and replicate it a number of times equal to theĀ  number of the rows of the matrix representing S, to have

[ 0 0 0 0 0 0 0 0 0 0 ]
[ 1 1 1 1 1 1 1 1 1 1 ]
[ 2 2 2 2 2 2 2 2 2 2 ]
[ 3 3 3 3 3 3 3 3 3 3 ]
[ 4 4 4 4 4 4 4 4 4 4 ]
[ 5 5 5 5 5 5 5 5 5 5 ]
[ 6 6 6 6 6 6 6 6 6 6 ]
[ 7 7 7 7 7 7 7 7 7 7 ]
[ 8 8 8 8 8 8 8 8 8 8 ]
[ 9 9 9 9 9 9 9 9 9 9 ]
[ 10 10 10 10 10 10 10 10 10 10 ]
[ 11 11 11 11 11 11 11 11 11 11 ]
[ 12 12 12 12 12 12 12 12 12 12 ]
[ 13 13 13 13 13 13 13 13 13 13 ]
[ 14 14 14 14 14 14 14 14 14 14 ]
[ 15 15 15 15 15 15 15 15 15 15 ]
[ 16 16 16 16 16 16 16 16 16 16 ]
[ 17 17 17 17 17 17 17 17 17 17 ]
[ 18 18 18 18 18 18 18 18 18 18 ]
[ 19 19 19 19 19 19 19 19 19 19 ]

2. Replicate the vector v a number of times equal to theĀ  number of the rows of the matrix representing S, to have

[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]
[0 1 12 18 20 3 10 8 5 15]

3. Calculate the squared difference between the replicated vector and the matrix representing the set S by using thrust::transform.

4. Perform a reduction using thrust::reduce_by_key and using the above constructed indices matrix as key.

On our GitHub website a fully worked example is reported.

Leave a Reply

Your email address will not be published. Required fields are marked *