Fraction-Free Factorization of a Toeplitz Matrix

Abstract: The paper presents a fast and efficient integer algorithm for the fraction-free triangular factorization of a strongly regular Hermitian Toeplitz matrix. The algorithm enhances the ordinary fast Schur algorithm for this factorization with the property that when it is applied to a matrix with (Gaussian or real) integer entries, the algorithm is completed over the respective integral domain with integers of minimal length and an overall low binary complexity.