| 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++
Department of Information Engineering and Computer Science
Feng Chia University
Taichung, 407 Taiwan
+Department of Computer Science
National Tsing Hua University
Hsinchu, 300 Taiwan
++Department of Computer Science and Information Engineering
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.
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.