A UNIFIED SUPERFAST DIVIDE-AND-CONQUER ALGORITHM FOR STRUCTURED MATRICES OVER ABSTRACT FIELDS

VICTOR PAN

Abstract. We propose a superfast divide-and-conquer algorithm that uses 2n − 2 random parameters, O(n) memory space and O((n log^{2} n) log log n) operations in a fixed arbitrary field in order to compute the rank and a basis for the null space of a structured n × n matrix X given with its short generator, as well as to solve a linear system Xy = b or to determine its inconsistency. If rank X = n, the algorithm also computes det X and a short generator of X^{−1}. The cost bounds cover correctness verification for the output but not the cost of the generation of random parameters. The algorithm gives a unified treatment of various classes of structured matrices including ones of Toeplitz, Hankel, Vandermonde and Cauchy types.