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
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- 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.
- 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.
- 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).
- 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.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.