Complexity Issues for Solving Triangular Linear Systems in Parallel
Title | Complexity Issues for Solving Triangular Linear Systems in Parallel |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Santos, E. E. |
Other Numbers | 935 |
Abstract | We consider the problem of solving triangular linear systems on parallel distributed-memory machines. Working with the LogP model, we present tight asymptotic bounds for solving these systems using forward/back- ward substitution. Specifically, in this paper we present lower bounds on execution time independent of the data layout, lower bounds for data layouts in which the number of data items per processor is bounded, and lower bounds for specific data layouts commonly used in designing parallel algorithms for this problem. Furthermore, algorithms are provided which have running times within a constant factor of the lower bounds described. Finally, we present a generalization of the lower bounds to banded triangular linear systems. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-94-065.pdf |
Bibliographic Notes | ICSI Technical Report TR-94-065 |
Abbreviated Authors | E. E. Santos |
ICSI Publication Type | Technical Report |