Abstract
We propose a novel way of solving systems of linear equations with sparse coefficient matrices using iterative methods on a VLSI array. The nonzero entries of the coefficient matrix are mapped onto a processor array of size √e × √e, where e is the number of nonzero elements, n is the number of equations and e ≥ n. The data transport problem that arises because of this mapping is solved using an efficient routing technique. Preprocessing is carried out on the iteration matrix of the system to compute the routing control-words that are used in the data transfer. This results in O(√e) time for each iteration of the method, with a small constant factor. As compared to existing VLSI methods for solving the problem, the proposed method yields a superior time performance, greater ease of programmability and an area efficient design. We also develop a second implementation of our algorithm that uses a slightly higher number of communication steps, but reduces the number of arithmetic operations to O(log e). The latter algorithm is suitable for many other architectures as well. The algorithm can be implemented in O(log e) time using e processors on a hypercube, shuffle-exchange, and cube-connected-cycles.
Original language | English (US) |
---|---|
Pages (from-to) | 525-544 |
Number of pages | 20 |
Journal | Parallel Computing |
Volume | 19 |
Issue number | 5 |
DOIs | |
State | Published - May 1993 |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computer Graphics and Computer-Aided Design
- Artificial Intelligence
Keywords
- Linear equation system
- VLSI architecture
- iiterative methods
- multiprocessor systems
- sparse matrices