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

DOI10.1016/0022-0000(81)90029-5zbMath0458.68009OpenAlexW2056521480MaRDI QIDQ1151751

John E. Savage

Publication date: 1981

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(81)90029-5

zbMATH Keywords

transitive closurematrix inversioncomputation timecomplexity measurechip areavery large scale integrated semiconductor circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items

Area-time tradeoffs for bilinear forms computations in VLSI ⋮ Area-time complexity of the unconstrained minimization problem ⋮ Communication complexity hierarchy ⋮ Area-time lower-bound techniques with applications to sorting ⋮ The matrix equation MX + XN = B in the VLSI model ⋮ The communication complexity of several problems in matrix computation ⋮ An O(1) time optimal algorithm for multiplying matrices on reconfigurable mesh ⋮ Unbounded hardware is equivalent to deterministic Turing machines ⋮ Area-time tradeoff for rectangular matrix multiplication in VLSI models ⋮ Area-period tradeoffs for multiplication of rectangular matrices ⋮ The performance of multilective VLSI algorithms ⋮ Communication complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Area-time optimal VLSI networks for multiplying matrices
• The Area-Time Complexity of Binary Multiplication