Journal article
On designing optimal parallel triangular solvers
Information and computation, v 161(2), pp 172-210
2000
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
This paper explores the problem of solving triangular linear systems on parallel distributed-memory machines. Working within the LogP model, tight asymptotic bounds for solving these systems using forward/backward substitution are presented. Specifically, 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 are presented in this paper. Furthermore, algorithms are provided which have running times within a constant factor of the lower bounds described. One interesting result is that the popular two-dimensional block matrix layout necessarily results in significantly longer running times than simpler one-dimensional schemes. Finally, a generalization of the lower bounds to banded triangular linear systems is presented.
Metrics
1 Record Views
Details
- Title
- On designing optimal parallel triangular solvers
- Creators
- Eunice E. Santos - Virginia Tech
- Publication Details
- Information and computation, v 161(2), pp 172-210
- Publisher
- Elsevier Inc
- Number of pages
- 39
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- School of Engineering
- Web of Science ID
- WOS:000089567800003
- Scopus ID
- 2-s2.0-0034666806
- Other Identifier
- 991022207051604721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
Source: SDGs in the Output
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied