Compact Representation and Efficient Manipulation of Sparse Multidimensional Arrays

Abstract: Efficient manipulation of sparse multidimensional arrays, or tensors, is of interest because their decompositions have applications in many different areas. These areas include neuroscience, machine learning, psychometrics, data mining, numerical analysis, and more. This thesis aims to develop the performance-critical parts of a library for manipulating sparse multidimensional arrays by focusing on sorting them in one or more dimensions—a fundamental operation on which many other operations can be built. High performance is achieved by tailoring algorithms to a compact representation scheme. Evaluation is done on different algorithms and implementation techniques. The result is shown to be 20 to 70 times faster than qsort in the C standard library. The resulting library is open source.