TY - GEN
T1 - Generalized scans and tri-diagonal systems
AU - Fischer, Paul F.
AU - Preparata, Franco P.
AU - Savage, John E.
N1 - Funding Information:
E-mail address: jes@cs.brown.edu (J.E. Savage). 1Supported in part by NSF Grant ACS-9405403 and AFOSR Grant F49620-95-1-0074. 2Supported in part by NSF Grant CCR-9400232. 3Supported in part by the O@ce of Naval Research under contract N00014-91-J-4052, ARPA Order 8225. 4Supported in part by NSF Grant MIP-902570.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.
PY - 1995
Y1 - 1995
N2 - The classical problem of solving tridiagonal linear systems of equations is reconsidered. An extremely simple factorization of the system's matrix - implied by but not explicit in the known techniques - is identified and shown to belong to a class of transformations termed generalized scans. This class has an associative property which is the key to the complete parallelization of the technique. Due to the very weak constraints upon which it is based, the method extends naturally to arbitrary banded systems.
AB - The classical problem of solving tridiagonal linear systems of equations is reconsidered. An extremely simple factorization of the system's matrix - implied by but not explicit in the known techniques - is identified and shown to belong to a class of transformations termed generalized scans. This class has an associative property which is the key to the complete parallelization of the technique. Due to the very weak constraints upon which it is based, the method extends naturally to arbitrary banded systems.
UR - http://www.scopus.com/inward/record.url?scp=84892056557&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84892056557&partnerID=8YFLogxK
U2 - 10.1007/3-540-59042-0_71
DO - 10.1007/3-540-59042-0_71
M3 - Conference contribution
AN - SCOPUS:84892056557
SN - 3540590420
SN - 9783540590422
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 168
EP - 180
BT - STACS 1995 - 12th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Mayr, Ernst W.
A2 - Puech, Claude
PB - Springer
T2 - 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1995
Y2 - 2 March 1995 through 4 March 1995
ER -