Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/5999
Title: Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
Authors: Hopcroft, John E.
Musinski, J.
Keywords: computer science
technical report
Issue Date: Oct-1972
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-147
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.
URI: http://hdl.handle.net/1813/5999
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
72-147.pdf1.78 MBAdobe PDFView/Open
72-147.ps660.58 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us