# The ICICS/CS Reading Room

## UBC CS TR-86-17 Summary

- No on-line copy of this technical report is available.

- 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
help@cs.ubc.ca.