High Performance Rearrangement and Multiplication Routines for Sparse Tensor Arithmetic.

Researchers are increasingly incorporating numeric high-order data, i.e.,numeric tensors, within their practice. Just like the matrix/vector (MV)paradigm, the development of multi-purpose, but high-performance, sparse datastructures and algorithms for arithmetic calculations, e.g., those found inEinstein-like notation, is crucial for the continued adoption of tensors. Weuse the example of high-order differential operators to illustrate this need.As sparse tensor arithmetic is an emerging research topic, with challengesdistinct from the MV paradigm, many aspects require further articulation. Wefocus on three core facets. First, aligning with prominent voices in the field,we emphasise the importance of data structures able to accommodate theoperational complexity of tensor arithmetic. However, we describe a linearisedcoordinate (LCO) data structure that provides faster and more memory-efficientsorting performance. Second, flexible data structures, like the LCO, relyheavily on sorts and permutations. We introduce an innovative permutationalgorithm, based on radix sort, that is tailored to rearrange already-sortedsparse data, producing significant performance gains. Third, we introduce anovel poly-algorithm for sparse tensor products, where hyper-sparsity is apossibility. Different manifestations of hyper-sparsity demand their ownapproach, which our poly-algorithm is the first to provide. These developmentsare incorporated within our LibNT and NTToolbox software libraries. Benchmarks,frequently drawn from the high-order differential operators example,demonstrate the practical impact of our routines, with speed-ups of 40% orhigher compared to alternative high-performance implementations. Comparisonsagainst the MATLAB Tensor Toolbox show over 10 times speed improvements. Thus,these advancements produce significant practical improvements for sparse tensorarithmetic.