home

publications

teaching

short CV

personal

the pub

publications

This cartoon is out of the famous comic series Asterix (from the issue "Asterix in Britain"). The text reads: "After 2000 years of maintenance, my lawn will be quite bearable, I think." The "lawns" below were created in less time but with the same commitment to quality.

Submitted

1. Frédéric de Mesmay, Srinivas Chellappa, Franz Franchetti and Markus Püschel
   Computer Generation of Efficient Software Viterbi Decoders
   submitted for publication
2. Srinivas Chellappa, Franz Franchetti and Markus Püschel
   Computer Generation of Fast FFTs for the Cell Broadband Engine
   submitted for publication
3. Daniel McFarlin, Franz Franchetti, José M. F. Moura and Markus Püschel
   High Performance Synthetic Aperture Radar Image Formation On Commodity Architectures
   submitted for publication
4. Franz Franchetti and Markus Püschel
   Generating High-Performance Pruned FFT Implementations
   submitted for publication
5. Markus Püschel, Peter A. Milder and James C. Hoe
   Permuting Streaming Data Using RAMs
   to appear in Journal of the ACM
6. Yevgen Voronenko and Markus Püschel
   Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Real DFTs
   to appear in IEEE Transactions on Signal Processing

Journal/Book Chapters/Conference Papers (Fully Reviewed)

1. Srinivas Chellappa, Franz Franchetti and Markus Püschel
   How To Write Fast Numerical Code: A Small Introduction
   Proc. Summer School on Generative and Transformational Techniques in Software Engineering (GTTSE), Lecture Notes in Computer Science, Springer, Vol. 5235, pp. 196-259, 2008
2. Markus Püschel
   DFT and FFT: An Algebraic View
   in Fast Fourier Transforms, Eds. C. Sidney Burrus, Connexions 2008
3. Markus Püschel and José M. F. Moura
   Algebraic Signal Processing Theory: Foundation and 1-D Time
   IEEE Transactions on Signal Processing, Vol. 56, No. 8, pp. 3572-3585, 2008
4. Markus Püschel and José M. F. Moura
   Algebraic Signal Processing Theory: 1-D Space
   IEEE Transactions on Signal Processing, Vol. 56, No. 8, pp. 3586-3599, 2008
5. Markus Püschel and José M. F. Moura
   Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
   IEEE Transactions on Signal Processing, Vol. 56, No. 4, pp. 1502-1521, 2008
6. Markus Püschel and Martin Rötteler
   Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms on the 2-D Spatial Hexagonal Lattice
   Applicable Algebra in Engineering, Communication and Computing, special issue on "The memory of Thomas Beth", Vol. 19, No. 3, pp. 259-292, 2008
7. Franz Franchetti and Markus Püschel
   Generating SIMD Vectorized Permutations
   Proc. International Conference on Compiler Construction (CC), Lecture Notes in Computer Science, Springer, Vol. 4959, pp. 116-131, 2008
8. (Best paper award nominee, among 11 out of 147) Peter A. Milder, Franz Franchetti, James C. Hoe and Markus Püschel
   Formal Datapath Representation and Manipulation for Implementing DSP Transforms
   Proc. Design Automation Conference (DAC), 2008
9. Christina A. Hallock, Inci Özgünes, Ramamurthy Bhagavatula, Gustavo K. Rohde, Justin C. Crowley, Christina E. Onorato, Abhay Mavalankar, Amina Chebira, Chuen Hwa Tan, Markus Püschel and Jelena Kovacevic
   Axonal Bouton Modeling Detection and Distribution Analysis for the Study of Neural Circuit Organization and Plasticity
   Proc. International Symposium on Biomedical Imaging (ISBI), pp. 165-168, 2008
10. Doru Balcan, Aliaksei Sandryhaila, Jonathan Gross and Markus Püschel
    Alternatives to the Discrete Fourier Transform
    Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3537-3540, 2008
11. Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel
    Haar Filter Banks for 1-D Space Signals
    Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3505-3508, 2008
    
    2007
12. Yevgen Voronenko and Markus Püschel
    Mechanical Derivation of Fused Multiply-Add Algorithms for Linear Transforms
    IEEE Transactions on Signal Processing, Vol. 55, No. 9, pp. 4458-4473, 2007
13. Peter Tummeltshammer, James C. Hoe and Markus Püschel
    Time-Multiplexed Multiple Constant Multiplication
    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 26, No. 9, pp. 1551-1563, 2007
14. Markus Püschel and Martin Rötteler
    Algebraic Signal Processing Theory: 2-D Spatial Hexagonal Lattice
    IEEE Transactions on Image Processing, Vol. 16, No. 6, pp. 1506-1521, 2007
15. Yevgen Voronenko and Markus Püschel
    Multiplierless Multiple Constant Multiplication
    ACM Transactions on Algorithms, Vol. 3, No. 2, 2007
16. Amina Chebira, Luis P. Coelho, Aliaksei Sandryhaila, Stephen Lin, William G. Jenkinson, Jeremiah MacSleyne, Christopher Hoffman, Philipp Cuadra, Charles Jackson, Markus Püschel, and Jelena Kovacevic
    An Adaptive Multiresolution Approach to Fingerprint Recognition
    Proc. International Conference on Image Processing (ICIP), Vol. 1, pp. I-457-I-460, 2007
17. Franz Franchetti and Markus Püschel
    SIMD Vectorization of Non-Two-Power Sized FFTs
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 2, pp. II-17-II-20, 2007
18. Paolo D'Alberto, Franz Franchetti, Peter A. Milder, Aliaksei Sandryhaila, James C. Hoe, José M. F. Moura and Markus Püschel
    Generating FPGA Accelerated DFT Libraries
    Proc. IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2007
19. Paolo D'Alberto, Markus Püschel and Franz Franchetti
    Performance/Energy Optimization of DSP Transforms on the XScale Processor
    Proc. International Conference on High Performance Embedded Architectures & Compilers (HiPEAC), 2007
    
    2006
20. (Best paper award, 1 out of 80) Andreas Bonelli, Franz Franchetti, Juergen Lorenz, Markus Püschel and Christoph W. Ueberhuber
    Automatic Performance Optimization of the Discrete Fourier Transform on Distributed Memory Computers
    Proc. International Symposium on Parallel and Distributed Processing and Application (ISPA), 2006
21. Franz Franchetti, Yevgen Voronenko and Markus Püschel
    FFT Program Generation for Shared Memory: SMP and Multicore
    Proc. Supercomputing (SC), 2006
22. Sung-Chul Han, Franz Franchetti and Markus Püschel
    Program Generation for the All-Pairs Shortest Path Problem
    Proc. Parallel Architectures and Compilation Techniques (PACT) , pp. 222-232, 2006
23. Franz Franchetti, Yevgen Voronenko and Markus Püschel
    A Rewriting System for the Vectorization of Signal Transforms
    Proc. High Performance Computing for Computational Science (VECPAR), Lecture Notes in Computer Science, Springer, Vol. 4395, pp. 363-377, 2006
24. Yevgen Voronenko and Markus Püschel
    Algebraic Derivation of General Radix Cooley-Tukey Algorithms for the Real Discrete Fourier Transform
    Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 3, 2006
25. Markus Püschel and José M. F. Moura
    The Algebraic Structure in Signal Processing: Time and Space
    Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 5, 2006
26. Jelena Kovacevic and Markus Püschel
    Sampling Theorem Associated with the Discrete Cosine Transform
    Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 3, 2006
27. Peter A. Milder, Mohammad Ahmad, James C. Hoe and Markus Püschel
    Fast and Accurate Resource Estimation of Automatically Generated Custom DFT IP Cores
    Proc. FPGA, pp. 211-220, 2006
    
    2005
28. Markus Püschel and Martin Rötteler
    Fourier Transform for the Spatial Quincunx Lattice
    Proc. IEEE International Conference on Image Processing (ICIP), Vol. 2, pp. 494-497, 2005
29. Franz Franchetti, Yevgen Voronenko and Markus Püschel
    Formal Loop Merging for Signal Transforms
    Proc. Programming Languages Design and Implementation (PLDI), pp. 315-326 , 2005
30. Grace Nordin, Peter A. Milder, James C. Hoe and Markus Püschel
    Automatic Generation of Customized Discrete Fourier Transform IPs
    Proc. Design Automation Conference (DAC), 2005, pp. 471-474
31. Markus Püschel and Jelena Kovacevic
    Real, Tight Frames Maximally Robust To Erasures
    Proc. Data Compression Conference (DCC), pp. 63-72, 2005
32. Markus Püschel and Martin Rötteler
    Fourier Transform for the Directed Quincunx Lattice
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2005
33. Thammanit Pipatsrisawat, Aca Gacic, Franz Franchetti, Markus Püschel and José M. F. Moura
    Performance Analysis of the Filtered Backprojection Image Reconstruction Algorithms
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 5, pp. 153-156, 2005
34. Markus Püschel, José M. F. Moura, Jeremy Johnson, David Padua, Manuela Veloso, Bryan Singer, Jianxin Xiong, Franz Franchetti, Aca Gacic, Yevgen Voronenko, Kang Chen, Robert W. Johnson and Nicholas Rizzolo
    SPIRAL: Code Generation for DSP Transforms
    Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", Vol. 93, No. 2, 2005, pp. 232- 275
35. José M. F. Moura, Markus Püschel, David Padua and Jack Dongarra
    Scanning the Issue: Special Issue on Program Generation, Optimization, and Platform Adaptation
    Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", Vol. 93, No. 2, pp. 211-215, 2005
    
    2004
36. Markus Püschel, Adam C. Zelinski and James C. Hoe
    Custom-Optimized Multiplierless Implementations of DSP Algorithms
    Proc. International Conference on Computer-Aided Design (ICCAD), pp. 175-182, 2004
37. Peter Tummeltshammer, James C. Hoe and Markus Püschel
    Multiple Constant Multiplication By Time-Multiplexed Mapping of Addition Chains
    Proc. Design Automation Conference (DAC), pp. 826-829, 2004
38. Franz Franchetti, Stefan Kral, Juergen Lorenz, Markus Püschel, Christoph W. Ueberhuber and Peter Wurzinger
    Automatically Tuned FFTs for BlueGene/L’s Double FPU
    Proc. High Performance Computing for Computational Science (VECPAR), Lecture Notes in Computer Science, Springer, Vol. 3402, pp. 23-36, 2004
39. Markus Püschel and Martin Rötteler
    The Discrete Triangle Transform
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2004
40. Adam C. Zelinski, Markus Püschel, Smarahara Misra and James C. Hoe
    Automatic Cost Minimization for Multiplierless Implementations of Discrete Signal Transforms
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2004, Vol. 5, pp. V-221-V-224
41. Aca Gacic, Markus Püschel and José M. F. Moura
    Automatically Generated High-Performance Code for Discrete Wavelet Transforms
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2004, Vol. 5, pp. V-69-V-72
42. Yevgen Voronenko and Markus Püschel
    Automatic Generation of Implementations for DSP Transforms on Fused Multiply-Add Architectures
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2004, Vol. 5, pp. V-101-V-104
43. Markus Püschel, Bryan Singer, Jianxin Xiong, José M. F. Moura, Jeremy Johnson, David Padua, Manuela Veloso and Robert W. Johnson
    SPIRAL: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms
    Journal of High Performance Computing and Applications, special issue on "Automatic Performance Tuning", Vol. 18, No. 1, 2004, pp. 21-45
44. Jeremy Johnson, José Moura, Markus Püschel, Dan Rockmore
    Special Issue on Computer Algebra and Signal Processing: Foreword by the Guest Editors
    Journal of Symbolic Computation 2004, Vol. 37, No. 2, pp. 133-135
45. Sebastian Egner and Markus Püschel
    Symmetry-Based Matrix Factorization
    Journal of Symbolic Computation 2004, special Issue on Computer Algebra and Signal Processing, Vol. 37, No. 2, pp. 157-186
    
    2003
46. (Best paper award nominee, among 14 out of 152) Fang Fang, Rob A. Rutenbar, Markus Püschel and Tsuhan Chen
    Toward Efficient Static Analysis of Finite-Precision Effects in DSP Applications via Affine Arithmetic Modeling
    Proc. Design Automation Conference (DAC), 2003, pp. 496-501
47. Markus Püschel and José Moura
    The Algebraic Approach to the Discrete Cosine and Sine Transforms and their Fast Algorithms
    SIAM Journal of Computing 2003, Vol. 32, No. 5, pp. 1280-1316
48. Markus Püschel
    Cooley-Tukey FFT like Algorithms for the DCT
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2003, Vol. 2, pp. 501-504
49. Franz Franchetti and Markus Püschel
    Short Vector Code Generation for the Discrete Fourier Transform
    Proc. International Parallel and Distributed Processing Symposium (IPDPS), 2003
50. Aca Gacic, Markus Püschel and José M. F. Moura
    Fast Automatic Implementations of FIR Filters
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2003, Vol. 2, pp. 541-544
51. Franz Franchetti and Markus Püschel
    Short Vector Code Generation and Adaptation for DSP Algorithms
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2003, Vol. 2, pp. 537-540
52. Markus Püschel, Sebastian Egner, and Thomas Beth
    AREP
    in "Computer Algebra Handbook, Foundations, Applications, Systems", Eds. J. Grabmeier, E. Kaltofen, V. Weispfenning, Springer 2003, pp. 461-462
    
    2002
53. Franz Franchetti and Markus Püschel
    A SIMD Vectorizing Compiler for Digital Signal Processing Algorithms
    Proc. International Parallel and Distributed Processing Symposium (IPDPS), 2002, pp. 20-26
54. Markus Püschel
    Decomposing Monomial Representations of Solvable Groups
    Journal of Symbolic Computation 2002, Vol. 34, No. 6, pp. 561-596
55. Markus Püschel, Bryan Singer, Manuela Veloso and José M. F. Moura
    Fast Automatic Generation of DSP Algorithms
    Proc. International Conference on Computational Science (ICCS), Lecture Notes In Computer Science, Springer, 2001, Vol. 2073, pp. 97-106
56. Sebastian Egner and Markus Püschel
    Automatic Generation of Fast Discrete Signal Transforms
    IEEE Transactions on Signal Processing 2001, Vol. 49, No. 9, pp. 1992-2002
    
    2001
57. Sebastian Egner, Jeremy Johnson, David Padua, Markus Püschel, and Jianxin Xiong
    Automatic Derivation and Implementation of Signal Processing Algorithms
    ACM SIGSAM Bulletin Communications in Computer Algebra 2001, Vol. 35, No. 2, pp. 1-19
    
    2000
58. Jeremy Johnson and Markus Püschel
    In Search of the Optimal Walsh-Hadamard Transform
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2000, Vol. 6, pp. 3347-3350
    
    1999
59. Martin Rötteler, Markus Püschel, and Thomas Beth
    Fast Signal Transforms for Quantum Computers
    Proc. of the Workshop on Physics and Computer Science, Heidelberg/Germany, 1999, Werner Kluge (Ed.), pp. 31-43
60. Markus Püschel, Martin Rötteler, and Thomas Beth
    Fast Quantum Fourier Transforms for a Class of Non-abelian Groups
    Proc. AAECC, LNCS 1719, Springer, 1999, pp. 148-159
    
    1998
61. Sebastian Egner and Markus Püschel
    Solving Puzzles related to Permutations Groups
    Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC) 1998, pp. 186-193
    
    1997
62. Sebastian Egner, Markus Püschel, and Thomas Beth
    Decomposing a Permutation into a Conjugated Tensor Product
    Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC) 1997, pp. 101-108

Editor

1. José Moura, Markus Püschel, David Padua, and Jack Dongarra (Eds.)
   Program Generation, Optimization, and Adaptation
   special issue of the Proceedings of the IEEE, Vol. 93, No. 2, 2005
2. Jeremy Johnson, José Moura, Markus Püschel, Dan Rockmore (Eds.)
   Computer Algebra and Signal Processing
   special issue of the Journal of Symbolic Computation Vol. 37, No. 2, 2004

Theses

1. Markus Püschel
   Signaltransformationen: Theorie, Algorithmen und Implementierung
   Habilitation thesis Applied Computer Science, University of Vienna, Austria 2005
2. Markus Püschel
   Konstruktive Darstellungstheorie und Algorithmengenerierung
   Ph.D. Thesis Computer Science, University of Karlsruhe, Germany 1998 (advisor Prof. Dr. T. Beth, 135 pages);
   also in English:
   Constructive Representation Theory and Fast Discrete Signal Transforms
   Technical Report Drexel-MCS-1999-1, Drexel University, Philadelphia, 1999 (141 pages)
3. Markus Püschel
   Über Gamma₀(n) und seinen Normalisator in den rationalen Fällen
   Diploma Thesis Mathematics, University of Karlsruhe, Germany 1994 (advisor Prof. Dr. H.-W. Leopoldt, 144 pages)
   

Other Conference Papers

1. (Best paper award) Yevgen Voronenko, Franz Franchetti, Frédéric de Mesmay and Markus Püschel
   Generating High-Performance General Size Linear Transform Libraries Using Spiral
   Proc. High Performance Embedded Computing (HPEC), 2008
2. Franz Franchetti, Daniel McFarlin, Frédéric de Mesmay, Hao Shen, Tomasz Wiktor Włodarczyk, Srinivas Chellappa, Marek Telgarsky, Peter A. Milder, Yevgen Voronenko, Qian Yu, James C. Hoe, José M. F. Moura and Markus Püschel
   Program Generation with Spiral: Beyond Transforms
   Proc. High Performance Embedded Computing (HPEC), 2008
3. Yevgen Voronenko, Franz Franchetti, Frédéric de Mesmay and Markus Püschel
   System Demonstration of Spiral: Generator for High-Performance Linear Transform Libraries
   Proc. Algebraic Methodology and Software Technology (AMAST), 2008
4. Srinivas Chellappa, Franz Franchetti and Markus Püschel
   FFT Program Generation for the Cell BE
   Proc. International Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA), 2008
5. Franz Franchetti, Yevgen Voronenko, Peter A. Milder, Srinivas Chellappa, Marek Telgarsky, Hao Shen, Paolo D'Alberto, Frédéric de Mesmay, James C. Hoe, José M. F. Moura and Markus Püschel
   Domain-Specific Library Generation for Parallel Software and Hardware Platforms
   Proc. NSF Next Generation Software Program Workshop (NSFNGS) colocated with IPDPS, 2008
6. Peter Milder, Franz Franchetti, James C. Hoe, and Markus Püschel
   Discrete Fourier Transform Compiler: From Mathematical Description to Efficient Hardware
   poster at FPGA 2007
7. Robert Kirby and Markus Püschel
   Program Generation for Polynomial Transforms in Unstructured Finite Element Computation
   workshop on Finite Element Methods in Engineering and Science (FEMTEC) 2006
8. F. Franchetti, A. Bonelli, E. Chuangsuwanich, Y. J. Lee, J. Lorenz, T. Peter, H. Shen, M. Telgarsky, Y. Voronenko, M. Püschel, J. M. F. Moura, C. W. Ueberhuber
   Parallelism in Spiral
   Proc.  Workshop on Programming Models for Ubiquitous Parallelism (PMUP), 2006
9. Paolo D'Alberto, Peter Milder, Franz Franchetti, James Hoe, Markus Püschel, and José Moura
   Discrete Fourier Transform Compiler for FPGA and CPU/FPGA Partitioned Implementations
   Proc. High Performance Embedded Computing (HPEC) 2006
10. Markus Püschel
    Algebraic Signal Processing Theory: An Overview
    Proc. 12th IEEE DSP Workshop 2006
11. Roland Wunderlich, Markus Püschel, and James C. Hoe
    Accelerating Blocked Matrix-Matrix Multiplication using a Software-Managed Memory Hierarchy with DMA
    Proc. High Performance Embedded Computing (HPEC) 2005
12. Lawrence C. Chang, Yevgen Voronenko, and Markus Püschel
    Adaptive Mapping of Linear DSP Algorithms to Fixed-Point Arithmetic
    Proc. High Performance Embedded Computing (HPEC) 2004
13. Grace Nordin, James C. Hoe, and Markus Püschel
    Discrete Fourier Transform IP Generator
    Proc. High Performance Embedded Computing (HPEC) 2004
14. Markus Püschel and Martin Rötteler
    Cooley-Tukey FFT Like Algorithm for the Discrete Triangle Transform
    Proc. 11th IEEE DSP Workshop 2004
15. José Moura and Markus Püschel
    SPIRAL: An Overview
    Proc. Workshop on Optimizations for DSP and Embedded Systems (ODES), held with International Symposium on Code Generation and Optimization (CGO), 2003
16. Aca Gacic, Markus Püschel, and José Moura
    High Performance Code Generation for FIR Filters and the Discrete Wavelet Transform Using SPIRAL
    Proc. High Performance Embedded Computing (HPEC) 2003, MIT Lincoln Laboratories
17. Smarahara Misra, Adam Zelinski, James Hoe, and Markus Püschel
    Custom Reduction of Arithmetic in Linear DSP Transforms
    Proc. High Performance Embedded Computing (HPEC) 2003, MIT Lincoln Laboratories
18. Markus Püschel and José Moura
    The Discrete Trigonometric Transforms and Their Fast Algorithms: An Algebraic Symmetry Perspective
    Proc. 10th IEEE Digital Signal Processing Workshop, 2002
19. Markus Püschel and José Moura
    Generation and Manipulation of DSP Transform Algorithms
    Proc. 10th IEEE Digital Signal Processing Workshop, 2002
20. Franz Franchetti, Markus Püschel, José Moura, and Christoph Überhuber
    Short Vector SIMD Code Generation for DSP Algorithms
    Proc. High Performance Embedded Computing (HPEC) 2002, MIT Lincoln Laboratories
21. Fang Fang, James C. Hoe, Markus Püschel, and Smarahara Misra
    Generation of Custom DSP Transform IP Cores: Case Study Walsh-Hadamard Transform
    Proc. High Performance Embedded Computing (HPEC) 2002, MIT Lincoln Laboratories
22. Markus Püschel
    SPIRAL: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms
    Proc. Workshop on Performance Optimization for High-Level Languages and Libraries (POHLL), held with International Conference on Supercomputing (ICS), 2002
23. José Moura, Jeremy Johnson, Robert W. Johnson, David Padua, Viktor Prasanna, Markus Püschel, Bryan Singer, Manuela Veloso, and Jianxin Xiong
    Generating Platform-Adapted DSP Libraries using SPIRAL
    Proc. High Performance Embedded Computing (HPEC) 2001, MIT Lincoln Laboratories
24. José Moura, Jeremy Johnson, Robert W. Johnson, David Padua, Viktor Prasanna, Markus Püschel, and Manuela Veloso
    SPIRAL: Automatic Implementation of Signal Processing Algorithms
    Proc. High Performance Embedded Computing (HPEC) 2000, MIT Lincoln Laboratories

Other Writing

1. Sebastian Egner and Markus Püschel
   AREP - a Package for Constructive Representation Theory and Fast Signal Transforms
   GAP share package and manual 1998 (99 pages)
2. Armin Nückel, Markus Püschel, and Volker Baumgarte
   Spezifikation und Simulation technologischer Prozesse - am Beispiel einer Zementmühle
   E.I.S.S.- Report 1998/2, University of Karlsruhe, 1998 (39 pages)
3. Armin Nückel, Markus Püschel, Volker Baumgarte, and Winfried Fakler
   VERMEIL - Verfahren und Methoden zur wissensbasierten Entwicklung zuverlässiger Leitanlagen
   BMBF-Projekt, 6 interim reports July 95 - July 98
   

descriptions and downloads

We present the discrete Fourier transform as a basic primitive in the treatment of controlled quantum systems. Based on the complexity model for quantum circuits the Fourier transform of size 2ⁿ surprisingly can be realised with O(n²) elementary operations which is an exponential speedup compared to the classical case. This is the reason for its presence in almost all known quantum algorithms among which Shor's algorithm for factoring is the most prominent example.

We show how recent results in the theory of signal processing (for a classical computer) can be applied to obtain fast quantum algorithms for various discrete signal transforms. As an example we derive a quantum circuit implementing the discrete cosine transform, type IV, of size 8x8 efficiently.

A short description of the GAP share package AREP for constructive representation theory and fast signal transforms.

An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2ⁿ first (where n is the number of qubits).

As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2ⁿ is O(n²) in all cases.

Many fast discrete signal transforms are given as a decomposition of the corresponding matrix into a product of sparse matrices. In this thesis an algorithm is presented which generates such decompositions automatically using methods of representation theory of finite groups.

Have a look at several examples of fast signal transforms automatically generated with the new methods.

• DCT, type 2 and 3
• DCT, type 4
• Hartley transform
• Haar transform
• Wreath Product Transform

In addition, well-known algorithms as the Cooley-Tukey FFT, or the Rader FFT can be derived as well. This reveals a strong relationship between discrete signal transforms and representation theory, opening a new area of research to explore the benefits of this connection.

The procedure for decomposing a transform/matrix has its roots in the thesis of Torsten Minkwitz and consists essentially of two steps. First, the symmetry of the matrix is determined, which is a pair of monomial representations under which the matrix is invariant. Second, the representations are decomposed stepwise, giving rise to factorized decomposition matrices which determine the factorization of the matrix. Intuitively speaking, the symmetry catches redundancy contained in the matrix and the decomposition of the representations turns the redundancy into a factorization of the matrix. Computation of symmetry has been treated in the PhD Thesis of Sebastian Egner. The main contribution of my thesis is an algorithm for the decomposition of a large class of monomial representations including the computation of a factorized decomposition matrix. To solve this problem, a constructive approach to representation theory is developed where representations are considered up to equality instead of equivalence. In this sense, refinements of well-known theorems (e.g. Mackey's Subgroup Theorem, Clifford's Theorem) are developed and applied to the special cases of permutation and monomial representations. Formulas are derived allowing the explicit construction of decomposition matrices for monomial representations in many cases.

AREP, a GAP share package for constructive representation theory, has been created in collaboration with Sebastian Egner and used to implement all algorithms contained in this thesis. Using AREP it was possible to generate fast algorithms for many signal transforms including the Fourier transform, trigonometric transforms, Hartley transform, and Haar transform (see above).

The problem of decomposing a single permutation into a conjugated tensor product of smaller permutations is solved. In general the decomposition is not uniquely determined. An algorithm is presented which enumerates all solutions. In particular it is possible to decide considerably fast if a permutation is tensor-indecomposable.