SPARSE MATRIX FACTORIZATIONS FOR FAST SYMMETRIC FOURIER TRANSFORMS.
Item
-
Title
-
SPARSE MATRIX FACTORIZATIONS FOR FAST SYMMETRIC FOURIER TRANSFORMS.
-
Identifier
-
AAI8801760
-
identifier
-
8801760
-
Creator
-
SEGUEL, JAIME.
-
Date
-
1987
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics
-
Abstract
-
In this work we propose new fast algorithms computing the discrete Fourier transform of certain families of symmetric sequences. We deal with sequences that are commonly found in problems of structure determination by x-ray crystallography and in the numerical solutions of boundary-value problems in partial differential equations.;In the algorithms presented in this work, the redundancies in the input and output data, due to the presence of symmetries in the input data sequence, have been eliminated. Using ring-theoretical methods we get a matrix representation for the remaining calculations; which factors as the product of a complex block-diagonal matrix times an integral matrix.;A basic two-step algorithm scheme arises from this factorization with a first step consisting of pre-additions and a second step containing the calculations involved in computing with the blocks in the block-diagonal factor. These blocks are structured as block-Hankel matrices and two sparse matrix factoring formulas are developed in order to diminish their arithmetic complexity. In the first formula the block-Hankel matrices are reduced to block-diagonal ones having only skew-circulant blocks in the main diagonal. This is done to the cost of pre and post-additions. In the second formula the block-Hankel matrices are expressed as tensor products of identity matrices times skew-circulant ones. This formula is obtained to the cost of permutations in both, input and output data sequences.;Through these formulas, computing with block-Hankel matrices is bounded to the execution of fast cyclic convolution algorithms.;The practical value of these formulas is yet to be tested; however, simple theoretical considerations indicate that minimal complexity bounds can be achieved when the number of input data is highly composite. On the other hand, the formulation of these algorithms as tensor product of matrices makes them suitable for their implementation in parallel or vector processors.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
-
Program
-
Mathematics
