Generalized scans and tridiagonal systems

Motivated by the analysis of known parallel techniques for the solution of linear tridiagonal system, we introduce generalized scans, a class of recur sively defined length-preserving, sequence-to-sequence transformations that generalize the well-known prefix computations (scans). Generalized scan fu nctions are described in terms of three algorithmic phases, the reduction p hase that saves data for the third of expansion phase and prepares data for the second phase which is a recursive invocation of the same function on o ne fewer variable. Both the reduction and expansion phases operate on bound ed number of variables, a key feature for their parallelization. Generalize d scans enjoy a property, called here protoassociativity, that gives rise t o ordinary associativity when generalized scans are specialized to ordinary scans. We show that the solution of positive-definite block tridiagonal li near systems can be cast as a generalized scan, thereby shedding light on t he underlying structure enabling known parallelization schemes for this pro blem. We also describe a variety of parallel algorithms including some that are well known for tridiagonal systems and some that are much better suite d to distributed computation. (C) 2001 Elsevier Science B.V. All rights res erved.