Abstract
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 Loge 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.
Research partially supported by an NSF CAREER Grant.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
C. Amodio and N. Mastronardi. A parallel version of the cyclic reduction algorithm on a hypercube. Parallel Computing, 19, 1993.
D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, E. Santos, K. E. Schauser, R. Subramonian, and T. von Eicken. LogP: A Practical Model of Parallel Computation. Communications of the ACM, May 1996.
D. Heller. A survey of parallel algorithms in numerical linear algebra. SIAM J. Numer. Anal., 29(4), 1987.
A. W. Hockney and C. R. Jesshope. Parallel Computers. Adam-Hilger, 1981.
S. L. Johnsson. Solving tridiagonal systems on ensemble architectures. SIAM J. Sci. Stat. Comput., 8, 1987.
R. M. Karp, A. Sahay, E. E. Santos, and K.E. Schauser Optimal Broadcast and Summation on the LogP Model. In Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, 1993.
S. P. Kumar. Solving tridiagonal systems on the butterfly parallel computer. International J. Supercomputer Applications, 3, 1989.
S. Lakshmivarahan and S. D. Dhall. A Lower Bound on the Communication Complexity for Solving Linear Tridiagonal Systems on Cube Architectures. In Hypercubes 1987, 1987.
S. Lakshmivarahan and S. D. Dhall. Analysis and Design of Parallel Algorithms Arithmetic and Matrix Problems. McGraw-Hill, 1990.
F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes. Morgan Kaufmann, 1992.
E. E. Santos. Direct methods for solving tridiagonal linear systems in parallel. Technical Report TR-95-029, International Computer Science Institute, 1995.
E. E. Santos. Optimal and efficient parallel algorithms for summing and prefix summing. In Proceedings of the Eighth Annual IEEE Symposium on Parallel and Distributed Processing, 1996. *** DIRECT SUPPORT *** A0008C42 00024
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Santos, E.E. (1997). Optimal parallel algorithms for solving tridiagonal linear systems. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002802
Download citation
DOI: https://doi.org/10.1007/BFb0002802
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive