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）变换算法。群表示理论提供了对信号变换结构的更深层次的理解，并提供了一个背景，以解决信号建模和处理中的基本问题。我们提出利用表征理论来设计具有理想特性的新变换。我们的工作是在DSP算法库（DSP- al）的元级，如SPIRAL，[23]。SPI-RAL是一个DSP算法库，它将公式生成器块与代码生成器块连接起来，为给定的计算机生成优化的软件实现。spiral应用迭代快速算法，即算法规则，为相同的DSP算法生成丰富的替代等效公式（公式空间）集合。对于每个公式，SPIRALthen会自动生成在给定计算机上有效运行的优化代码。通过搜索公式空间，SPIRAL自动生成公式和相应的代码实现，以优化算法与硬件相匹配。什么螺旋，或任何其他现有的DSP-AL为那件事，不做的是快速算法或算法规则的自动生成。这个元层次是我们建议研究的重点。我们利用群表示理论来开发理论框架和工具，为许多DSP变换自动生成这些快速算法。我们将实现这些工具并将其接口到DSP- al（螺旋），这将使我们能够将我们的工具生成的快速DSP算法直接翻译为高效的低级语言程序。生成一个快速的离散信号变换，以矩阵形式给出，由两步组成：确定变换的“对称性”，即变换不变的一对表示；逐步分解表示，得到分解矩阵，它决定了变换的分解。对称性捕获了变换中的冗余，表示的分解将冗余转化为变换的因式分解——快速算法。为了实现这个程序，分解矩阵的新结果将在标准表示理论的建设性扩展的背景下得到，其中表示被操纵到相等，而不仅仅是等价。我们将实现在一个包内生成快速离散信号变换的算法，该算法用于使用群表示和结构化矩阵进行符号计算，并将其与DSP-AL（即SPIRAL）接口。我们考虑不同类型的“对称性”，超越正则表示，包括任意排列和单项式表示，以便在表示框架中捕获广泛类别的信号变换。除了DFT和三角变换外，我们还将考虑包括小波变换在内的其他变换。我们使用群表示框架来探索信号变换的“对称性”与其在信号处理方面的性质之间的联系。可以根据数据背后的模型来证明转换的使用是合理的。在描述应用中广泛使用的某类模型时，我们已经证明了这种关系与假定的边界条件（b.c）有关。这些公元前。也反映了假设的“数据扩展”类型，例如，公元前循环信号周期扩展和离散傅里叶变换。本提案将利用表征，信号变换和信号模型的“对称性”之间的关系，使我们能够解决一些基本问题，即如何设计适应给定信号模型的信号变换（即，反映所需的对称性）并且在计算上最有效。