# CUDA and OpenMp Implementation of Boolean Matrix Product with Applications in Visual SLAM
###### Abstract  
In this paper, the concept of ultrametric structure is intertwined with the SLAM procedure. A set of pre-existing transformations has been used to create a new simultaneous localization and mapping (SLAM) algorithm. We have developed two new parallel algorithms that implement the time-consuming Boolean transformations of the space dissimilarity matrix. The resulting matrix is an important input to the vector quantization (VQ) step in SLAM processes. These algorithms, written in Compute Unified Device Architecture (CUDA) and Open Multi-Processing (OpenMP) pseudo-codes, make the Boolean transformation computationally feasible on a real-world-size dataset. We expect our newly introduced SLAM algorithm, ultrametric Fast Appearance Based Mapping (FABMAP), to outperform regular FABMAP2 since ultrametric spaces are more clusterable than regular Euclidean spaces. Another scope of the presented research is the development of a novel measure of ultrametricity, along with creation of Ultrametric-PAM clustering algorithm. Since current measures have computational time complexity order, \(O(n^{3})\) a new measure with lower time complexity, \(O(n^{2})\), has a potential significance.  
ul  
Footnote †: journal:  
0000-0001-9999-22000  
0000-0001-9999-22000-00001-9999-22000-0001-9999-22000  
In order to create clusters, we apply the PAM algorithm [8] which searches a data set for k representative objects (K Medoids) and assigns each object to the closest Medoid. The overall goal is to minimize the sum of dissimilarities between cluster objects and the cluster's center (Medoid) [9]. One of the advantages of PAM clustering algorithm is that it is less sensitive to outliers than the other partitioning algorithms [10]. In this work, we present a new Ultrametric-PAM and incorporate it into the LCD pat of the Fast Appearance Based Mapping (FABMAP) SLAM procedure. The regular FABMAP [11], is available online at [12]. It significantly improves accuracy and speeds up computations by a factor of 1000.  
Furthermore, we introduce a new measure of ultrametricity and demonstrate that the new measure significantly reduces the time complexity from order \(O(n^{3})\) to \(O(n^{2})\) in several different algorithms.  
We parallelize the serial algorithm presented in Section 5, which can be embedded in the VQ part of FABMAP algorithm, to scale up our proposed approach to large data sets. For real-world-size datasets, parallelization of set of transformations is required because applying these transformations serially is nearly intractable. We present two different implementations of this algorithm, with Compute Unified Device Architecture (CUDA) and Open Multiprocessing (OpenMP).  
The following is how the paper is structured. Section 2 is devoted to a review of previous works in this field as well as the motivation for introducing a new measure of ultrametricity. The set of transformations on the Euclidean distance matrices defined in [1] are then briefly reviewed in Section 3. Sections 4 and 5 define the Ultrametric-FABMAP SLAM method, introduce the new measure, and describe the parallel algorithms used to compute the transformations. In Section 6 we present the necessary definitions as well as the notion of ultrametric space, as well as motivating examples. To evaluate the results of the Ultrametric-PAM algorithm, we run simulation experiments on large-scale datasets. Furthermore, we compare the presented measure with [PERSON]'s measure [13].