Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp đa lưới cho ma trận Toeplitz khối với các khối kích thước nhỏ
Tóm tắt
Trong bài báo này, chúng tôi thảo luận về các phương pháp đa lưới cho các ma trận Toeplitz khối đối xứng dương xác định có điều kiện kém. Hệ thống ma trận Toeplitz khối của chúng tôi có tính chất tổng quát ở chỗ các khối riêng lẻ không nhất thiết phải là Toeplitz, nhưng chúng tôi giới hạn sự chú ý vào các khối có kích thước nhỏ. Chúng tôi nghiên cứu cách chọn các toán tử chuyển giao cho mở rộng và thu hẹp sao cho các thuật toán đa lưới của chúng tôi hội tụ nhanh chóng. Chúng tôi chỉ ra tại sao các toán tử chuyển giao này cũng có thể được hiểu như là các ma trận khối và chúng có liên quan như thế nào đến các nghiệm của hàm ma trận sinh ra. Chúng tôi giải thích cách mà các thuật toán mới của chúng tôi có thể được kết hợp hiệu quả với việc sử dụng một toán tử lưới thô tự nhiên. Chúng tôi xác định rõ một lớp các ma trận Toeplitz khối có điều kiện kém cho mà các ý tưởng thuật toán của chúng tôi là phù hợp. Ở phần cuối cùng, chúng tôi trình bày cái nhìn về các hệ thống Toeplitz khối có điều kiện tốt và các vấn đề loại Laplace vector. Trong trường hợp sau, các khối kích thước nhỏ có thể được hiểu là các bậc tự do liên quan đến một nút. Một số lượng lớn các thí nghiệm số xuyên suốt bài báo xác nhận thuyết phục rằng các bộ giải đa lưới của chúng tôi dẫn đến hội tụ theo bậc tối ưu.
Từ khóa
#ma trận Toeplitz khối #phương pháp đa lưới #hội tụ nhanh #toán tử chuyển giao #điều kiện kémTài liệu tham khảo
A. Aricò, M. Donatelli, and S. Serra Capizzano, V-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 186–214.
W. Briggs, A Multigrid Tutorial, SIAM, Philadelphia, 1987.
R. Chan and M. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38 (1996), pp. 427–482.
R. Chan, C. Chang, and H. Sun, Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput., 19 (1998), pp. 516–529.
G. Fiorentino and S. Serra, Multigrid methods for Toeplitz matrices, Calcolo, 28 (1992), pp. 283–305.
G. Fiorentino and S. Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput., 17 (1996), pp. 1068–1081.
A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, Philadelphia, 1997.
U. Grenander and G. Szegö, Toeplitz Forms and Their Applications, 2nd edn., Chelsea, New York, 1984.
W. Hackbusch, Multigrid methods and applications, Springer, Berlin, 1985.
T. Huckle and J. Staudacher, Matrix multilevel methods and preconditioning, BIT, 42 (2002), pp. 541–560.
T. Huckle and J. Staudacher, Multigrid preconditioning and Toeplitz matrices, Electron. Trans. Numer. Anal., 13 (2002), pp. 81–105.
M. Miranda and P. Tilli, Asymptotic spectra of Hermitian block Toeplitz matrices and preconditioning results, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 867–881.
S. Serra, Asymptotic results on the spectra of block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 31–44.
S. Serra, Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT, 39 (1999), pp. 152–175.
S. Serra Capizzano, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences, Numer. Math., 92 (2002), pp. 433–465.
S. Serra Capizzano and C. Tablino Possio, Multigrid methods for multilevel circulant matrices, SIAM J. Sci. Comput., 26 (2005), pp. 55–85.
J. Staudacher, Multigrid Methods for Matrices With Structure and Applications in Image Processing, Ph.D. thesis, Department of Computer Science, Technical University Munich, 2002, available online via http://tumb1.biblio.tu-muenchen.de/publ/diss/in/2002/staudacher.pdf
H. Sun, R. Chan, and Q. Chang, A note on the convergence of the two-grid method for Toeplitz systems, Comput. Math. Appl., 34 (1997), pp. 11–18.
H. Sun, X. Jin, and Q. Chang, Convergence of the multigrid method for ill-conditioned block Toeplitz systems, BIT, 41 (2001), pp. 179–190.
U. Trottenberg, C. Oosterlee, and K. Schüller, Multigrid, Academic Press, London, 2001.
P. Vanek, M. Brezina, and J. Mandel, Convergence of algebraic multigrid based on smoothed aggregation, Numer. Math., 88 (2001), pp. 559–579.
P. Vanek, J. Mandel, and M. Brezina, Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56 (1996), pp. 179–196.