Immittance- versus scattering-domain fast algorithms for non-Hermitian Toeplitz and quasi-Toeplitz matrices (Q908655)

The classical algorithms of Schur and Levinson for solving or factoring a Hermitian Toeplitz matrix are considered here (as scattering-domain algorithms). Based on a recent carefully study of the authors on immittance-domain Schur and Levinson algorithms, this paper presents immittance versions of these algorithms for non-Hermitian Toeplitz and quasi-Toeplitz matrices. A study of all possible pairs of recursions of highest efficiency is presented, showing five essentially different pairs of recursions of equal efficiency. For the algorithms of Schur and Levinson, the immittance versions are presented in all five cases. It is also shown how the extended QT algorithm can also be transformed into immittance algorithm. The immittance version of each algorithm for non-Hermitian matrices needs as much computation as its scattering counterpart. Both the immittance and the scattering algorithms exploit the (quasi-) Toeplitz structure for producing fast algorithms. However, unlike the scattering algorithms, the immittance algorithms can utilize the symmetrical property of the matrix and in Hermitian cases produce algorithms of improved efficiency.