K-Closest-Circles (K-means variation)

Algorithm in CUDA C that fits points in circles. For the calculation in GPU of the least squares solution, MAGMA library (http://icl.cs.utk.edu/magma/) is used.

---

K-Closest-Circles Algorithm

Input:

1. N = number of points
2. X = the Npoints in the 2D coordinate system
3. K = number of circles to fit

Output:

1. P_i, i ∈ {1..K}: the assignment of points in X to the i-th circle (hence, sum(count(P_i)) = N)
2. C_i, i ∈ {1..K}: the circles, represented as centre coordinates and radii

Algorithm Steps:

1. Create the set C of initial circles (C_i, i ∈ {1..K})
2. While not finished: a. For each point, assign it to the circle that is closest to it - this populates all P_i, i ∈ {1..K} b. For every P_i, fit a circle using least squares method - this creates a better set C

Stopping Criteria:
Stop if either of these conditions are met:

1. No change is assignment of points to circles from the previous iteration
2. Maximum number of iterations is reached

---

Instructions

The following enviroment variables must be set in order to compile:
export PATH=/usr/local/cuda/bin:$PATH
export LD_LIBRARY_PATH=/usr/local/cuda/lib64:$LD_LIBRARY_PATH
export LD_LIBRARY_PATH=/opt/openblas/0.2.15/gcc/lib:$LD_LIBRARY_PATH
export LD_LIBRARY_PATH=/opt/magma/1.7.0/openblas/gcc/lib:$LD_LIBRARY_PATH

make
./hpc