| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 28, 2000 |
| Latest Amendment Date: | September 25, 2002 |
| Award Number: | 9988296 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
John Cozzens
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2000 |
| End Date: | August 31, 2003 (Estimated) |
| Total Intended Award Amount: | $287,018.00 |
| Total Awarded Amount to Date: | $301,118.00 |
| Funds Obligated to Date: |
FY 2001 = $96,477.00 FY 2002 = $109,351.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
5000 FORBES AVE PITTSBURGH PA US 15213-3815 (412)268-8746 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
5000 FORBES AVE PITTSBURGH PA US 15213-3815 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
NETWORKING RESEARCH, SIGNAL PROCESSING SYS PROGRAM |
| Primary Program Source: |
01000102DB NSF RESEARCH & RELATED ACTIVIT app-0102 |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Proposal Summary
In this research, we propose to use group representation theory to generate automatically fast
algorithms for digital signal processing (DSP) transforms. Group representation theory provides a
deeper understanding of the structure of signal transforms and a context to address fundamental
questions in modeling and processing of signals. We propose to use representation theory to design
new 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 code
generator block to produce optimized software implementations for a given computer. SPIRAL
applies iteratively fast algorithms, the algorithmic rules, to generate a rich collection of alternative
equivalent formulas (the formula space) for the same DSP algorithm. For each formula, SPIRAL
then produces automatically optimized code that runs efficiently on the given computer. By
searching 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 automatic
generation of the fast algorithm, or algorithmic rules. This meta-level is the focus of our proposed
research. We exploit group representation theory to develop the theoretical framework and the
tools that produce automatically these fast algorithms for a number of DSP transforms. We will
implement and interface these tools to a DSP-AL (SPIRAL) which will enable us to translate
directly 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 transform
is invariant; decomposing stepwise the representations, giving rise to factorized decomposition ma-
trices, which determine the factorization of the transform. The symmetry catches redundancy in
the 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 decomposition
matrices will be derived in the context of a constructive extension of standard representation
theory, 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 package
for symbolic computation with group representations and structured matrices and interface it with
a DSP-AL, namely SPIRAL.
We consider different types of "symmetry," going beyond regular representations to include
arbitrary permutation and monomial representations, in order to capture in the representation
framework a wide class of signal transforms. Besides the DFT, and trigonometric transforms, we
will 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 transform
can be justified on the basis of the model underlying the data. We have shown this relation to be
connected to the boundary conditions (b.c.) assumed in describing a certain class of models widely
used 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 signal
transform, and the signal models, enabling us to address some fundamental questions, namely
how to design a signal transform which is adapted to a given signal model (i.e., reflects a desired
symmetry) and is computationally the most efficient.
Please report errors in award information by writing to: awardsearch@nsf.gov.
