Stable And Efficient Algorithms For Structured Systems Of Linear Equations

. Recent research shows that structured matrices such as Toeplitz and Hankel matrices can be transformed into a different class of structured matrices called Cauchy-like matrices using the FFT or other trigonometric transforms. Gohberg, Kailath and Olshevsky demonstrate numerically that their fast variation of the straightforward Gaussian elimination with partial pivoting (GEPP) procedure on Cauchy-like matrices is numerically stable. Sweet and Brent show that the error growth in this variation could be much larger than would be encountered with straightforward GEPP in certain cases. In this paper, we present a modified algorithm that avoids such extra error growth and can perform a fast variation of Gaussian Elimination with Complete Pivoting (GECP). Our analysis shows that it is both efficient and numerically stable, provided that the element growth in the computed factorization is not large. We also present a more efficient variation of this algorithm and discuss implementation tech..