publications
 Markus Püschel
Professor
Associate Department Head
Computer Science
ETH Zürich
Switzerland

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. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    Distributed Optimization With Local Domains: Applications in MPC and Network Flows
    submitted for publication
  2. Marcela Zuluaga, Andreas Krause, Guillaume Sergent and Markus Püschel 
    Active Learning for Multi-Objective Optimization 
    to appear in Proc. International Conference on Machine Learning (ICML), 2013

Journal/Book Chapters/Conference Papers (Fully Reviewed)

  1. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
    IEEE Transactions on Signal Processing, Vol. 61, No. 10, pp. 2718-2723, 2013

    2012
  2. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    ADMM For Consensus On Colored Networks
    Proc. IEEE Conference on Decision and Control (CDC), 2012
  3. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    Distributed ADMM for Model Predictive Control and Congestion Control
    Proc. IEEE Conference on Decision and Control (CDC), 2012
  4. (Best paper award nominee, among 3 out of 18) Marcela Zuluaga, Andreas Krause, Peter A. Milder and Markus Püschel 
    "Smart" Design Space Sampling to Predict Pareto-Optimal Solutions 
    Proc. Languages, Compilers, Tools and Theory for Embedded Systems (LCTES), pp. 119-128 , 2012
  5. Marcela Zuluaga, Peter A. Milder and Markus Püschel 
    Computer Generation of Streaming Sorting Networks 
    Proc. Design Automation Conference (DAC), pp. 1245-1253, 2012
  6. Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel 
    Algebraic Signal Processing Theory: 1-D Nearest-Neighbor Models 
    IEEE Transactions on Signal Processing, Vol. 60, No. 5, pp. 2247-2259, 2012
  7. Robert Koutsoyannis, Peter A. Milder, Christian Berger, Madeleine Glick, James C. Hoe and Markus Püschel
    Improving Fixed-Point Accuracy of FFT Cores in O-OFDM Systems
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2012
  8. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    D-ADMM: A Distributed Algorithm for Compressed Sensing and Other Separable Optimization Problems
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2012
  9. Peter A. Milder, Franz Franchetti, James C. Hoe and Markus Püschel 
    Computer Generation of Hardware for Linear Digital Signal Processing Transforms 
    ACM Transactions on Design Automation of Electronic Systems, Vol. 17, No. 2, 2012
  10. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    Distributed Basis Pursuit (website)
    IEEE Transactions on Signal Processing, Vol. 60, No. 4, pp. 1942-1956, 2012
  11. Aliaksei Sandryhaila, Samir Saba, Markus Püschel and Jelena Kovacevic
    Efficient compression of QRS complexes using Hermite expansion
    IEEE Transactions on Signal Processing, Vol. 60, No. 2, pp. 947-955, 2012

    2011
  12. Rachid Bouziane, Peter A. Milder, Robert Koutsoyannis, Yannis Benlachtar, James C. Hoe, Markus Püschel, Madeleine Glick and Robert I. Killey
    Design studies for ASIC implementations of 28 GS/s optical QPSK- and 16-QAM-OFDM transceivers
    Optics Express, Vol. 19, No. 21, pp. 20857-20864, 2011
  13. Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel
    Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Polynomial Transforms Based on Induction
    SIAM Journal on Matrix Analysis and Applications, Vol. 32, No. 2, pp. 364-384, 2011
  14. Franz Franchetti and Markus Püschel
    Fast Fourier Transform
    in Encyclopedia of Parallel Computing, Eds. David Padua, Springer 2011
  15. Markus Püschel, Franz Franchetti and Yevgen Voronenko
    Spiral
    in Encyclopedia of Parallel Computing, Eds. David Padua, Springer 2011
  16. Daniel McFarlin, Volodymyr Arbatov, Franz Franchetti and Markus Püschel
    Automatic SIMD Vectorization of Fast Fourier Transforms for the Larrabee and AVX Instruction Sets
    Proc. International Conference on Supercomputing (ICS), 2011
  17. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    Basis Pursuit in Sensor Networks
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 2916-2919, 2011
  18. Aliaksei Sandryhaila, Jelena Kovacevic and Markus Püschel
    Compression of QRS Complexes Using Hermite Expansion
    Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 581-584, 2011
  19. Christian Berger, Volodymyr Arbatov, Yevgen Voronenko, Franz Franchetti and Markus Püschel
    Real-Time Software Implementation of an IEEE 802.11a Baseband Receiver on Intel Multicore
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 1693-1696, 2011

    2010
  20. Yannis Benlachtar, Rachid Bouziane, Robert I. Killey, Christian Berger, Peter A. Milder, Robert Koutsoyannis, James C. Hoe, Markus Püschel and Madeleine Glick
    Optical OFDM for the Data Center
    Proc. International Conference on Transparent Optical Networks (ICTON), pp. 1-4, 2010
  21. Yevgen Voronenko, Volodymyr Arbatov, Christian Berger, Ronghui Peng, Markus Püschel and Franz Franchetti
    Computer Generation of Platform-Adapted Physical Layer Software
    to appear in Proc. Software Defined Radio (SDR), 2010
  22. Rachid Bouziane, Peter A. Milder, Robert Koutsoyannis, Yannis Benlachtar, Christian Berger, James C. Hoe, Markus Püschel, Madeleine Glick and Robert I. Killey
    Design Studies for an ASIC Implementation of an Optical OFDM Transceiver
    Proc. European Conference on Optical Communication (ECOC), pp. 1-3, 2010
  23. Yannis Benlachtar, Philip M. Watts, Rachid Bouziane, Peter A. Milder, Robert Koutsoyannis, James C. Hoe, Markus Püschel, Madeleine Glick and Robert I. Killey
    Real-Time Digital Signal Processing for the Generation of Optical Orthogonal Frequency Division Multiplexed Signals
    IEEE Journal of Selected Topics in Quantum Electronics, Vol. 16, No. 5, pp. 1235-1244 , 2010
  24. Aliaksei Sandryhaila, Amina Chebira, Christina Milo, Jelena Kovacevic and Markus Püschel
    Systematic Construction of Real Lapped Tight Frame Transforms
    IEEE Transactions on Signal Processing, Vol. 58, No. 5, pp. 2556-2567, 2010
  25. Frédéric de Mesmay, Yevgen Voronenko and Markus Püschel
    Offline Library Adaptation Using Automatically Generated Heuristics
    Proc. International Parallel and Distributed Processing Symposium (IPDPS), 2010
  26. Peter A. Milder, Franz Franchetti, James C. Hoe and Markus Püschel
    Hardware Implementation of the Discrete Fourier Transform with Non-Power-of-Two Problem Size
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2010
  27. Frédéric de Mesmay, Srinivas Chellappa, Franz Franchetti and Markus Püschel
    Computer Generation of Efficient Software Viterbi Decoders
    Proc. International Conference on High Performance Embedded Architectures and Compilers (HiPEAC), Lecture Notes in Computer Science, Springer, Vol. 5952, pp. 353-368, 2010
  28. Jelena Kovacevic and Markus Püschel
    Algebraic Signal Processing Theory: Sampling for Infinite and Finite 1-D Space
    IEEE Transactions on Signal Processing, Vol. 58, No. 1, 2010

    2009
  29. Franz Franchetti, Markus Püschel, Yevgen Voronenko, Srinivas Chellappa and José M. F. Moura
    Discrete Fourier Transform on Multicore
    IEEE Signal Processing Magazine, special issue on "Signal Processing on Platforms with Multiple Cores'', Vol. 26, No. 6, pp. 90-102, 2009
  30. Yannis Benlachtar, Philip M. Watts, Rachid Bouziane, Peter A. Milder, Deepak Rangaraj, Anthony Cartolano, Robert Koutsoyannis, James C. Hoe, Markus Püschel, Madeleine Glick and Robert I. Killey
    Generation of Optical OFDM Signals Using 21.4 GS/s Real Time Digital Signal Processing
    Optics Express, Vol. 17, No. 20, pp. 17658-17668, 2009
  31. Aliaksei Sandryhaila, Amina Chebira, Markus Püschel and Jelena Kovacevic
    A New Class of Seeded Real Lapped Tight Frame Transforms
    Proc. SPIE Conf. on Wavelet Applications in Signal and Image Processing, Vol. 7446, pp. 74460M-74460M-8, 2009
  32. Basilio B. Fraguela, Yevgen Voronenko and Markus Püschel
    Automatic Tuning of Discrete Fourier Transforms Driven by Analytical Modeling
    Proc. Parallel Architectures and Compilation Techniques (PACT), pp. 271-280, 2009
  33. (Best paper award, 3 out of 18) Franz Franchetti, Frédéric de Mesmay, Daniel McFarlin and Markus Püschel
    Operator Language: A Program Generation Framework for Fast Kernels
    Proc. IFIP Working Conference on Domain Specific Languages (DSL WC), Lecture Notes in Computer Science, Springer, Vol. 5658, pp. 385-410, 2009
  34. Frédéric de Mesmay, Arpad Rimmel, Yevgen Voronenko and Markus Püschel
    Bandit-Based Optimization on Graphs with Application to Library Performance Tuning
    Proc. International Conference on Machine Learning (ICML), pp. 729-736, 2009
  35. Srinivas Chellappa, Franz Franchetti and Markus Püschel
    Computer Generation of Fast Fourier Transforms for the Cell Broadband Engine
    Proc. International Conference on Supercomputing (ICS), pp. 26-35, 2009
  36. Peter A. Milder, James C. Hoe and Markus Püschel
    Automatic Generation of Streaming Datapaths for Arbitrary Fixed Permutations
    Proc. Design, Automation and Test in Europe (DATE), pp. 1118-1123, 2009
  37. Yevgen Voronenko, Frédéric de Mesmay and Markus Püschel
    Computer Generation of General Size Linear Transform Libraries
    Proc. International Symposium on Code Generation and Optimization (CGO), pp. 102-113, 2009
  38. Daniel McFarlin, Franz Franchetti, José M. F. Moura and Markus Püschel
    High Performance Synthetic Aperture Radar Image Formation On Commodity Architectures
    Proc. SPIE Conference on Defense, Security, and Sensing, Proceedings of SPIE, Vol. 7337, pp. 733708, 2009
  39. Franz Franchetti and Markus Püschel
    Generating High-Performance Pruned FFT Implementations
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 549-552, 2009
  40. Markus Püschel, Peter A. Milder and James C. Hoe
    Permuting Streaming Data Using RAMs
    Journal of the ACM, Vol. 56, No. 2, pp. 10:1-10:34, 2009
  41. Yevgen Voronenko and Markus Püschel
    Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Real DFTs
    IEEE Transactions on Signal Processing, Vol. 57, No. 1, 2009

    2008
  42. 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
  43. Markus Püschel
    DFT and FFT: An Algebraic View
    in Fast Fourier Transforms, Eds. C. Sidney Burrus, Connexions 2008
  44. 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
  45. 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
  46. 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
  47. 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
  48. 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
  49. (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), pp. 385-390, 2008
  50. 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
  51. 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
  52. 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
  53. 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
  54. 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
  55. 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
  56. Yevgen Voronenko and Markus Püschel
    Multiplierless Multiple Constant Multiplication
    ACM Transactions on Algorithms, Vol. 3, No. 2, 2007
  57. 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
  58. 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
  59. Paolo D'Alberto, Peter A. Milder, Aliaksei Sandryhaila, Franz Franchetti, James C. Hoe, José M. F. Moura, Markus Püschel and Jeremy Johnson
    Generating FPGA Accelerated DFT Libraries
    Proc. IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), pp. 173-184, 2007
  60. 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), Lecture Notes in Computer Science, Springer, Vol. 4367, pp. 201-214, 2007

    2006
  61. (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
  62. Franz Franchetti, Yevgen Voronenko and Markus Püschel
    FFT Program Generation for Shared Memory: SMP and Multicore
    Proc. Supercomputing (SC), 2006
  63. 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
  64. 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
  65. 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
  66. 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
  67. 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
  68. 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
  69. 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
  70. 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
  71. 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
  72. Markus Püschel and Jelena Kovacevic
    Real, Tight Frames Maximally Robust To Erasures
    Proc. Data Compression Conference (DCC), pp. 63-72, 2005
  73. 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
  74. 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
  75. 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
  76. 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
  77. 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
  78. 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
  79. 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
  80. Markus Püschel and Martin Rötteler
    The Discrete Triangle Transform
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2004
  81. 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
  82. 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
  83. 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
  84. 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
  85. 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
  86. 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
  87. (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
  88. 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
  89. 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
  90. Franz Franchetti and Markus Püschel
    Short Vector Code Generation for the Discrete Fourier Transform
    Proc. International Parallel and Distributed Processing Symposium (IPDPS), 2003
  91. 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
  92. 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
  93. 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
  94. 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
  95. Markus Püschel
    Decomposing Monomial Representations of Solvable Groups
    Journal of Symbolic Computation 2002, Vol. 34, No. 6, pp. 561-596
  96. 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
  97. 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
  98. 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
  99. 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
  100. 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
  101. 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
  102. 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
  103. 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 Gamma0(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. Yannis Benlachtar, Philip M. Watts, Rachid Bouziane, Peter A. Milder, Robert Koutsoyannis, James C. Hoe, Markus Püschel, Madeleine Glick and Robert I. Killey
    21.4 GS/s Real-Time DSP-Based Optical OFDM Signal Generation and Transmission Over 1600 km of Uncompensated Fibre
    Proc. European Conference on Optical Communication (ECOC), 2009
  2. (Best paper award, 1 out of about 80) Daniel McFarlin, Franz Franchetti and Markus Püschel
    Automatic Generation of Vectorized Fast Fourier Transform Libraries for the Larrabee and AVX Instruction Set Extension
    Proc. High Performance Embedded Computing (HPEC), 2009
  3. Srinivas Chellappa, Franz Franchetti and Markus Püschel
    High Performance Linear Transform Program Generation for the Cell BE
    Proc. High Performance Embedded Computing (HPEC), 2009
  4. Joao Mota, Joao Xavier, Pedro Aguiar, and Markus Püschel
    Distributed Algorithms for Basis Pursuit
    Proc. Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS), 2009
  5. (Best paper award, 1 out of about 80) 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. Markus Püschel
    Algebraic Signal Processing Theory: An Overview
    Proc. 12th IEEE DSP Workshop 2006
  15. 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
  16. 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
  17. Grace Nordin, James C. Hoe, and Markus Püschel
    Discrete Fourier Transform IP Generator
    Proc. High Performance Embedded Computing (HPEC) 2004
  18. Markus Püschel and Martin Rötteler
    Cooley-Tukey FFT Like Algorithm for the Discrete Triangle Transform
    Proc. 11th IEEE DSP Workshop 2004
  19. 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
  20. 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
  21. 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
  22. 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
  23. Markus Püschel and José Moura
    Generation and Manipulation of DSP Transform Algorithms
    Proc. 10th IEEE Digital Signal Processing Workshop, 2002
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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

Copyrights to the many of the following papers are held by the publishers. The attached Postscript files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Markus Püschel (Technical Report Drexel-MCS-1999-1, Drexel University, Philadelphia, 1999, 141 pp.)
Constructive Representation Theory and Fast Discrete Signal Transforms
A translation of my thesis to English.
Martin Rötteler, Markus Püschel, and Thomas Beth (Proc. of the Workshop on Physics and Computer Science, Heidelberg/Germany, 1999, Werner Kluge (Ed.), pp. 31-43)
Fast Signal Transforms for Quantum Computers
qsignal.ps (436 KB)

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 2n surprisingly can be realised with O(n2) 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.

Markus Püschel, Sebastian Egner, and Thomas Beth (in New Reference Book on Computer Algebra, Eds. J.Grabmeier, E.Kaltofen, V.Weispfenning, Springer 2002)
AREP

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

Markus Püschel, Martin Rötteler, and Thomas Beth (Proc. AAECC 1999, LNCS 1719, Springer, pp. 148-159)
Fast Quantum Fourier Transforms for a Class of Non-abelian Groups
qfft.ps (224 KB)

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 2n 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 2n is O(n2) in all cases.

Markus Püschel (PhD Thesis Computer Science 1998, ref.: Prof. Dr. T. Beth, Prof. Dr. H.-W. Leopoldt, 135 pp.)
Konstruktive Darstellungstheorie und Algorithmengenerierung
(Constructive Representation Theory and Generation of Algorithms)
full text online (German)
diss.ps (804 KB, German)
thesis.ps (946 KB, English)

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.

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).

Sebastian Egner, Markus Püschel, and Thomas Beth (Proc. ISSAC 97, pp. 101-108)
Decomposing a Permutation into a Conjugated Tensor Product
perm.ps (257 KB)

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.