Seleção Dinâmica da Dimensão do Subespaço de Krylov no Método GMRES(m) e suas Variantes
DOI:
https://doi.org/10.5540/tema.2006.07.02.0277Resumo
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
Como Citar
Edição
Seção
Licença
Direitos Autorais
Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.
Propriedade Intelectual e Termos de uso
O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.
O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.
