2010/10/27 by Marco Donatelli, Stefano Serra‐Capizzano, Donatelli, Marco +3
Computer Science · Mathematics · #Matrix Theory and Algorithms #Holomorphic and Operator Theory #Advanced Topics in Algebra
paper · pdf · doi:10.48550/arxiv.1010.5730
Starting from the spectral analysis of g-circulant matrices, we consider a\nnew multigrid method for circulant and Toeplitz matrices with given generating\nfunction. We assume that the size n of the coefficient matrix is divisible by g\n\≥ 2 such that at the lower level the system is reduced to one of size n/g by\nemploying g-circulant based projectors. We perform a rigorous two-grid\nconvergence analysis in the circulant case and we extend experimentally the\nresults to the Toeplitz setting, by employing structure preserving projectors.\nThe optimality of the proposed two-grid method and of the multigrid method is\nproved, when the number theta \∈ N of recursive calls is such that 1 < theta <\ng. The previous analysis is used also to overcome some pathological cases, in\nwhich the generating function has zeros located at "mirror points" and the\nstandard two-grid method with g = 2 is not optimal. The numerical experiments\nshow the correctness and applicability of the proposed ideas both for circulant\nand Toeplitz matrices.\n