Superfast Computations with Singular Structured Matrices over Abstract Fields

An effective superfast divide-and-conquer algorithm of Morf, 1980, and Bitmead and Anderson, 1980, computes the solution x = T −1 b to a strongly non- singular Toeplitz or Toeplitz-like linear system T x = b. The algorithm is called superfast because it runs in almost linear time, versus cubic time of Gaussian elimination and quadratic time of some known faster solutions. Recently, the algorithm was extended to similar superfast computations with n x n Cauchy and Cauchy-like matrices. We use randomization to extend this approach to superfast solution of a singular Cauchy-like linear system of equations over any field of constants and, futhermore, to superfast computation of the rank of a Cauchy-like matrix and a basis for its null space. We also ameliorate slightly Kaltofen’s superfast solver of singular Toeplitz-like linear systems in an arbitrary field. The algorithms can be easily extended to similar computations with singular Hankel-like and Vandermonde-like matrices. The applications include rational and polynomial interpolation, Pade approximation and decoding Reed-Solomon and algebraic-geometric codes.