A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling

We propose a superfast solver for Toeplitz linear systems based on rank structured matrix methods and randomized sampling. The solver uses displacement equations to transform a Toeplitz matrix $T$ into a Cauchy-like matrix $\mathcalC$, which is known to have low-numerical-rank off-diagonal blocks. Thus, we design a fast scheme for constructing a hierarchically semiseparable (HSS) matrix approximation to $\mathcalC$, where the HSS generators have internal structures. Unlike classical HSS methods, our solver employs randomized sampling techniques together with fast Toeplitz matrix-vector multiplications, and thus converts the direct compression of the off-diagonal blocks of $\mathcalC$ into the compression of much smaller blocks. A strong rank-revealing QR factorization method is used to generate/preserve certain special structures, and also to ensure stability. A fast ULV HSS factorization scheme is provided to take advantage of the special structures. We also propose a precomputation procedure for the HSS construction so as to further improve the efficiency. The complexity of these methods is significantly lower than some similar Toeplitz solvers for large matrix size $n$. Detailed flop counts are given, with the aid of a rank relaxation technique. The total cost of our methods includes $O(n)$ flops for HSS operations and $O(n\log^2 n)$ flops for matrix multiplications via FFTs, where $n$ is the order of $T$. Various numerical tests on classical examples, including ill-conditioned ones, demonstrate the efficiency, and also indicate that the methods are stable in practice. This work shows a practical way of using randomized sampling in the development of fast rank structured methods.