Abstract. Symmetric tensor operations arise in a wide variety of computations. However, the benefits of exploiting symmetry in order to reduce storage and computation is in conflict with a desire to simplify memory access patterns. In this paper, we propose Blocked Compact Symmetric Storage wherein we consider the tensor by blocks and store only the unique blocks of a symmetric tensor. We propose an algorithm-by-blocks, already shown of benefit for matrix computations, that exploits this storage format. A detailed analysis shows that, relative to storing and computing with tensors without taking advantage of symmetry, storage requirements are reduced by a factor O(m!) and computational requirements by a factor O(m), where m is the order of the tensor. An implementation demonstrates that the complexity introduced by storing and computing with tensors by blocks is manageable and preliminary results demonstrate that computational time is indeed reduced. The paper concludes with a discussion of how the insights point to opportunities for generalizing recent advances for the domain of linear algebra libraries to the field of multi-linear computation. 1. Introduction. A tensor is a multi-dimensional or m-array. Tensor computations are increasingly prevalent in a wide variety of applications [15] . Alas, libraries for dense multi-linear algebra (tensor computations) are in their infancy. The aim of this paper is to explore how ideas from matrix computations can be extended to the domain of tensors. Libraries for dense linear algebra (matrix computations) have long been part of the standard arsenal for computational science, including the Basic Linear Algebra Subprograms interface [16, 10, 9, 12, 11] For tensor computations, no high-performance general-purpose libraries exist. The MATLAB Tensor Toolbox [4, 3] defines many of the kernels (i.e., the interface) that would be needed by a library for multilinear algebra, but does not have any high-performance kernels nor special computations or data structure for symmetric tensors. The Tensor Contraction Engine (TCE) project [6] focuses on sequences of tensor contractions and uses compiler techniques to reduce workspace and operation counts. The very recent Cyclops Tensor Framework (CTF) [23] focuses on exploiting symmetry in storage for distributed memory parallel computation with tensors, but does not investigate the sequential libraries that will invariably be needed on the individual nodes. In a talk at the Eighteenth Householder Symposium meeting in Tahoe City, CA (2011), Prof. Charlie Van Loan stated "In my opinion, blocking will eventually have the same impact in tensor computations as it does in matrix computations." This paper provides early evidence in support of this statement. The approach we take in this
Schatz et al. proved that exploiting symmetry in tensor contraction expressions can improve storage and computational requirements and present CPU implementations REF .
Exploiting Symmetry in Tensors for High Performance: Multiplication with Symmetric Tensors
SIAM Journal on Scientific Computing, Vol. 36, No. 5, pp. C453-C479, September 2014
Mathematics Computer Science