ω-Circulant Matrices: A Selection of Modern Applications from Preconditioning of Approximated PDEs to Subdivision Schemes

Diaz Fuentes R.

First

;Serra-Capizzano S.;Sormani R. L.

2023-01-01

---

Abstract

It is well known that (Formula presented.) -circulant matrices with (Formula presented.) can be simultaneously diagonalized by a transform matrix, which can be factored as the product of a diagonal matrix, depending on (Formula presented.), and of the unitary matrix (Formula presented.) associated to the Fast Fourier Transform. Hence, all the sets of (Formula presented.) -circulants form algebras whose computational power, in terms of complexity, is the same as the classical circulants with (Formula presented.). However, stability is a delicate issue, since the condition number of the transform is equal to that of the diagonal part, tending to (Formula presented.). For (Formula presented.), the set of related matrices is still an algebra, which is the algebra of lower triangular matrices, but they do not admit a common transform since most of them (all except the multiples of the identity) are non-diagonalizable. In the present work, we review two modern applications, ranging from parallel computing in preconditioning of PDE approximations to algorithms for subdivision schemes, and we emphasize the role of such algebra. For the two problems, few numerical tests are conducted and critically discussed and the related conclusions are drawn.