High performance rearrangement and multiplication routines for sparse tensor arithmetic

DOI10.1137/17M1115873zbMATH Open1391.65120arXiv1802.02619MaRDI QIDQ4610135FDOQ4610135

Authors:

Publication date: 5 April 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: 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 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 example of high-order differential operators to illustrate this need. As sparse tensor arithmetic is an emerging research topic, with challenges distinct from the MV paradigm, many aspects require further articulation. We focus on three core facets. First, aligning with prominent voices in the field, we emphasise the importance of data structures able to accommodate the operational complexity of tensor arithmetic. However, we describe a linearised coordinate (LCO) data structure that provides faster and more memory-efficient sorting performance. 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 poly-algorithm for sparse tensor products, where hyper-sparsity is a possibility. Different manifestations of hyper-sparsity demand their own approach, which our poly-algorithm 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 speed-ups of 40% or higher compared to alternative high-performance implementations. Comparisons against the MATLAB Tensor Toolbox show over 10 times speed improvements. Thus, these advancements produce significant practical improvements for sparse tensor arithmetic.

Full work available at URL: https://arxiv.org/abs/1802.02619

Recommendations

• Design of a high-performance GEMM-like tensor-tensor multiplication
• Efficient MATLAB Computations with Sparse and Factored Tensors
• Exploiting symmetry in tensors for high performance: multiplication with symmetric tensors
• High-Performance Tensor Contraction without Transposition
• Recompression of Hadamard Products of Tensors in Tucker Format

zbMATH Keywords

sparse tensor productsMATLAB classessparse multidimensional arraysC++ classessparse sorting and permutation

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Multilinear algebra, tensor calculus (15A69) Data structures (68P05) Searching and sorting (68P10) Numerical algorithms for computer arithmetic, etc. (65Y04)

Cites Work

• Efficient MATLAB Computations with Sparse and Factored Tensors
• Title not available (Why is that?)
• Direct Methods for Sparse Linear Systems
• Tensor Decompositions and Applications
• The Influence of Caches on the Performance of Sorting
• Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
• Algorithm 862
• Algorithms for Numerical Analysis in High Dimensions
• Numerical Polynomial Algebra
• Title not available (Why is that?)
• Symmetric Tensors and Symmetric Tensor Rank
• Solution of Linear Systems and Matrix Inversion in the TT-Format
• Sparsity in higher order methods for unconstrained optimization
• Exploiting symmetry in tensors for high performance: multiplication with symmetric tensors
• Einstein summation for multidimensional arrays.
• Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
• Multilinear algebra for analyzing data with multiple linkages
• Implementing sparse matrices for graph algorithms
• Parallel sparse supports for array intrinsic functions of Fortran 90
• New ideas in sparse matrix matrix multiplication
• Efficient representation scheme for multidimensional array operations

Cited In (5)

• Parallel Algorithms for Tensor Train Arithmetic
• High-Performance Tensor Contraction without Transposition
• Parallel Algorithms for Low Rank Tensor Arithmetic
• xPerm: fast index canonicalization for tensor computer algebra
• Efficient vector and parallel manipulation of tensor products

Uses Software

• Matlab
• Boost C++ Libraries
• TensorToolbox
• EinSum
• Algorithm 862
• POOMA
• Boost
• CSparse
• CombBLAS
• GigaTensor

This page was built for publication: High performance rearrangement and multiplication routines for sparse tensor arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4610135)