EFFICIENT VLSI IMPLEMENTATION OF ITERATIVE SOLUTIONS TO SPARSE LINEAR-SYSTEMS

We propose a novel way of solving systems of linear equations with spa rse coefficient matrices using iterative methods on a VLSI array. The nonzero entries of the coefficient matrix are mapped onto a processor array of size square-root e X square-root e, where e is the number of nonzero elements, n is the number of equations and e greater-than-or-e qual-to n. The data transport problem that arises because of this mapp ing is solved using an efficient routing technique. Preprocessing is c arried out on the iteration matrix of the system to compute the routin g control-words that are used in the data transfer. This results in O( square-root e) time for each iteration of the method, with a small con stant factor. As compared to existing VLSI methods for solving the pro blem, 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 n umber of communication steps, but reduces the number of arithmetic ope rations to O(log e). The latter algorithm is suitable for many other a rchitectures as well. The algorithm can be implemented in O(log e) tim e using e processors on a hypercube, shuffle-exchange, and cube-connec ted-cycles.