Area-time tradeoff for rectangular matrix multiplication in VLSI models (Q796300)

\textit{J. E. Savage} [(*) J. Comput. Syst. Sci. 22, 230-242 (1981; Zbl 0458.68009)] has shown that the designer of any circuit for multiplying an \(m\times n\) matrix by an \(n\times p\) matrix ((m,n,p) problem) is confronted with an area-time tradeoff expressed by \(AT^ 2=\Omega(m^ 2p^ 2)\), when \((a-n)(b-n)<{1\over2}n^ 2\) with \(a=\max(m,n)\) and \(b=\max(n,p)\). No lower bound is known for the problem (m,n,p) when \((a- n)\times(b-n)\geq {1\over2}n^ 2\). In this paper the result given in (*) is partially emended and a new lower bound is given which holds for any choice of m,n,p, with \(m\geq n\), \(p\geq n\).