Treffer: A programming methodology for designing block recursive algorithms

Title:
A programming methodology for designing block recursive algorithms
Authors:
FAN, Min-Hsuan, HUANG, Chua-Huang, CHUNG, Yeh-Ching, LIU, Jen-Shiuh, LEE, Jei-Zhii
Source:
Journal of information science and engineering. 22(1):95-121
Publisher Information:
Taipei: Institute of Information Science, Academia sinica, 2006.
Publication Year:
2006
Physical Description:
print, 24 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Langages de programmation, Programming languages, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme rapide, Fast algorithm, Algoritmo rápido, Algorithme récursif, Recursive algorithm, Algoritmo recursivo, Langage programmation, Programming language, Lenguaje programación, Langage évolué, High level language, Lenguaje evolucionado, Produit matrice, Matrix product, Producto matriz, Produit tensoriel, Tensor product, Producto tensorial, Programme ordinateur, Computer program, Programa informático, Programme parallèle, Parallel program, Programa paralelo, Théorie programmation, Programming theory, Traitement parallèle, Parallel processing, Tratamiento paralelo, Traitement réparti, Distributed processing, Tratamiento repartido, Transformation Fourier discrète, Discrete Fourier transformation, Transformación Fourier discreta, block recursive algorithm, distributed processing, fast Fourier transform, parallel prefix, parallel processing, programming methodology, tensor product
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Department of Information Engineering and Computer Science Feng Chia University, Taichung, 407, Tawain, Province of China
Department of Computer Science National Tsing Hua University, Hsinchu, 300, Tawain, Province of China
Department of Computer Science and Information Engineering National Dong Hwa University, Hualien, 974, Tawain, Province of China
ISSN:
1016-2364
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17396360
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17396360
Database:
PASCAL Archive

Weitere Informationen

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.