Group Representations and Automatic Generation of Fast Algorithms for Discrete Signal Transforms

离散信号变换的群表示和快速算法的自动生成

• 批准号: 9988296
• 负责人: Jose Moura
• 金额: $ 28.7万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988296&HistoricalAwards=false
• 关键词: Group; Representations; Automatic; Generation; Fast

Proposal SummaryIn this research, we propose to use group representation theory to generate automatically fastalgorithms for digital signal processing (DSP) transforms. Group representation theory provides adeeper understanding of the structure of signal transforms and a context to address fundamentalquestions in modeling and processing of signals. We propose to use representation theory to designnew transforms with desirable characteristics.Our work is at the meta-level of DSP algorithm libraries (DSP-AL), like SPIRAL, [23]. SPI-RAL is a library of DSP algorithms that concatenates a formula generator block with a codegenerator block to produce optimized software implementations for a given computer. SPIRALapplies iteratively fast algorithms, the algorithmic rules, to generate a rich collection of alternativeequivalent formulas (the formula space) for the same DSP algorithm. For each formula, SPIRALthen produces automatically optimized code that runs efficiently on the given computer. Bysearching over the formula space, SPIRAL generates automatically the formula and correspond-ing code implementation that matches in an optimized sense the algorithm to the hardware.What SPIRAL, or any other existing DSP-AL for that matter, does NOT do is the automaticgeneration of the fast algorithm, or algorithmic rules. This meta-level is the focus of our proposedresearch. We exploit group representation theory to develop the theoretical framework and thetools that produce automatically these fast algorithms for a number of DSP transforms. We willimplement and interface these tools to a DSP-AL (SPIRAL) which will enable us to translatedirectly a fast DSP algorithm as generated by our tools to an efficient low-level language program.Generating a fast discrete signal transform, given as a matrix, consists of two steps: determin-ing the "symmetry" of the transform, which is a pair of representations under which the transformis invariant; decomposing stepwise the representations, giving rise to factorized decomposition ma-trices, which determine the factorization of the transform. The symmetry catches redundancy inthe transform, and the decomposition of the representations turns the redundancy into a factoriza-tion of the transform - the fast algorithm. To realize this program, new results on decompositionmatrices will be derived in the context of a constructive extension of standard representationtheory, where representations are manipulated up to equality, not only up to equivalence.We will implement the algorithm for generating fast discrete signal transforms within a packagefor symbolic computation with group representations and structured matrices and interface it witha DSP-AL, namely SPIRAL.We consider different types of "symmetry," going beyond regular representations to includearbitrary permutation and monomial representations, in order to capture in the representationframework a wide class of signal transforms. Besides the DFT, and trigonometric transforms, wewill consider other transforms including wavelet transforms.We use the group representation framework to explore the connection between the "symmetry"of a signal transform and its properties with respect to signal processing. The use of a transformcan be justified on the basis of the model underlying the data. We have shown this relation to beconnected to the boundary conditions (b.c.) assumed in describing a certain class of models widelyused in applications. These b.c.'s also reflect the type of "data extension" that is hypothesized,for example, cyclic b.c.'s versus signal periodic extension versus the discrete Fourier transform.This proposal will exploit the relations between the "symmetry" of the representation, the signaltransform, and the signal models, enabling us to address some fundamental questions, namelyhow to design a signal transform which is adapted to a given signal model (i.e., reflects a desiredsymmetry) and is computationally the most efficient.

提案总结本研究，我们建议使用小组表示理论来生成用于数字信号处理（DSP）变换的自动封装。小组表示理论提供了对信号转换结构的理解以及解决信号建模和处理中基本问题的上下文。我们建议使用表示理论来设计具有理想特征的DesignNew变换。我们的工作是在DSP算法库（DSP-AL）的元级，例如螺旋形，[23]。 Spi-ral是DSP算法的库，它将公式发电机块与代码Generator块连接在一起，以为给定计算机生成优化的软件实现。 SpiralApplies迭代快速算法，即算法规则，以生成相同DSP算法的丰富的替代等效公式（公式空间）。对于每个公式，Spiralthen生成自动优化的代码，该代码在给定的计算机上有效运行。在公式空间上进行搜索，Spiral会自动生成公式和相应的代码实现，以优化的意义匹配算法与硬件的算法。螺旋形成的或任何其他现有的DSP-AL都不是，这是快速算法的自动化，或者是Algorithmic规则的自动化。这个元级是我们提议的研究的重点。我们利用群体表示理论来开发理论框架，并为许多DSP变换而自动产生这些快速算法。 We willimplement and interface these tools to a DSP-AL (SPIRAL) which will enable us to translatedirectly a fast DSP algorithm as generated by our tools to an efficient low-level language program.Generating a fast discrete signal transform, given as a matrix, consists of two steps: determin-ing the "symmetry" of the transform, which is a pair of representations under which the transformis invariant;分解逐步表示表示，从而导致分解分解的MA-Trices，从而确定转换的分解。对称性捕获了转换中的冗余，并且表示形式的分解将冗余变成转换的因素 - 快速算法。要实现该程序，将在标准表示理论的建设性扩展的上下文中得出有关分解的新结果，在该上下文中，将表示形式被操纵至平等，不仅达到等效性，我们将实现算法，以在包装中生成快速离散信号转换的算法，这些算法在包装中，与组成型和结构的矩阵和结构型型型号相互互动，并与n nam interface Ita anda dya dya deperfe nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam nam toble。 “对称”超越了定期表示，包括核心置换和单次表示，以便在表示框架中捕获广泛的信号变换。除了DFT和三角变换外，我们将考虑包括小波变换在内的其他变换。我们使用组表示框架来探索信号变换的“对称性”与信号处理相对于信号处理的属性之间的连接。根据数据的基础模型，使用转换的使用是合理的。我们已经证明了与边界条件（B.C.）相关的关系，在描述应用程序中广泛使用的一类模型时。 These b.c.'s also reflect the type of "data extension" that is hypothesized,for example, cyclic b.c.'s versus signal periodic extension versus the discrete Fourier transform.This proposal will exploit the relations between the "symmetry" of the representation, the signaltransform, and the signal models, enabling us to address some fundamental questions, namelyhow to design a signal transform which is adapted to a given signal model (i.e.,反映了构成对称性），并且在计算上是最有效的。