On the optimal evaluation of a set of n-linear forms

David Dobkin

Research output: Contribution to conferencePaperpeer-review

6 Scopus citations


At the heart of a number of arithmetic complexity problems are some basic questions in tensor analysis. Questions regarding the complexity of multiplication operations which are n-linear are most easily studied in a tensor analytic framework. Certain results of tensor analysis are used in this paper to provide insight into the solution of some of these problems. Methods are given to determine a partial ordering on the set of tensors corresponding to a partial ordering with respect to complexity on the set of n-linear operations. Different classes of algorithms for evaluating n-linear operations are studied and a generalized cost criterion is used. Algorithms are given for determining the rank of a class of third order tensors and a canonical form for such tensors is presented. Bounds on the complexity of a wide class of operations are also derived.

Original languageEnglish (US)
Number of pages11
StatePublished - Jan 1 1973
Event14th Annual Symposium on Switching and Automata Theory - Iowa City, United States
Duration: Oct 15 1973Oct 17 1973


Conference14th Annual Symposium on Switching and Automata Theory
Country/TerritoryUnited States
CityIowa City

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Control and Optimization
  • Theoretical Computer Science
  • Artificial Intelligence


Dive into the research topics of 'On the optimal evaluation of a set of n-linear forms'. Together they form a unique fingerprint.

Cite this