A programming methodology for designing parallel prefix algorithms

In this paper we use the tensor product notation as the framework of a programming methodology for designing various parallel prefix algorithms. In this methodology, we first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, solve the matrix equation to obtain some simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for this problem. We will use the parallel prefix computation problem to illustrate our methodology and derive various parallel prefix algorithms including divide-and-conquer and recursive doubling algorithms.