Area-period tradeoffs for multiplication of rectangular matrices (Q1060844)

A VLSI computation model is presented with a time dimension in which the concept of information transfer is made precise and memory requirements (lower bounds for A) and area-period trade-offs (lower bounds for \(AP^ 2)\) are treated uniformly. By employing the transitivities of cyclic shiftings and binary multiplication it is proved that \(AP^{2\alpha}=\Omega ((\min (mn,np)\ell)^{1+\alpha}),\) \(0\leq \alpha \leq 1\), for the problem of multiplying \(m\times n\) and \(n\times p\) matrices of \(\ell\)-bit elements. We also show that min(mn,mp,np)\(\ell\) is the exact bound for chip area.