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
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.