@inproceedings{004dbd9fddae470ebff93e7c26e0e1c4,
title = "Optimal tridiagonal solvers on mesh interconnection networks",
abstract = "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.",
author = "Santos, {Eunice E.}",
year = "1999",
month = jan,
day = "1",
doi = "10.1007/3-540-49164-3_3",
language = "English (US)",
isbn = "3540656413",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "28--37",
editor = "Peter Zinterhof and Marian Vajter{\v s}ic and Andreas Uhl",
booktitle = "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",
note = "4th International ACPC Conference on Parallel Computation, ACPC 1999 ; Conference date: 16-02-1999 Through 18-02-1999",
}