Novas versões para a Inversa Aproximada em Blocos: Uma Comparação Numérica
DOI:
https://doi.org/10.5540/tcam.2022.023.03.00471Keywords:
Inversa Aproximada, Matrizes em Bloco, Precondicionadores, Métodos de Krylov.Abstract
Propomos duas variações do precondicionador de aproximação da inversa em blocos (BAINV), originalmente desenvolvido por Benzi, Kouhia e Tuma em 2001. A primeira variação, a aproximação da inversa em blocos estabilizada para matrizes não simétricas (SBAINV-NS), é válida para matrizes não simétricas e não singulares. A segunda variação, a aproximação da inversa em blocos estabilizada combinada (SBAINV-VAR), é baseada nas relações dos fatores da inversa aproximada em blocos com a fatoração LDU em blocos de A, as quais demonstraremos, e na relação de aproximação da inversa de Neumann. Demonstramos a consistência matemática dessas novas versões e apresentamos os algoritmos referentes a cada uma delas, além de exibir experimentos numéricos onde comparamos a densidade dos precondicionadores e o número de iterações quando aplicados ao método estabilizado de gradientes bi-conjugados (Bi-CGSTAB). Os principais resultados numéricos obtidos indicam que o uso da estrutura de blocos pode aumentar a performance do método iterativo de Krylov em comparação com a versão escalar. Além disso, nos experimentos apresentados, o SBAINV-VAR produz, em geral, precondicionadores que realizam menos iterações do Bi-CGSTAB e são menos densos do que o SBAINV-NS.References
G. H. Golub and C. F. van Loan,Matrix Computations. Johns Hopkins Uni-versity Press, 4rd ed., 2013.
Y. Saad,Iterative Methods for Sparse Linear Systems. SIAM, 2nd ed., 2003.
J. A. Meijerink and H. A. van der Vorst, “An iterative solution method forlinear systems of which the coefficient matrix is a symmetric M-matrix,”Math.Comp., vol. 31, pp. 148–162, 1977.
M. Benzi, C. D. Meyer, and M. Tůma, “A Sparse Approximate Inverse Pre-conditioner for the Conjugate Gradient Method,”SIAM Journal on ScientificComputing, vol. 17, no. 5, pp. 1135–1149, 1996.
M. Benzi and M. Tůma, “A Sparse Approximate Inverse Preconditionerfor Nonsymmetric Linear Systems,”SIAM Journal on Scientific Computing,vol. 19, no. 3, pp. 968–994, 1998.
R. Bridson and W.-P. Tang, “Refining an approximate inverse,”Journal ofComputational and Applied Mathematics, vol. 123, no. 1, pp. 293 – 306, 2000.Numerical Analysis 2000. Vol. III: Linear Algebra.
A. Rafiei and F. Toutounian, “New breakdown-free variant of ainv methodfor nonsymmetric positive definite matrices,”Journal of Computational andApplied Mathematics, vol. 219, no. 1, pp. 72 – 80, 2008.
A. Rafiei, “Left-looking version of ainv preconditioner with complete pivotingstrategy,”Linear Algebra and its Applications, vol. 445, pp. 103 – 126, 2014.
D. K. Salkuyeh, “A sparse approximate inverse preconditioner for nonsymme-tric positive definite matrices,”Journal of Applied Mathematics & Informatics,vol. 28, no. 5-6, pp. 1131–1141, 2010.
M. Benzi, R. Kouhia, and M. Tůma, “Stabilized and block approximate in-verse preconditioners for problems in solid and structural mechanics,”Compu-ter Methods in Applied Mechanics and Engineering, vol. 190, no. 49-50, pp. 6533– 6554, 2001.
A. Rafiei, M. Bollhöfer, and F. Benkhaldoun, “A block version of left-lookingainv preconditioner with one by one or two by two block pivots,”Applied Mathe-matics and Computation, vol. 350, pp. 366 – 385, 2019.
L. Fox,An introduction to numerical linear algebra. Mono. Num. Analys.,Oxford: Clarendon Press, 1964.
M. Almeida, J. Sekigushi, P. Goldfeld, L. M. Carvalho, and M. Souza, “Sup-porting theory for a block approximate inverse preconditioner,”Linear Algebraand its Applications, 2020.
R. J. Plemmons, “M-matrix characterizations. I—nonsingularM-matrices,”Linear Algebra and Its Applications, vol. 18, no. 2, pp. 175–188, 1977.
G. Meurant,Computer solution of large linear systems. Elsevier, 1999.
N. J. Higham,Accuracy and stability of numerical algorithms. SIAM, 2 ed.,2002.
H. van der Vorst, “BI-CGSTAB: a fast and smoothly converging variant of BI-CG for the solution of non-symmetric linear systems,”SIAM Journal on Scien.and Stat. Computing, vol. 13, pp. 631–644, March 1992.
A. Abdelfattah, H. Ltaief, D. Keyes, and J. Dongarra, “Performance optimi-zation of sparse matrix-vector multiplication for multi-component pde-basedapplications using gpus,”Concurrency and Computation: Practice and Expe-rience, vol. 28, no. 12, pp. 3447–3465, 2016.
S. Williams, A. Waterman, and D. Patterson, “Roofline: An insightful vi-sual performance model for multicore architectures,”Commun. ACM, vol. 52,p. 65–76, Apr. 2009.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.