A unified superfast divide-and-conquer algorithm for structured matrices over abstract fields
Victor Pan
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\times n$ matrix $X$ given with its short generator, as well as to solve a linear system $X{\bf y}={\bf 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.