Parallel solution of band triangular linear systems on VLSI arrays with limited fan-out
We are interested in the solution of band lower triangular linear systems of n equations Ax = b of bandwidth w, on modular VLSI arrays whose fan-out f is independent of w and n. Kung and Leiserson [5] have introduced a network such that f = 1 and that works in time T = 2n + w. We exhibit here an array of the same area such that f = 2 and T = n + [w2].We also show that, for any p >= 1, there exists a modular VLSI array of fan-out f = 2p that solves the system in time T @? [np] + [wp], provided that a sufficient number q >= (p + 2) [log"2p] - 1 of first subdiagonals of the matrix are zero.