Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms

Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms

File(s)
72-147.ps (660.58 KB)
72-147.pdf (1.74 MB)
Permanent Link(s)
https://hdl.handle.net/1813/5999
Collections
Computer Science Technical Reports
Author
Hopcroft, John E.
Musinski, J.
Abstract

The paper considers the complexity of bilinear forms in a noncommutative ring. The dual of a computation is defined and applied to matrix multiplication and other bilinear forms. It is shown that the dual of an optimal computation gives an optimal computation for a dual problem. An nxm by mxp matrix product is shown to be the dual of an nxp by pxm or an mxn by nxp matrix product implyiing that each of the matrix products requires the same number of multiplications to compute. Finally an algorithm for computing a single bilinear form over a noncommutaative ring with a minimum number of multiplications is derived by considering a dual problem.

Date Issued
1972-10
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-147
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance