Area-period tradeoffs for multiplication of rectangular matrices

DOI10.1016/0022-0000(85)90050-9MaRDI QIDQ1060844zbMATH OpenOpenAlexFDO

Authors Ferng-Ching Lin, I-Chen Wu

Publication date 1985

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(85)90050-9

zbMATH Keywords

chip areacyclic shiftingsinformation transfermatrix multiplicationmemory requirementsVLSI computation model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Area-time tradeoff for rectangular matrix multiplication in VLSI models
• scientific article; zbMATH DE number 3911707
• scientific article; zbMATH DE number 4057005
• A Robust Matrix-Multiplication Array
• scientific article; zbMATH DE number 3905849

Cites work

• Area-time optimal VLSI networks for multiplying matrices
• Area-time tradeoffs for matrix multiplication and related problems in VLSI models
• scientific article; zbMATH DE number 3628373 (Why is no real title available?)
• scientific article; zbMATH DE number 3449755 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Information transfer and area-time tradeoffs for VLSI multiplication
• Some Area-Time Tradeoffs for VLSI
• The Area-Time Complexity of Binary Multiplication

Cited in

(5)

• The communication complexity of several problems in matrix computation
• Rectangular matrix multiplication revisited
• Optimal Allocation of Area for Single-Chip Computations
• Area time trade-offs in micro-grain VLSI array architectures
• Area-time tradeoff for rectangular matrix multiplication in VLSI models

This page was built for publication: Area-period tradeoffs for multiplication of rectangular matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060844)