Blocking structures, approximation, and preconditioning

We consider block-structured matrices An, where the blocks are of (block) unilevel Toeplitz type with s×t matrix-valued generating functions. Under mild assumptions on the size of the (rectangular) blocks, the asymptotic distribution of the singular values of the associated matrix-sequences is identified and, when the related singular value symbol is Hermitian, it coincides with the spectral symbol. Building on the theoretical derivations, we approximate the matrices with simplified block structures that show two important features: a) the related simplified matrix-sequence has the same distributions as {An}n; b) a generic linear system involving the simplified structures can be solved in O(nlogn) arithmetic operations. The two key properties a) and b) suggest a natural way for preconditioning a linear system with coefficient matrix An. Under mild assumptions, the singular value analysis and the spectral analysis of the preconditioned matrix-sequences is provided, together with a wide set of numerical experiments.