Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0671.65021
Ammar, Gregory; Gragg, William B.
Superfast solution of real positive definite Toeplitz systems. (English)
[A] Linear algebra in signals, systems, and control, Proc. SIAM Conf., Boston/Mass. 1986, 107-125 (1988).

[For the entire collection see Zbl 0661.00019.] \par The authors derive a generalized Schur algorithm for the ``superfast'' solution of real positive definite Toeplitz systems $Mx=b$ of order $n+1$, where $n=2\sp{\nu}$. Fast Toeplitz solvers are based on ideas from the classical theory of Szegö polynomials. In particular, the Szegö polynomials can be identified with the columns of the reverse Cholesky factorization of $M\sp{-1}$. Schur's algorithm generates a continued fraction representation of the holomorphic function mapping the unit disk in the complex plane into its closure. \par The generalized Schur algorithm is a doubling procedure for calculating the linear fractional transformation that results from n steps of Schur's algorithm. By using standard fast Fourier transform, the authors construct the linear fractional transformation that results from n steps of Schur's algorithm in O(n $\log\sp 2n)$ complex multiplications. The implementation uses the split-radix fast Fourier transform algorithms for real data of Duhamel that exploit the inherent symmetries of the real data.
[Th.Beth]

MSC 2000:: *65F05 Direct methods for linear systems
65T40 Trigonometric approximation and interpolation
68Q25 Analysis of algorithms and problem complexity

Keywords: superfast solution; Schur algorithm; positive definite Toeplitz systems; Fast Toeplitz solvers; Szegö polynomials; Cholesky factorization; continued fraction representation; linear fractional transformation; fast Fourier transform; data of Duhamel

Citations: Zbl 0661.00019

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]