Show simple item record

dc.contributor.authorHopcroft, John E.en_US
dc.contributor.authorMusinski, J.en_US
dc.description.abstractThe 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.en_US
dc.format.extent1822636 bytes
dc.format.extent676439 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleDuality Applied to the Complexity of Matrix Multiplication and Other Bilinear Formsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record