Fast superoptimal preconditioning of multiindex Toeplitz matrices

RODRIGUEZ, GIUSEPPE;VAN DER MEE, CORNELIS VICTOR MARIA;SEATZU S.

2006-01-01

---

Abstract

In this article three wellknown methods of circulant preconditioning of finite multiindex Toeplitz linear systems, that is linear systems indexed by integers i1 , . . ., id with 0=<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 ··· nd log(n1 · · · nd )) floating point operations.