A performance analysis of sparse MTTKRP implementations with regards to permuted tensors

In this thesis, we apply a novel way of analyzing the MTTKRP algorithm. We look at multiple libraries that optimize the MTTKRP for sparse tensors, including several libraries from both the COO and CSF format, as well as a novel linearization format. These libraries are benchmarked on their performance of different transpositions of the same tensor. We use this to show an approach's consistency in execution time, showing that some algorithms' MTTKRP vary as much as 17x on the same tensor, for different transpositions. We then analyze the relative execution time between modes and permutations, trying to analytically predict the optimal dimension ordering of a tensor for each algorithm. This analysis can be useful to speed up existing implementations or to select the appropriate implementation based on a specific tensor structure. We therefore advocate that this type of analysis should be made with future publications of novel MTTKRP algorithms