# CUDA and OpenMp Implementation of Boolean Matrix Product with Applications in Visual SLAM
## 5 Ultrametric-PAM and Ultrametric-FABMAP  
In this section, we describe a set of serial and parallel algorithms(Algorithms 1-4) to transform an Euclidean distance matrix into a hierarchical distance matrix. The standard Ultrametric-PAM algorithm will be discussed first. It is desired to investigate how compactness, Donn index, and other clustering evaluation criteria change when higher ultrametric configuration dissimilarity matrices are used as input to the PAM clustering algorithm. Algorithm 1 determines how well PAM clustering algorithm identifies clusters in a dataset by evaluating clustering compactness, Donn index, sum of squared errors, and normalized mutual information (NMI), for dissimilarity spaces \((X,A^{1}),(X,A^{2}),\dots,(X,A^{k}(A))\). The NMI, compactness, sum of squared error, and Donn index criteria are measured. One of the algorithm's potential benefits is that it can detect spiral clusters, which most clustering algorithms that are not density-based fail to detect. However, Algorithm 1 can only be used on toy datasets; for real-world-size datasets, this algorithm takes a long time. As a result, it must be parallelized. A possible parallel version can be achieved using OpenMp and Intel intrinsic Advanced Vector Extension (AVX-256) functions. Algorithm 2 is designed to speed up the transformations even further. Another option is to parallelize the slow serial Algorithm 1 using GPU programming. Algorithm 3 presents the proposed solution. ```
1:Input: \(A\in M_{n}\), \(A\in M_{n}\), \(A\in M_{n}\), \(A^{1},A^{2},...,A^{n}\), \(A^{1},A^{2},...,A^{n}\), \(A^{2},...,A^{n}\), \(A^Algorithm 4 generates the cluster centroids and BoW representation of the training and testing data required by the FABMAP algorithm. To train the Chow-Liu tree in the FABMAP algorithm, we use the BoW representation and the clustering centroid of the training data set. In the next section, we present the clustering evaluation metrics used in performance benchmarks. Input: Euclidean distance matrix A

Output: matrix of a dendrogram
```
1:procedureUltrametric-PAM(\(K\gets 1\), \(B\gets A\), \(S\leftarrow\{\}\), \(C=n\times n\))
2:while\(A^{K}\
eq A^{K+1}\)do
3:\(PAM(A^{K},n)/PAM(A^{K},n)\)
4:err(K) = Sum of squared errors
5:Calculate Clusterings Compactness and Donn index
6:for\(i=1\) to \(n\)do
7:for\(j=1\) to \(n\)do
8:for\(t=1\) to \(n\)do
9: Add \(Max(A[i,t],B[t,j]))\) to \(S\)
10:endfor
11:\(C[i,j]\gets Min(S)\)
12: Make S empty
13:endfor
14:endfor
15:\(A\gets C\)
16:\(K\gets K+1\)
17:endwhile
18: Return \(A\)
19:endprocedure
```
**Algorithm 1** (Ultrametric-PAM) Runs PAM with the transformed distance matrices

Input: Euclidean distance matrix A

Output: matrix of a dendrogram
```
1:omp_set_num_threads(80);
2:#pragma omp parallel for
3:for(int = 0; 1 < rows; 1++)
4:for(int p = 0; p < rows; p++)
5:float*a,*b,copyC;
6:__m256*aAVX,*bAVX,*cAVX;
7:posix_memalign((void **)& copyC, 32, Size);
8:posix_memalign((void **) & a, 32, Size);
9:posix_memalign((void **) & b, 32, Size);
10:a = Distance_matrix[]; b = Distance_matrix[][]
11:aAVX = (void*a); bAVX = (void*b); cAVX = (void*) copyC;
12:for(int g=0; g < length; g += 8, aAVX++, bAVX++, cAVX++)
13:*cAVX = -mm256_max_ps(*aAVX,*bAVX);
14:result[][p] = AVX_find_peaks(copyC,Jenth);
```
**Algorithm 2** **AVX-256** Transformation
```
1:\(\_\)global\(\_\)void CUDA-Transformation(float *M, float *N, float *P){
2:int tx = blockIdx.x * blockDim.x + threadIdx.x;
3:int ty = blockIdx.y * blockDim.y + threadIdx.y;
4:Minimum = large number;
5:If (tx < blockDim.x & ty < blockDim.y )
6:for\(k=0\) to WIDTH
7:If (fmax (M[ty* WIDTH +k],N[k* blockDim.x +tx]) \(\leq\) Minimum)
8:Minimum =fmax(M[ty* WIDTH +k],N[k* blockDim.x +tx])
9:P[ty* blockDim.x +tx] = Minimum
```
**Algorithm 4** (Ultrametric-FABMAP).