Fast superoptimal preconditioning of multiindex Toeplitz matrices

In this article three well-known methods of circulant preconditioning of finite multiindex Toeplitz linear systems, that is linear systems indexed by integers i1, … , id with 0 ⩽ is < ns (s = 1, … , d), are studied in detail. A general algorithm for the construction of the so-called superoptimal preconditioner is also given and it is shown that this procedure requires O(n1 ⋯ ndlog(n1 ⋯ nd)) floating point operations.