Area-Time Optimal VLSI Networks for Matrix Multiplication and Inversion of Triangular Matrices.
Abstract
This report consists of two papers describing networks for parallel matrix operations. In the first paper, Area-time optimal VLSI (Very Large Scale Integration) networks for multiplying matrices, we describe a class of VLSI networks having chip area A for multiplying two n x n matrices in time T, with an area x time squared product A.T squared = O(n to the 4th power). These networks achieve Savage's lower bound to this complexity measure for any T such that log n < or = T < or = n. The second paper, Optimal integrated-circuit implementation of triangular matrix inversion, describes a class of VLSI implementations of algorithms for inverting an n x n triangular matrix. These networks have area A and time T, with an area x time squared AT squared = O(n to the 4th power) for all values of T such that O(2 log n) < or = T < or = O(n). Since there is a simple reduction of matrix multiplication to inversion of a triangular matrix, due to Savage's result the presented networks are optimal in the VLSI model.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1980
- Accession Number
- ADA123944
Entities
People
- Franco P. Preparata
- Jean E. Vuillemin
Organizations
- University of Illinois Urbana–Champaign