Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] |

¡@

**
Min-Hsuan Fan, Chua-Huang Huang, Yeh-Ching Chung ^{+}, Jen-Shiuh Liu and Jei-Zhii Lee^{++}
**

Feng Chia University

Taichung, 407 Taiwan

National Tsing Hua University

Hsinchu, 300 Taiwan

National Dong Hwa University

Hualien, 974 Taiwan

In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms. We first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, we try to find a solution of the matrix equation such that the solution is composed of simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for the given problem. In this methodology, the operations of a tensor product formula can be mapped to language constructs of high-level programming languages. That is, we can generate computer programs, including programs for parallel computers and distributed-memory multiprocessors, from tensor product formulas. In this paper, we use the parallel prefix problem and the discrete Fourier transform problem as examples to illustrate the methodology and derive various parallel prefix and fast Fourier transform algorithms.

*
Keywords:
*
programming methodology, tensor product, block recursive algorithm, parallel
processing, distributed processing, parallel prefix, fast Fourier transform

Retrieve PDF document (**200601_06.pdf**)

Received January 9, 2004; revised April 29, 2004; accepted June 8, 2004.

Communicated by Gen-Huey Chen.
^{*} This work was supported in part by the National Science Council, R.O.C., No. NSC 89-2213-E-259-005.