Graduate Thesis Or Dissertation
 

An algebraic view of the symmetry of fast transforms

Público Deposited

Contenido Descargable

Descargar PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/qf85nd635

Descriptions

Attribute NameValues
Creator
Abstract
  • Why are the fast Fourier transform and the fast Hadamard transform fast? A transform can be computed by multiplying a matrix times a vector, which normally requires 0(n²) operations. The matrices corresponding to these transforms can be rearranged to eliminate redundant computations resulting in O(nlogn) operations. We investigate algebraic reasons for fast transforms. Specifically, we notice that these fast transform matrices correspond to the multiplication tables of particular rings. We demonstrate sufficient conditions involving the decomposition of a ring into a descending chain of subrings and a corresponding ascending chain of annihilator subrings. These conditions allow the ring's multiplication table to be arranged in a form which is tiled with variations of a single subblock. We need conditions to insure that the mapping from the ring table to the transform matrix will preserve the subblock structure. One sufficient condition, motivated by the Fourier transform, is that the mapping is a homomorphism. Another sufficient condition, motivated by the Hadamard transform, is that the ring has an orthogonal basis. We display other rings satisfying these conditions or a mixture of these conditions which produce fast transform matrices. Our conditions are only sufficient: they give a proper subset of the transform matrices representable by the generalized Kronecker product of Fino and Algazi. However, our conditions can describe all commonly used transforms.
Resource Type
Fecha Disponible
Fecha de Emisión
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Declaración de derechos
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6670 in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Relaciones

Parents:

This work has no parents.

En Collection:

Elementos

Miniatura Título Fecha de subida Visibilidad Acciones
file details RubyGlennR1983.pdf 2017-08-07 Público Descargar