TY - GEN
T1 - Optimal parallel algorithms for solving tridiagonal linear systems
AU - Santos, Eunice E.
PY - 1997/12/1
Y1 - 1997/12/1
N2 - We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods: odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.
AB - We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods: odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.
UR - http://www.scopus.com/inward/record.url?scp=84870926569&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84870926569&partnerID=8YFLogxK
U2 - 10.1007/bfb0002802
DO - 10.1007/bfb0002802
M3 - Conference contribution
AN - SCOPUS:84870926569
SN - 9783540634409
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 700
EP - 709
BT - Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings
PB - Springer
T2 - 3rd International Conference on Parallel Processing, Euro-Par 1997
Y2 - 26 August 1997 through 29 August 1997
ER -