Area—time tradeoffs for matrix multiplication and related problems in VLSI models

摘要

Two models for very-large scale integrated (VLSI) semiconductor circuits are considered that have been developed by Thompson and by Brent and Kung. The models permit the study of tradeoffs between chip area and computation time. We show that these tradeoffs can be derived from a single common complexity measure of a problem. We derive bounds on this measure for matrix multiplication under weak assumptions about the operations of addition and multiplication. The assumptions are such that the bounds can be applied directly to transitive closure and matrix inversion.