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.0277Abstract
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.References
[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
Published
How to Cite
Issue
Section
License
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
