A new class of partitioned matrix algorithms is developed for possible VLSI implementation of large-scale matrix solvers. Fast matrix solvers are higherly demanded in signal/image processing and in many real-time and scientific applications. Only a few functional types of VLSI arithmetic chips are needed for submatrix computations after partitioning. This partitioned approach is not restricted by problem sizes and thus can be applied to solve arbitrarily large linear systems of equations in an iterative fashion. The following four matrix computations are shown systematically partitionable into submatrix operations, which are feasible for direct VLSI implementation.

VLSI modular arithmetic structures and new partitioned matrix algorithms are developed in this paper to perform hardware matrix computations in solving large-scale linear system of equations. Gaussian elimination and inversion of triangular matrices are shown systematically partitionable. All the partitioned algorithms being developed can achieve linear computation time 0(n), where n is the order of the linear system. The partitioned matrix computations are feasible for modular VLSI implementation with constrained I/O terminals. Performance analysis and design tradeoffs of the partitioned VLSI arithmetic structures are also provided.