Report Number: CSL-TR-74-77
Institution: Stanford University, Computer Systems Laboratory
Title: Parallel solution methods for triangular linear systems of equations
Author: Orcutt, Samuel E.
Date: June 1974
Abstract: In this paper we consider developing parallel solution methods for triangular linear systems of equations. For a system of N equations in N unknowns the serial method requires O(N2) steps, and the straightforward parallel method requires steps and O(N) processors. In this paper we develop methods that require O(log N) time when used with O(N3) processors and O( R(N) log N) time when used with O(N2) processors. We also consider solutions to band triangular systems and develop a method that requires O((log N) (log m)) time and O(Nm2) processors, where m is the bandwidth of the system.
http://i.stanford.edu/pub/cstr/reports/csl/tr/74/77/CSL-TR-74-77.pdf