publications
Markus Püschel
Professor
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. Gagandeep Singh, Martin Vechev and Markus Püschel
    Fast Pentagon Domain on Vector Architectures
    submitted for publication
  2. Gagandeep Singh, Martin Vechev and Markus Püschel
    Fast Polyhedra Abstract Domain
    to appear in Principles of Programming Languages (POPL), 2017

Journal/Book Chapters/Conference Papers (Fully Reviewed)

  1. Georg Ofenbeck, Tiark Rompf, Markus Püschel

    RandIR: Differential Testing for Embedded Compilers
    Proc. Scala Symposium, pp. 21-30, 2016

  2. Marcela Zuluaga, Andreas Krause and Markus Püschel 
    e-PAL: An Active Learning Approach to the Multi-Objective Optimization Problem 
    Journal of Machine Learning Research (JMLR), Vol. 17, No. 104, pp. 1-32, 2016

  3. Francois Serre and Markus Püschel
    Generalizing Block LU Factorization: A Lower-Upper-Lower Block Triangular Decomposition with Minimal Off-Diagonal Ranks
    Linear Algebra and its Applications (LAA), Vol. 509, pp. 114-142
  4. Marcela Zuluaga, Peter A. Milder, and Markus Püschel 
    Streaming Sorting Networks 
    ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol. 21, No. 4, 2016
  5. Daniele G. Spampinato and Markus Püschel
    A Basic Linear Algebra Compiler for Structured Matrices 
    Proc. International Symposium on Code Generation and Optimization (CGO), pp. 117-127, 2016
  6. Francois Serre and Markus Püschel
    Optimal Circuits for Streamed Linear Permutations using RAM
    International Symposium on Field-Programmable Gate Arrays (FPGA), pp. 215-223, 2016

    2015
  7. Gagandeep Singh, Martin Vechev and Markus Püschel
    Making Numerical Program Analysis Fast
    Proc. Programming Languages Design and Implementation (PLDI), pp. 303-313, 2015
  8. Tiark Rompf, Kevin Brown, HyoukJoong Lee, Arvind Sujeeth, Manohar Jonnalagedda, Nada Amin, Georg Ofenbeck, Alen Stojanov, Yannis Klonatos, Mohammad Dashti, Christoph Koch, Markus Püschel, Kunle Olukotun
    Go Meta! A Case for generative programming and DSLs in Performance-critical Systems
    SNAPL: The Inaugural Summit on Advances in Programming Languages, 2015
  9. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    Distributed Optimization With Local Domains: Applications in MPC and Network Flows
    IEEE Transactions on Automated Control, Vol. 60, No. 7, pp. 2004-2009, 2015
  10. Nikolaos Kyrtatas, Daniele G. Spampinato and Markus Püschel 
    A Basic Linear Algebra Compiler for Embedded Processors 
    Proc. Design, Automation and Test in Europe (DATE), pp. 1054-1059, 2015

    2014
  11. Benjamin Hess, Thomas Gross and Markus Püschel
    Automatic Locality-Friendly Interface Extension of Numerical Functions
    Proc. International Conference on Generative Programming: Concepts & Experiences (GPCE), 2014
  12. Victoria Caparrós Cabezas and Markus Püschel
    Performance Bottleneck Modeling: Analyzing DAGs With Microarchitectural Constraints
    Proc. IEEE International Symposium on Workload Characterization (IISWC), 2014
  13. Jörn Schumacher and Markus Püschel 
    High-performance sparse fast Fourier transforms 
    Proc. IEEE Workshop on Signal Processing Systems (SIPS), pp. 1-6, 2014
  14. Alen Stojanov, Georg Ofenbeck, Tiark Rompf and Markus Püschel
    Abstracting Vector Architectures in Library Generators: Case Study Convolution Filters
    Proc. ACM International Workshop on Libraries, Languages and Compilers for Array Programming (ARRAY), pp. 14, 2014
  15. (Best paper award nominee, among 4 out of 29) Daniele G. Spampinato and Markus Püschel 
    A Basic Linear Algebra Compiler 
    Proc. International Symposium on Code Generation and Optimization (CGO), pp. 23-32, 2014
  16. Georg Ofenbeck, Ruedi Steinmann, Victoria Caparrós Cabezas, Daniele G. Spampinato and Markus Püschel 
    Applying the Roofline Model 
    Proc. IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pp. 76-85, 2014

    2013
  17. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    A Unified Algorithmic Approach to Distributed Optimization
    Proc. GlobalSIP, pp. 607-610, 2013
  18. Georg Ofenbeck, Tiark Rompf, Alen Stojanov, Martin Odersky and Markus Püschel 
    Spiral in Scala: Towards the Systematic Construction of Generators for Performance Libraries 
    Proc. International Conference on Generative Programming: Concepts & Experiences (GPCE), 2013
  19. Marcela Zuluaga, Andreas Krause, Guillaume Sergent and Markus Püschel 
    Active Learning for Multi-Objective Optimization 
    Proc. International Conference on Machine Learning (ICML), 2013
  20. 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
  21. 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), pp. 5116-5121, 2012
  22. 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), pp. 5110-5115, 2012
  23. (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
  24. Marcela Zuluaga, Peter A. Milder and Markus Püschel 
    Computer Generation of Streaming Sorting Networks 
    Proc. Design Automation Conference (DAC), pp. 1245-1253, 2012
  25. 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
  26. 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), pp. 1585-1588, 2012
  27. 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), pp. 2869-2872, 2012
  28. (ACM TODAES best paper award, 1 out of 51) 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 (TODAES), Vol. 17, No. 2, 2012
  29. (IEEE Signal Processing Society young author best paper award) 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
  30. 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
  31. 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
  32. 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
  33. Franz Franchetti and Markus Püschel
    Fast Fourier Transform
    in Encyclopedia of Parallel Computing, Eds. David Padua, Springer 2011
  34. Markus Püschel, Franz Franchetti and Yevgen Voronenko
    Spiral
    in Encyclopedia of Parallel Computing, Eds. David Padua, Springer 2011
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. Yevgen Voronenko, Volodymyr Arbatov, Christian Berger, Ronghui Peng, Markus Püschel and Franz Franchetti
    Computer Generation of Platform-Adapted Physical Layer Software
    Proc. Software Defined Radio (SDR), 2010
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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
  50. 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
  51. 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
  52. (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
  53. 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
  54. 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
  55. 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
  56. 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
  57. 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
  58. 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
  59. 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
  60. 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
  61. 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
  62. Markus Püschel
    DFT and FFT: An Algebraic View
    in Fast Fourier Transforms, Eds. C. Sidney Burrus, Connexions 2008
  63. 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
  64. 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
  65. 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
  66. 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
  67. 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
  68. (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
  69. 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
  70. 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
  71. 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
  72. 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
  73. 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
  74. 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
  75. Yevgen Voronenko and Markus Püschel
    Multiplierless Multiple Constant Multiplication
    ACM Transactions on Algorithms, Vol. 3, No. 2, 2007
  76. 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
  77. 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
  78. 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
  79. 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
  80. (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
  81. Franz Franchetti, Yevgen Voronenko and Markus Püschel
    FFT Program Generation for Shared Memory: SMP and Multicore
    Proc. Supercomputing (SC), 2006
  82. 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
  83. 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
  84. 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
  85. 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
  86. 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
  87. 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
  88. 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
  89. 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
  90. 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
  91. Markus Püschel and Jelena Kovacevic
    Real, Tight Frames Maximally Robust To Erasures
    Proc. Data Compression Conference (DCC), pp. 63-72, 2005
  92. 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
  93. 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
  94. 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
  95. 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
  96. 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
  97. 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
  98. 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
  99. Markus Püschel and Martin Rötteler
    The Discrete Triangle Transform
    Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2004
  100. 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
  101. 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
  102. 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
  103. 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
  104. 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
  105. 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
  106. (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
  107. 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
  108. 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
  109. Franz Franchetti and Markus Püschel
    Short Vector Code Generation for the Discrete Fourier Transform
    Proc. International Parallel and Distributed Processing Symposium (IPDPS), 2003
  110. 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
  111. 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
  112. 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
  113. 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
  114. Markus Püschel
    Decomposing Monomial Representations of Solvable Groups
    Journal of Symbolic Computation 2002, Vol. 34, No. 6, pp. 561-596
  115. 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
  116. 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
  117. 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
  118. 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
  119. 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
  120. 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
  121. 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
  122. 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. João Mota, João Xavier, Pedro Q. Aguiar and Markus Püschel
    Distributed Compressed Sensing Algorithms: Completing the Puzzle
    Proc. GlobalSIP, 2013
  2. 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
  3. (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
  4. 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
  5. 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
  6. (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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. Markus Püschel
    Algebraic Signal Processing Theory: An Overview
    Proc. 12th IEEE DSP Workshop 2006
  16. 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
  17. 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
  18. Grace Nordin, James C. Hoe, and Markus Püschel
    Discrete Fourier Transform IP Generator
    Proc. High Performance Embedded Computing (HPEC) 2004
  19. Markus Püschel and Martin Rötteler
    Cooley-Tukey FFT Like Algorithm for the Discrete Triangle Transform
    Proc. 11th IEEE DSP Workshop 2004
  20. 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
  21. 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
  22. 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
  23. 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
  24. Markus Püschel and José Moura
    Generation and Manipulation of DSP Transform Algorithms
    Proc. 10th IEEE Digital Signal Processing Workshop, 2002
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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.