Multiprocessor Schemes for Solving Block Tridiagonal Linear Systems

Abstract

The solution of large, banded diagonally dominant or symmetric positive definite linear systems constitutes one of the most common computational tasks asso ciated with implementations of the finite element method in applications such as fluid dynamics and structural analysis. Thus, designing multiprocessor algorithms for solving large block tridiagonal systems becomes of paramount importance for efficient imple mentation of these applications on vector and parallel machines. We present such schemes here, along with specific performance results on the Alliant FX/8 and CRAY X-MP/48. We particularly emphasize the speedups obtained with these schemes over popular direct band solvers. The development of a candidate scheme for the multicluster CEDAR machine is our goal.

Get full access to this article

View all access options for this article.

References

Berry, M. , Gallivan, K. , Harrod, W. , Jalby, W. , Lo, S. , Meier, U. , Phillipe, B. , and Sameh, A. 1986. Parallel numerical algorithms on the CEDAR system. Lecture Notes in Comput. Sci. 237:25-39.

Calahan, D. 1986. Block-oriented, local-memory-based linear equation solution on the CRAY-2: uni-processor algorithms. Proc. of ICPP 1986, Washington, D.C.: IEEE Computer Press.

Dekker, T. , and Hoffman, W. 1986. Rehabilitation of the Gauss-Jordan algorithm. Technical Report 86-28. University of Amsterdam, Dept. of Mathematics.

Dongarra, J. , Bunch, J. , Moler, C. , and Stewart, G.W. 1979. LINPACK Users' Guide, Philadelphia : SIAM.

Dongarra, J. , DuCroz, J. , Hammarling, S. , and Hanson, R. 1984. A proposal for an extended set of Fortran basic linear algebra subprograms. Technical Memo No. 41, Argonne National Laboratory, Mathematics and Computer Science Division.

Gallivan, K. , Jalby, W. , and Meier, U. 1987. The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory. SIAM J. Sci. Stat. Comput. 18:6:1079-1084.

Golub, G. , and Van Loan, C. 1983. Matrix Computations. Baltimore : The Johns Hopkins University Press.

Guzzi, M. 1987. CEDAR Fortran programmer's handbook. CSRD Report No. 601 . University of Illinois at Urbana-Champaign.

Heller, D. 1976. Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems. SIAM J. Numer. Anal. 13:484-496.

10.

Kuck, D. , Davidson, E. , Lawrie, D. , and Sameh, A. 1986. Parallel supercomputing today and the CEDAR approach . Science 231:967-974.

11.

McGrath, R. , and Emrath, P. 1987. Using memory in the CEDAR system. CSRD Report No. 655 . University of Illinois at Urbana-Champaign.

12.

Peters, G. , and Wilkinson, J. , 1975. On the stability of Gauss-Jordan elimination with pivoting . CACM 18:20-24.

13.

Sameh, A. 1983. On two numerical algorithms for multiprocessors. Proc. of NATO Adv. Res. Workshop on High-Speed Comp. (Series F: Computer and Systems Sciences), New York: Springer-Verlag .