On the optimal evaluation of a set of bilinear forms

Roger W. Brockett, David Dobkin

Research output: Contribution to journalArticle

54 Scopus citations

Abstract

Although general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. In this paper we propose and defined a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems. The problem of minimizing the number of multiplications required to perform a calculation leads to a problem in matrix algebra relating to the expansion of a given set of matrices as linear combinations of rank-one matrices. In this paper we make a systematic attack on this problem and derived some general results which unify and extend numerous known results.

Original languageEnglish (US)
Pages (from-to)207-235
Number of pages29
JournalLinear Algebra and Its Applications
Volume19
Issue number3
DOIs
StatePublished - 1978

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the optimal evaluation of a set of bilinear forms'. Together they form a unique fingerprint.

  • Cite this