TY - JOUR
T1 - Area-period tradeoffs for multiplication of rectangular matrices
AU - Lin, Ferng Ching
AU - Wu, I-Chen
PY - 1985/6
Y1 - 1985/6
N2 - 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 AP2) are treated uniformly. By employing the transitivities of cyclic shiftings and binary multiplication it is proved that AP2α = ω((min(mn, mp, np)l)1 + α), 0 ≤5 α ≤ 51, for the problem of multiplying m × n and n × p matrices of l-bit elements. We also show that min(mn, mp,np)l is the exact bound for chip area.
AB - 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 AP2) are treated uniformly. By employing the transitivities of cyclic shiftings and binary multiplication it is proved that AP2α = ω((min(mn, mp, np)l)1 + α), 0 ≤5 α ≤ 51, for the problem of multiplying m × n and n × p matrices of l-bit elements. We also show that min(mn, mp,np)l is the exact bound for chip area.
UR - http://www.scopus.com/inward/record.url?scp=0022083885&partnerID=8YFLogxK
U2 - 10.1016/0022-0000(85)90050-9
DO - 10.1016/0022-0000(85)90050-9
M3 - Article
AN - SCOPUS:0022083885
SN - 0022-0000
VL - 30
SP - 329
EP - 342
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 3
ER -