Fast Cauchy-like and Singular Toeplitz-like Matrix Computations
Victor Pan and Ailong Zheng
An effective algorithm of Bitmead and Anderson, 1980, and Morf, 1980, computes the solution $\vec{x}=T^{-1}\vec{b}$ to a nonsingular Toeplitz or Toeplitz-like linear system $T\vec{x}=\vec{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\times 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^3n)$ 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.