Novas versões para a Inversa Aproximada em Blocos: Uma Comparação Numérica

Authors

DOI:

https://doi.org/10.5540/tcam.2022.023.03.00471

Keywords:

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.

Published

2022-09-12

How to Cite

Cruz, J. S., Almeida, M. C., Carvalho, L. M., & Souza, M. (2022). Novas versões para a Inversa Aproximada em Blocos: Uma Comparação Numérica. Trends in Computational and Applied Mathematics, 23(3), 471–498. https://doi.org/10.5540/tcam.2022.023.03.00471

Issue

Section

Original Article