An algebraic view of the symmetry of fast transforms Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/qf85nd635

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
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
Additional Information
  • description.provenance : Approved for entry into archive by Deborah Campbell(deborah.campbell@oregonstate.edu) on 2013-08-14T17:01:20Z (GMT) No. of bitstreams: 1 RubyGlennR1983.pdf: 412130 bytes, checksum: cd788359114e8ad81a3ebf2b88a84550 (MD5)
  • description.provenance : Submitted by Katy Davis (kdscannerosu@gmail.com) on 2013-08-12T21:06:50Z No. of bitstreams: 1 RubyGlennR1983.pdf: 412130 bytes, checksum: cd788359114e8ad81a3ebf2b88a84550 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-08-12T21:30:21Z (GMT) No. of bitstreams: 1 RubyGlennR1983.pdf: 412130 bytes, checksum: cd788359114e8ad81a3ebf2b88a84550 (MD5)
  • description.provenance : Made available in DSpace on 2013-08-14T17:01:20Z (GMT). No. of bitstreams: 1 RubyGlennR1983.pdf: 412130 bytes, checksum: cd788359114e8ad81a3ebf2b88a84550 (MD5) Previous issue date: 1982-06-04

Relationships

In Administrative Set:
Last modified: 08/07/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items