Complexity Issues for Solving Triangular Linear Systems in Parallel

TitleComplexity Issues for Solving Triangular Linear Systems in Parallel
Publication TypeTechnical Report
Year of Publication1994
AuthorsSantos, E. E.
Other Numbers935

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.

Bibliographic Notes

ICSI Technical Report TR-94-065

Abbreviated Authors

E. E. Santos

ICSI Publication Type

Technical Report