Superfast algorithms for Cauchy-like matrix computations and extensions (Q1978119)

The algorithm by \textit{M. Morf} [Doubling algorithms for Toeplitz and related equations, in: Proc. IEEE Int. Conf. on ASSP, IEEE Computer Soc. Press, Silvert Spring, MD, 954-959 (1980)] and by \textit{R. R. Bitmead} and \textit{B. D. D. Anderson} [ibid. 34, 103-116 (1980; Zbl 0458.65018)] to solve Toeplitz and Toeplitz-like systems is based on the notion of displacement rank and a divide and conquer strategy. In combination with the fast Fourier transform (FFT), this gives superfast algorithms that solve a system of size \(n\) in \(O(n\log^2 n)\) operations. In this paper, the authors develop a similar strategy for Cauchy (displacement rank 1) and Cauchy-like (displacement rank \(r\)) matrices. Here the displacement rank is with respect to the displacement operator \(\nabla A = D(q)A-AD(t)\) where \(D(q)\) and \(D(t)\) are diagonal matrices. Because matrix vector multiplications for these matrices can not be directly computed with FFT, the resulting algorithm has a complexity of \(O(nr^2\log^3n)\). In principle the algorithm works for strongly nonsingular matrices \(A\), but a technique of symmetrization and/or randomization can overcome this restriction. As by-products algorithms for determinant calculation, triangular factorization, least squares solution, and matrix inversion are obtained. The algorithms apply to matrices with entries from an arbitrary field. Comparison with other (super)fast algorithms for such matrices is also made.