TY - GEN
T1 - Optimal tridiagonal solvers on mesh interconnection networks
AU - Santos, Eunice E.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999/1/1
Y1 - 1999/1/1
N2 - We consider the problem of designing optimal and effcient algorithms for solving tridiagonal linear systems on a mesh interconnection network. We derive precise upper and lower bounds for these solvers using odd-even cyclic reduction. We present various important lower bounds on execution time for solving these systems including general lower bounds which are independent of initial data assignment, lower bounds based on classifications of initial data assignments which classify assignments via the proportion of initial data assigned amongst processors, and lower bounds for commonly-used data layouts for tridiagonal solvers. Finally, algorithms are provided which have running times not only within a small constant factor of the lower bounds provided but which are within a small constant additive term of the lower bounds.
AB - We consider the problem of designing optimal and effcient algorithms for solving tridiagonal linear systems on a mesh interconnection network. We derive precise upper and lower bounds for these solvers using odd-even cyclic reduction. We present various important lower bounds on execution time for solving these systems including general lower bounds which are independent of initial data assignment, lower bounds based on classifications of initial data assignments which classify assignments via the proportion of initial data assigned amongst processors, and lower bounds for commonly-used data layouts for tridiagonal solvers. Finally, algorithms are provided which have running times not only within a small constant factor of the lower bounds provided but which are within a small constant additive term of the lower bounds.
UR - http://www.scopus.com/inward/record.url?scp=1242268715&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1242268715&partnerID=8YFLogxK
U2 - 10.1007/3-540-49164-3_3
DO - 10.1007/3-540-49164-3_3
M3 - Conference contribution
AN - SCOPUS:1242268715
SN - 3540656413
SN - 9783540656418
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 28
EP - 37
BT - Parallel Computation - 4th International ACPC Conference Including Special Tracks on Parallel Numerics (ParNum 1999) and Parallel Computing in Image Processing, Video Processing, and Multimedia, Proceedings
A2 - Zinterhof, Peter
A2 - Vajteršic, Marian
A2 - Uhl, Andreas
PB - Springer
T2 - 4th International ACPC Conference on Parallel Computation, ACPC 1999
Y2 - 16 February 1999 through 18 February 1999
ER -