Look-ahead Levinson and Schur algorithms for non-HermitianToeplitz systems |
| |
Authors: | Martin H. Gutknecht Marlies Hochbruck |
| |
Affiliation: | (1) Interdisciplinary Project Center for Supercomputing, ETH Zurich, ETH-Zentrum, CH-8092 Zurich, Switzerland. E-mail: na.gutknecht@na-net.ornl.gov , CH;(2) Mathematisches Institut, Universit"at T"ubingen, Auf der Morgenstelle 10, D-72076 T"ubingen, Germany. E-mail: marlis@na.mathematik.uni-tuebingen.de , DE |
| |
Abstract: | Summary. We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our generalized Levinson and Schur recurrences require $ operations, and the Schur recurrences can be combined with recursive doubling so that an $ algorithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix. Received July 26, 1993 |
| |
Keywords: | Mathematics Subject Classification (1991): 65F05 30E05, 41A21, 42A70, 60G25 |
本文献已被 SpringerLink 等数据库收录! |
|