Paper Info
Title
High Performance Rearrangement and Multiplication Routines for Sparse Tensor Arithmetic.
Abstract
Researchers from diverse disciplines are increasingly incorporating numeric highorder data, i.e., numeric tensors, within their practice. Just like the matrix-vector (MV) paradigm, the development of multipurpose, but high-performance, sparse data structures and algorithms for arithmetic calculations, e.g., those found in Einstein-like notation, is crucial for the continued adoption of tensors. We use the motivating example of high-order differential operators to illustrate this need. As sparse tensor arithmetic represents an emerging research topic, with challenges distinct from the MV paradigm, many aspects require further articulation and development. This work focuses on three core facets. First, aligning with prominent voices in the field, we emphasize the importance of data structures able to accommodate the operational complexity of tensor arithmetic. However, we describe a linearized coordinate (LCO) data structure that provides faster and more memory-efficient sorting performance in support of this operational complexity. Second, flexible data structures, like the LCO, rely heavily on sorts and permutations. We introduce an innovative permutation algorithm, based on radix sort, that is tailored to rearrange already sorted sparse data, producing significant performance gains. Third, we introduce a novel polyalgorithm for sparse tensor products, where hypersparsity is a possibility. Different manifestations of hypersparsity demand their own customized approach, which our multiplication polyalgorithm is the first to provide. These developments are 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 speedups of 40% or higher compared to alternative high-performance implementations. Comparisons against the MATLAB Tensor Toolbox show over 10 times improvement in speed. Thus, these advancements produce significant practical improvements for sparse tensor arithmetic.
Year
DOI
Venue
2018
10.1137/17M1115873
SIAM JOURNAL ON SCIENTIFIC COMPUTING
Keywords
DocType
Volume
sparse multidimensional arrays,sparse sorting and permutation,sparse tensor products,C plus plus classes,MATLAB classes
Journal
40
Issue
ISSN
Citations 
2
1064-8275
1
PageRank 
References 
Authors
0.35
21
2
Name
Order
Citations
PageRank
Adam P. Harrison110117.06
Dileepan Joseph2498.48