Efficient VLSI implementation of iterative solutions to sparse linear systems

Manavendra Misra, David Nassimi, Viktor K. Prasanna

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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 languageEnglish (US)
Pages (from-to)525-544
Number of pages20
JournalParallel Computing
Volume19
Issue number5
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Efficient VLSI implementation of iterative solutions to sparse linear systems'. Together they form a unique fingerprint.

Cite this