Area-period tradeoffs for multiplication of rectangular matrices

Ferng Ching Lin*, I-Chen Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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 AP = ω((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.

Original languageEnglish
Pages (from-to)329-342
Number of pages14
JournalJournal of Computer and System Sciences
Volume30
Issue number3
DOIs
StatePublished - 1 Jan 1985

Fingerprint Dive into the research topics of 'Area-period tradeoffs for multiplication of rectangular matrices'. Together they form a unique fingerprint.

Cite this