FAST CAUCHY-LIKE AND SINGULAR TOEPLITZ-LIKE MATRIX COMPUTATIONS

VICTOR PAN AILONG ZHENG

Abstract. An effective algorithm of Bitmead and Anderson, 1980, and Morf, 1980, computes the solution x⃗ = T^{−1}b⃗ to a nonsingular Toeplitz or Toeplitz-like linear system T x⃗ = b⃗, a short displacement generator for the inverse T^{−1} of T, and det T. We extend this algorithm to the similar computations with n × n Cauchy ( generalized Hilbert ) and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr^{2} log^{3} n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C ( r = 1 if C is a Cauchy matrix ). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C^{−1}, and the solution to a nonsingular linear system of n equations with such a matrix C. Our algorithm does not use the reduction to Toeplitz-like computations. We avoid singularity in this algorithm and run it in an arbitrary field by using randomization. We also ameliorate slightly Kaltofen’s solver of Toeplitz-like singular linear systems in an arbitrary field.