NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A fast, preconditioned conjugate gradient Toeplitz solverA simple factorization is given of an arbitrary hermitian, positive definite matrix in which the factors are well-conditioned, hermitian, and positive definite. In fact, given knowledge of the extreme eigenvalues of the original matrix A, an optimal improvement can be achieved, making the condition numbers of each of the two factors equal to the square root of the condition number of A. This technique is to applied to the solution of hermitian, positive definite Toeplitz systems. Large linear systems with hermitian, positive definite Toeplitz matrices arise in some signal processing applications. A stable fast algorithm is given for solving these systems that is based on the preconditioned conjugate gradient method. The algorithm exploits Toeplitz structure to reduce the cost of an iteration to O(n log n) by applying the fast Fourier Transform to compute matrix-vector products. Matrix factorization is used as a preconditioner.
Document ID
19900015415
Acquisition Source
Legacy CDMS
Document Type
Contractor Report (CR)
Authors
Pan, Victor
(State Univ. of New York Albany., United States)
Schrieber, Robert
(Rensselaer Polytechnic Inst. Troy, NY., United States)
Date Acquired
September 6, 2013
Publication Date
March 1, 1989
Subject Category
Computer Programming And Software
Report/Patent Number
NAS 1.26:180367
NASA-CR-180367
RIACS-TR-89.14
Accession Number
90N24731
Funding Number(s)
CONTRACT_GRANT: NCC2-387
CONTRACT_GRANT: DAAL03-86-K-0112
CONTRACT_GRANT: PSC-CUNY-668541
CONTRACT_GRANT: N00014-86-K-0610
CONTRACT_GRANT: NSF CCR-88-05782
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available