Abstract
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.
Supported in part by NSF Grant ACS-9405403 and AFOSR grant F49620-93-1-0090.
The research of F.P. Preparata and J.E. Savage was supported in part by the Office of Naval Research under contract N00014-91-J-4052, ARPA Order 8225. In addition F.P. Preparata and J.E. Savage were supported in part by NSF Grants CCR-9400232 and MIP-902570, respectively.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Dehne, A. Fabri, and A. Rau-Chaplin, Scalable Parallel Geometric Algorithms for Coarse Grained Multicomputers. Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, 298–307, 1993.
J.J. Dongarra and A.H. Sameh. On Some Parallel Banded System Solvers. Parallel Computing, 1:223–235, 1984.
R.W. Hockney. A Fast Direct Solution of Poisson's Equation Using Fourier Analysis. JACM, 12:95–113, 1965.
S.L. Johnsson. Solving Narrow Banded Systems on Ensemble Architectures. Research Report YALEU/DCS/RR-418 Dept. of Computer Science, Yale University, New Haven, CT, August 1985.
S.L. Johnsson. Solving Tridiagonal Systems on Ensemble Architectures SIAM J. of. Sci. Statist. Comput., 8:354–392, 1987.
R. E. Ladner and M. J. Fischer. Parallel Prefix Computation. JACM, 27:831–838, Oct. 1980.
U. Meier. A Parallel Partition Method for Solving Banded Systems of Linear Equations. Parallel Computing, 2:33–43, 1985.
H.S. Stone. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations. JACM, 20:27–38, Jan. 1973.
P.N. Swarztrauber. A Direct Method for the Discrete Solution of Separable Elliptic Equations. SIAM J. of Num. Anal., 11:1136–1150, 1974.
R.A. Sweet. A Generalized Cyclic-Reduction Algorithm. SIAM J. of Num. Anal., 11:506–520, 1974.
R.A. Sweet. A Cyclic-Reduction Algorithm for Solving Block Tridiagonal Systems of Arbitrary Dimension. SIAM J. of. Num. Anal., 14:706–720, 1977.
H.H. Wang. A Parallel Method for Tridiagonal Equations. ACM Trans. Math. Software, 7:170–183, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fischer, P.F., Preparata, F.P., Savage, J.E. (1995). Generalized scans and tri-diagonal systems. In: Mayr, E.W., Puech, C. (eds) STACS 95. STACS 1995. Lecture Notes in Computer Science, vol 900. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59042-0_71
Download citation
DOI: https://doi.org/10.1007/3-540-59042-0_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59042-2
Online ISBN: 978-3-540-49175-0
eBook Packages: Springer Book Archive