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

Autores

  • J. S. Cruz Programa de Pós Graduação em Engenharia Mecânica - PPG-EM/UERJ, FEN, Universidade do Estado do Rio de Janeiro. https://orcid.org/0000-0002-7296-3928
  • M. C. Almeida Departamento de Matemática, Instituto Federal do Rio de Janeiro. https://orcid.org/0000-0002-6170-2036
  • L. M. Carvalho IME, Universidade do Estado do Rio de Janeiro.
  • M. Souza Departamento de Estatística e Matemática Aplicada, Universidade Federal do Ceará.

DOI:

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

Palavras-chave:

Inversa Aproximada, Matrizes em Bloco, Precondicionadores, Métodos de Krylov.

Resumo

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.

Referências

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

Publicado

2022-09-12

Como Citar

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

Edição

v. 23 n. 3 (2022)

Seção

Artigo Original

Licença

Política para Periódicos de Acesso Livre


Autores que publicam nesta revista concordam com os seguintes termos:
  1. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
  2. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
  3. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
  4. Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
 
Propriedade intelectual

Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.