Sridhar, MK and Srinath, R and Parthasarathy, K (1987) On the direct parallel solution of systems of linear equations: New algorithms and systolic structures. In: Information Sciences, 43 (1-2). pp. 25-53.Full text not available from this repository. (Request a copy)
The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.
|Item Type:||Journal Article|
|Additional Information:||Copyright of this article belongs to Elsevier Science.|
|Department/Centre:||Division of Electrical Sciences > Electrical Engineering|
|Date Deposited:||12 Jan 2010 09:30|
|Last Modified:||12 Jan 2010 09:30|
Actions (login required)