Accession Number : AD0751088

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

Descriptive Note : Technical rept.,

Corporate Author : CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hopcroft,John ; Musinski,Jean

Report Date : OCT 1972

Pagination or Media Count : 32

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 implying 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 noncommutative ring with a minimum number of multiplications is derived by considering a dual problem. (Author)

Descriptors :   (*MATRICES(MATHEMATICS), ALGORITHMS), RINGS(MATHEMATICS), TRANSFORMATIONS(MATHEMATICS), DETERMINANTS(MATHEMATICS), THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE