Seleção Dinâmica da Dimensão do Subespaço de Krylov no Método GMRES(m) e suas Variantes

Autores

  • T.T. Gonçalez
  • R.D. da Cunha

DOI:

https://doi.org/10.5540/tema.2006.07.02.0277

Resumo

Nesse trabalho apresentamos alguns algoritmos adaptativos do Método do Resíduo Mínimo Generalizado (GMRES) [10], um método iterativo para resolver sistemas de equações lineares com matrizes não simétricas e esparsas, o qual baseiase nos métodos de projeção ortogonal sobre um subespaço de Krylov. O GMRES apresenta uma versão reinicializada, denotada por GMRES(m), também proposta em [10], com o intuito de permitir a utilização do método para resolver sistemas de equações lineares cuja matriz dos coeficientes apresenta uma grande dimensão. No entanto, escolher um valor apropriado, m, para a dimensão da base do subsespaço de Krylov é bastante difícil. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um critério que tem por objetivo escolher, ao longo das iterações, um m tal que se obtenha a convergência do método, possivelmente de forma mais rápida. Aproximadamente duas centenas de testes foram realizados utilizando as matrizes da coleção Harwell-Boeing, que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons conforme apresentaremos nesse trabalho.

Referências

[1] A. Baker, E. Jessup, T. Manteuffel, A Technique for Accelerating the Convergence of Restarted GMRES. Technical Report CU-CS-945-03, Dept. of Computer Science, College of Engineering and Applied Science, University of Colorado at Boulder, 2003.

A. Chapman, Y. Saad, Deflated and augmented Krylov subspace techniques. Numerical Linear Algebra with Applications, 4 (1997), 15–41.

M.S. Driver, Parallel sparse linear algebra for homotopy methods. PhD thesis, Faculty of the Virginia Polytechnic Institute and State University, 1997.

E. Embree, How descriptive are GMRES convergence bounds? Research Report NA-99/08, Numerical Analysis Group, Oxford University Computing Laboratory, 1999.

T.T. Gonçalez, Algoritmos adaptativos para o método GMRES(m). Dissertação de mestrado, Programa de Pós-Graduação em Matemática Aplicada, UFRGS, 2005.

L.A. Hageman, D.M. Young, “Applied Iterative Methods”, Academic Press, New York, 1981.

W. Joubert, On the convergence behavior of the restarted GMRES algorithm for solving nonsymmetric linear systems. Numerical Linear Algebra with Applications, 1 No. 5 (1994), 427–447.

Mathematical and Computational Sciences Division, Information Technology Laboratory, National Institute of Standards and Technology, Matrix Market: A visual repository of test data for use in comparative studies of algorithms for numerical linear algebra. http://math.nist.gov/MatrixMarket/, 2003.

K. Moriya, T. Nodera, New adaptive GMRES(m) method with choosing suitable restart cycle m. In R. Wyrzykowski et al., editor, Parallel Processing and Applied Mathematics 2003, number 3019 in Lecture Notes in Computer Science, pp 1105–1113, Berlin, 2003. Spring-Verlag.

Y. Saad, M.H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal of Scientific and Statistical Computing, 7 (1986), 856–869.

N. Tsuno, T. Nodera, The speedup of the GMRES(m) method using the early restarting procedure. Journal of the Information Processing Society of Japan, 40, No. 4 (1999), 1760–1773.

H.F. Walker, Implementation of the GMRES method using Householder transformations. SIAM Journal on Scientific and Statistical Computing, 9, No. 1 (1989), 152–163.

H.F. Walker, L. Zhou, A simpler GMRES. Linear Algebra and its Applications, 1 (1994), 574–581.

Downloads

Publicado

2006-06-01

Como Citar

Gonçalez, T., & da Cunha, R. (2006). Seleção Dinâmica da Dimensão do Subespaço de Krylov no Método GMRES(m) e suas Variantes. Trends in Computational and Applied Mathematics, 7(2), 277–286. https://doi.org/10.5540/tema.2006.07.02.0277

Edição

Seção

Artigo Original