Generalized scans and tridiagonal systems. (English) Zbl 0974.68058

Motivated by the analysis of known parallel techniques for the solution of linear tridiagonal system, we introduce generalized scans, a class of recursively defined length-preserving, sequence-to-sequence transformations that generalize the well-known prefix computations (scans). Generalized scan functions are described in terms of three algorithmic phases, the reduction phase that saves data for the third or expansion phase and prepares data for the second phase which is a recursive invocation of the same function on one fewer variable. Both the reduction and expansion phases operate on bounded number of variables, a key feature for their parallelization. Generalized scans enjoy a property, called here protoassociativity, that gives rise to ordinary associativity when generalized scans are specialized to ordinary scans. We show that the solution of positive-definite block tridiagonal linear systems can be cast as a generalized scan, thereby shedding light on the underlying structure enabling known parallelization schemes for this problem. We also describe a variety of parallel algorithms including some that are well known for tridiagonal systems and some that are much better suited to distributed computation.


68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI


[1] Blelloch, G.E., Scans as primitive parallel operations, IEEE trans. comput., 38, 1526-1538, (1989)
[2] Dongarra, J.J.; Sameh, A.H., On some parallel banded system solvers, Parallel comput., 1, 223-235, (1984) · Zbl 0572.65015
[3] Hockney, R.W., A fast direct solution of Poisson’s equation using Fourier analysis, Jacm, 12, 95-113, (1965) · Zbl 0139.10902
[4] Johnsson, S.L., Solving narrow banded systems on ensemble architectures, research report YALEU/DCS/RR-418, dept. of computer science, (1985), Yale University New Haven, CT · Zbl 0573.68011
[5] Johnsson, S.L., Solving tridiagonal systems on ensemble architectures, SIAM J. sci. statist. comput., 8, 354-392, (1987) · Zbl 0624.65021
[6] Ladner, R.E.; Fischer, M.J., Parallel prefix computation, Jacm, 27, 831-838, (1980) · Zbl 0445.68066
[7] Meier, U., A parallel partition method for solving banded systems of linear equations, Parallel comput., 2, 33-43, (1985) · Zbl 0599.65016
[8] V. Pan, J.H. Reif, Efficient parallel solution of linear systems, Proc. 7th Ann. ACM Symp. on Theory of Computing, 1985, pp. 143-152.
[9] J.H. Reif, \( O( log\^{}\{2\} n)\) Time efficient parallel factorization of dense, sparse separable, and banded matrices, Proc. 6th Ann. ACM Symp. on Parallel Algorithms and Architectures, 1994 pp. 278-289.
[10] Stone, H.S., An efficient parallel algorithm for the solution of a tridiagonal linear system of equations, Jacm, 20, 27-38, (1973) · Zbl 0269.65018
[11] Swarztrauber, P.N., A direct method for the discrete solution of separable elliptic equations, SIAM J. numer. anal., 11, 1136-1150, (1974) · Zbl 0292.65054
[12] Sweet, R.A., A generalized cyclic-reduction algorithm, SIAM J. numer. anal., 11, 506-520, (1974) · Zbl 0253.65061
[13] Sweet, R.A., A cyclic-reduction algorithm for solving block tridiagonal systems of arbitrary dimension, SIAM J. numer. anal., 14, 706-720, (1977) · Zbl 0366.65015
[14] Wang, H.H., A parallel method for tridiagonal equations, ACM trans. math. software, 7, 170-183, (1981) · Zbl 0473.65010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.