Sringeri Vageeswara, Abhijit · OhioLink ETD Center (Ohio Library and Information Network) · 2015
Tensor contractions are frequently encountered computationally expensive operations in the fields of Nuclear Physics, Quantum Chemistry, Fluid dynamics and other areas of computational science.Most often, these operations are executed in a sequence, where the output of one operation is used as input to later operations.Existing parallel solutions are either not communication optimal or do not handle a sequence of contractions optimally.A recently developed RRR framework requires tensors to be distributed in certain specific ways over a certain specific logical views of a processor grid for optimal communication.Redistribution of tensors over changing logical processor grids between successive contractions in a sequence enables it to be executed in a communication efficient manner in the RRR framework.While these redistributions involve no computation and are just communication operations, they can take a significant amount of the runtime of the contraction operation.In this thesis, an efficient way to redistribute tensors onto changing logical views of multi-dimensional processor grids is presented.A cost model to select the best distribution and grid scheme is implemented and is tested on a sequence of CCSD tensor contraction equations and the results are presented.iii A report on some work to optimize the CCSD(T) method of the NWChem software suite is also presented.
Cited by 0Open access
Jean Kossaifi, Zack Chase Lipton, Aran Khanna et al. · 2018
Convolution neural networks typically consist of many convolutional layers followed by several fully-connected layers. While convolutional layers map between high-order activation tensors, the fully-connected layers operate on flattened activation vectors. Despite its success, this approach has notable drawbacks. Flattening discards the multi-dimensional structure of the activations, and the fully-connected layers require a large number of parameters. We present two new techniques to address these problems. First, we introduce tensor contraction layers which can replace the ordinary fully-connected layers in a neural network. Second, we introduce tensor regression layers, which express the output of a neural network as a low-rank multi-linear mapping from a high-order activation tensor to the softmax layer. Both the contraction and regression weights are learned end-to-end by backpropagation. By imposing low rank on both, we use significantly fewer parameters. Experiments on the ImageNet dataset show that applied to the popular VGG and ResNet architectures, our methods significantly reduce the number of parameters in the fully connected layers (about 65% space savings) while negligibly impacting accuracy.
Cited by 14
J.F. Blinn · IEEE Computer Graphics and Applications · 2001
In my last column (see ibid., January/February 2001), I talked about a notational device for matrix algebra called tensor diagrams. This time I write some C++ code to symbolically evaluate these quantities. This gives me a chance to play with some as yet untried features in the C++ standard library, such as strings and standard template library (STL) container classes.
Cited by 1
Gallagher, Kiana · UVic’s Research and Learning Repository (University of Victoria) · 2023
Tensor networks are mathematical objects that can be used to model many-body systems in physics. Without the use of tensors, the computations of these models are exponential. Different operations can be applied on tensors to find information regarding the system. One of these operations is tensor contraction. My research project was to create an algorithm that is able to contract a tensor network into a single tensor. Contracting tensors naively will result in exponential memory requirements which will cause the average computer to run out of memory quickly or it will take a long time to compute. Thus, a contraction algorithm will decide which tensors to contract to minimize the time for contraction and the memory required.
Cited by 0
Jianyu Huang, Devin A. Matthews, Robert A. Geijn · SIAM Journal on Scientific Computing · 2018
Tensor contraction (TC) is an important computational kernel widely used in numerous applications. It is a multidimensional generalization of matrix multiplication (GEMM). While Strassen's algorithm for GEMM is well studied in theory and practice, extending it to accelerate TC has not been previously pursued. Thus, we believe this to be the first paper to demonstrate how one can in practice speed up TC with Strassen's algorithm. By adopting a block-scatter-matrix format, a novel matrix-centric tensor layout, we can conceptually view TC as GEMM for a general stride storage, with an implicit tensor-to-matrix transformation. This insight enables us to tailor a recent state-of-the-art implementation of Strassen's algorithm to a recent state-of-the-art TC, avoiding explicit transpositions (permutations) and extra workspace, and reducing the overhead of memory movement that is incurred. Performance benefits are demonstrated with a performance model as well as in practice on modern single core, multicore, and distributed memory parallel architectures, achieving up to $1.3 \times$ speedup. The resulting implementations can serve as a drop-in replacement for various applications with significant speedup.
Cited by 12
Bryan O’Gorman · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.
Cited by 4Open access
2011
Tensors are multivariate data embedded with complex information in time and space. Tensors of practical interests may conveniently be represented in matrix form with respect to a reference coordinate system. These include for example strain tensors, stress tensors and convective momentum flux tensors. In this chapter, tensor rank reduction techniques are applied. These include: contractions, tensor invariants, principal states and principal axes trajectories combined with evolving tensor ellipses. Study in strain/stress analysis has contributed significantly to the development of tensor visualization techniques both experimentally and theoretically. For example, the two-dimensional photo-elasticity technique in stress analysis has provided experimental means of tensor visualization. Several graphical plots have been developed from tensor/matrix theory to aid visualization of tensor fields. Vorticity tensor is a typical example of antisymmetric tensors and because it plays an important part in hydrodynamics and has analogy in other fields. Controlled Vocabulary Terms hydrodynamics; photoelasticity; stress-strain relations; tensors
Cited by 0
Johnnie Gray, Stefanos Kourtis · Quantum · 2021
Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>×</mml:mo></mml:math>compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.
Cited by 168Open access
Gray, Johnnie, Kourtis, Stefanos · arXiv (Cornell University) · 2020
Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000$\times$ compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.
Cited by 0Open access
Susan Williamson · Linear Algebra and its Applications · 1969
Cited by 11
Somesh Singh, Bora Uçar · IEEE Transactions on Parallel and Distributed Systems · 2025
We investigate the performance of algorithms for sparse tensor-sparse tensor multiplication (SpGETT). This operation, also called sparse tensor contraction, is a higher order analogue of the sparse matrix-sparse matrix multiplication (SpGEMM) operation. Therefore, SpGETT can be performed by first converting the input tensors into matrices, then invoking high performance variants of SpGEMM, and finally reconverting the resultant matrix into a tensor. Alternatively, one can carry out the scalar operations underlying SpGETT in the realm of tensors without matrix formulation. We discuss the building blocks in both approaches and formulate a hashing-based method to avoid costly search or redirection operations. We present performance results with the current state-of-the-art SpGEMM-based approaches, existing SpGETT approaches, and a carefully implemented SpGETT approach with a new fine-tuned hashing method, proposed in this paper. We evaluate the methods on real world tensors by contracting a tensor with itself along varying dimensions. Our proposed hashing-based method for SpGETT consistently outperforms the state-of-the-art method, achieving a 25% reduction in sequential execution time on average and a 21% reduction in parallel execution time on average across a variety of input instances.
Cited by 0Open access
Qingda Lu A, Xiaoyang Gao A, Sriram Krishnamoorthy A et al. · 2013
Cited by 0
Adam Jermyn · SciPost Physics · 2020
The evaluation of partition functions is a central problem in statistical physics. For lattice systems and other discrete models the partition function may be expressed as the contraction of a tensor network. Unfortunately computing such contractions is difficult, and many methods to make this tractable require periodic or otherwise structured networks. Here I present a new algorithm for contracting unstructured tensor networks. This method makes no assumptions about the structure of the network and performs well in both structured and unstructured cases so long as the correlation structure is local.
Cited by 9Open access
Mike Heddes, Igor Nunes, Tony Givargis et al. · ArXiv.org · 2026
Tensor network contraction is a fundamental mathematical operation that generalizes the dot product and matrix multiplication. It finds applications in numerous domains, such as database systems, graph theory, machine learning, probability theory, and quantum mechanics. Tensor network contractions are computationally expensive, in general requiring exponential time and space. Sketching methods include a number of dimensionality reduction techniques that are widely used in the design of approximation algorithms. The existing sketching methods for tensor network contraction, however, only support acyclic tensor networks. We present the first method capable of approximating arbitrary tensor network contractions, including those of cyclic tensor networks. Additionally, we show that the existing sketching methods require a computational complexity that grows exponentially with the number of contractions. We present a second method, for acyclic tensor networks, whose space and time complexity depends only polynomially on the number of contractions.
Cited by 0Open access
Devin A. Matthews · arXiv (Cornell University) · 2016
Tensor computations--in particular tensor contraction (TC)--are important kernels in many scientific computing applications. Due to the fundamental similarity of TC to matrix multiplication (MM) and to the availability of optimized implementations such as the BLAS, tensor operations have traditionally been implemented in terms of BLAS operations, incurring both a performance and a storage overhead. Instead, we implement TC using the flexible BLIS framework, which allows for transposition (reshaping) of the tensor to be fused with internal partitioning and packing operations, requiring no explicit transposition operations or additional workspace. This implementation, TBLIS, achieves performance approaching that of MM, and in some cases considerably higher than that of traditional TC. Our implementation supports multithreading using an approach identical to that used for MM in BLIS, with similar performance characteristics. The complexity of managing tensor-to-matrix transformations is also handled automatically in our approach, greatly simplifying its use in scientific applications.
Cited by 5Open access
Frank Schindler, Adam S. Jermyn · Zurich Open Repository and Archive (University of Zurich) · 2020
Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance
Cited by 11Open access
Mike Heddes, Igor Nunes, Tony Givargis et al. · arXiv (Cornell University) · 2026
Tensor network contraction is a fundamental mathematical operation that generalizes the dot product and matrix multiplication. It finds applications in numerous domains, such as database systems, graph theory, machine learning, probability theory, and quantum mechanics. Tensor network contractions are computationally expensive, in general requiring exponential time and space. Sketching methods include a number of dimensionality reduction techniques that are widely used in the design of approximation algorithms. The existing sketching methods for tensor network contraction, however, only support acyclic tensor networks. We present the first method capable of approximating arbitrary tensor network contractions, including those of cyclic tensor networks. Additionally, we show that the existing sketching methods require a computational complexity that grows exponentially with the number of contractions. We present a second method, for acyclic tensor networks, whose space and time complexity depends only polynomially on the number of contractions.
Cited by 0Open access
Eliot Fried, Nicolas P. D. Sawaya, Yudong Cao et al. · PLoS ONE · 2018
Classical simulation of quantum computation is necessary for studying the numerical behavior of quantum algorithms, as there does not yet exist a large viable quantum computer on which to perform numerical tests. Tensor network (TN) contraction is an algorithmic method that can efficiently simulate some quantum circuits, often greatly reducing the computational cost over methods that simulate the full Hilbert space. In this study we implement a tensor network contraction program for simulating quantum circuits using multi-core compute nodes. We show simulation results for the Max-Cut problem on 3- through 7-regular graphs using the quantum approximate optimization algorithm (QAOA), successfully simulating up to 100 qubits. We test two different methods for generating the ordering of tensor index contractions: one is based on the tree decomposition of the line graph, while the other generates ordering using a straight-forward stochastic scheme. Through studying instances of QAOA circuits, we show the expected result that as the treewidth of the quantum circuit's line graph decreases, TN contraction becomes significantly more efficient than simulating the whole Hilbert space. The results in this work suggest that tensor contraction methods are superior only when simulating Max-Cut/QAOA with graphs of regularities approximately five and below. Insight into this point of equal computational cost helps one determine which simulation method will be more efficient for a given quantum circuit. The stochastic contraction method outperforms the line graph based method only when the time to calculate a reasonable tree decomposition is prohibitively expensive. Finally, we release our software package, qTorch (Quantum TensOR Contraction Handler), intended for general quantum circuit simulation. For a nontrivial subset of these quantum circuits, 50 to 100 qubits can easily be simulated on a single compute node.
Cited by 50Open access
Jiace Sun, Garnet Kin-Lic Chan · arXiv (Cornell University) · 2026
Many computational methods in ab initio quantum chemistry are formulated in terms of high-order tensor contractions, whose cost determines the size of system that can be studied. We introduce stochastic tensor contraction to perform such operations with greatly reduced cost, and present its application to the gold-standard quantum chemistry method, coupled cluster theory with up to perturbative triples. For total energy errors more stringent than chemical accuracy, we reduce the computational scaling to that of mean-field theory, while starting to approach the mean-field absolute cost, thereby challenging the existing cost-to-accuracy landscape. Benchmarks against state-of-the-art local correlation approximations further show that we achieve an order-of-magnitude improvement in both total computation time and error, with significantly reduced sensitivity to system dimensionality and electron delocalization. We conclude that stochastic tensor contraction is a powerful computational primitive to accelerate a wide range of quantum chemistry.
Cited by 0Open access
Jielun Chen, Jiaqing Jiang, Dominik Hangleiter et al. · PRX Quantum · 2025
We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries. Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower computational complexity as compared to tensor networks with general real or complex entries. This raises the question of how this transition in computational complexity manifests itself in the hardness of different tensor-network-contraction schemes. We pursue this question by studying random tensor networks with varying bias toward positive entries. First, we consider contraction via Monte Carlo sampling and find that the transition from hard to easy occurs when the tensor entries become predominantly positive; this can be understood as a tensor-network manifestation of the well-known negative-sign problem in quantum Monte Carlo. Second, we analyze the commonly used contraction based on boundary tensor networks. The performance of this scheme is governed by the number of correlations in contiguous parts of the tensor network (which by analogy can be thought of as entanglement). Remarkably, we find that the transition from hard to easy—i.e., from a volume-law to a boundary-law scaling of entanglement—already occurs for a slight bias of the tensor entries toward a positive mean, scaling inversely with the bond dimension <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mi>D</a:mi></a:math>, and thus the problem becomes easy the earlier the larger <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><d:mi>D</d:mi></d:math> occurs. This is in contrast both to expectations and to the behavior found in Monte Carlo contraction, where the hardness at fixed bias increases with the bond dimension. To provide insight into this early breakdown of computational hardness and the accompanying entanglement transition, we construct an effective classical statistical-mechanical model that predicts a transition at a bias of the tensor entries of <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><g:mn>1</g:mn><g:mo>/</g:mo><g:mi>D</g:mi></g:math>, confirming our observations. We conclude by investigating the computational difficulty of computing expectation values of tensor-network wave functions (projected entangled-pair states, PEPSs) and find that in this setting, the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation that maps PEPS expectation values to a positive-valued tensor network. This not only provides insight into the origin of the observed boundary-law entanglement scaling but also suggests new approaches toward PEPS contraction based on positive decompositions.
Cited by 6Open access