The arithmetic complexity of tensor contractions

DOI10.4230/LIPICS.STACS.2013.365MaRDI QIDQ2957898zbMATH OpenOpenAlexFDO

Authors Florent Capelli, Arnaud Durand, Stefan Mengel

Publication date 30 January 2017

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

zbMATH Keywords

arithmetic circuitstensor calculusalgebraic complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: We investigate the algebraic complexity of tensor calulus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture VP, the class of polynomial families efficiently computable by arithmetic circuits. This gives a natural and robust characterization of this complexity class that despite its naturalness is not very well understood so far.

Recommendations

• The arithmetic complexity of tensor contraction
• The complexity of tensor calculus
• Characterizing Valiant's algebraic complexity classes
• Circuits arithmétiques et calculs tensoriels
• The complexity of tensor circuit evaluation

Cited in

(10)

• Circuits arithmétiques et calculs tensoriels
• The Hackbusch conjecture on tensor formats. II.
• The arithmetic complexity of tensor contraction
• Strassen's Algorithm for Tensor Contraction
• Algorithmic simplification of tensor expressions
• scientific article; zbMATH DE number 1834647 (Why is no real title available?)
• The complexity of tensor calculus
• Algebraic complexity classes
• The complexity of tensor circuit evaluation
• Length Complexity of Tensor Products

This page was built for publication: The arithmetic complexity of tensor contractions

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