Technical Reports

The ICICS/CS Reading Room

UBC CS TR-86-17 Summary

Additional Requirements for Matrix \& Transposed Matrix Products, October 1986 M. Kaminski, David G. Kirkpatrick and N. H. Bshouty

Let $M$ be an $s \times t$ matrix and let $M^{T}$ be the transpose of $M$. Let {\bf x} and {\bf y} be $t$- and $s$-dimensional indeterminate column vectors, respectively. We show that any linear algorithm $A$ that computes $M${\bf x} has associated with it a natural dual linear algorithm denoted $A^{T}$ that computes $M^{T}${\bf y}. Furthermore, if $M$ has no zero rows or columns then the number of additions used by $A^{T}$ exceeds the number of additions used by $A$ by exactly $s-t$. In addition, a strong correspondence is established between linear algorithms that compute the product $M{\bf x}$ and bilinear algorithms that compute the bilinear form ${\bf y}^{T}M{\bf x}$.}

If you have any questions or comments regarding this page please send mail to