Subespaços de Krylov: GMRES(m) com precondicionadores

Abstract

Grandes sistemas não simétricos esparsos e mal condicionados surgem frequentemente na discretização de EDPs. Logo, a resolução de sistemas lineares do tipo Ax  b, onde A é uma matriz de grande porte, é computacionalmente inviável através de métodos analıticos como regra de Crammer, eliminação gaussiana. O GMRES foi publicado em 1986 por Saad e Schultz como um método de subespaços de Krylov, [7]. Dessa forma, o GMRES é um método iterativo para resolver sistemas lineares da forma Ax  b onde A Mnn(R) é uma matriz esparsa e x, b Mn1(R). As variações do GMRES são amplamente usadas nas aplicações de dinâmica do fluido computacional. Também é uma escolha comum na supercomputação, para mais exemplos, ver [3],[4]. Queremos minimizar o vetor resıduo r  b  Ax para obtermos uma solução aproximada para este sistema. O GMRES é um método de projeção e pertence à famılia dos subespaços de Krylov. Antes de discutirmos sobre o GMRES, apresentaremos um algoritmo de projeção oblıqua, algumas definições e teoremas importantes sobre subespaços de Krylov, [1], [5]. Veremos o motivo pelo qual uma matriz que contém uma base para o espaço de Krylov da forma Kk ( b Ab · · · Aj1b) não é adequada para a implementação numérica. Assim, precisaremos de um método para o cálculo de uma base ortonormal para um subespaço de Krylov. Usaremos neste trabalho o método de Arnoldi utilizado pelo GMRES. No caso do GMRES com estratégia de reinicialização GMRES(m), o valor de m limitará a dimensão do subespaço de Krylov. Uma das dificuldades encontradas é o fato de não termos critérios para a escolha do valor desse m, [6]. Por fim, apresentaremos o GMRES, GMRES precondicionado, GMRES(m) e GMRES(m) precondicionado e exemplos implementados no Matlab. O precondicionamento é uma técnica usada para transformar o sistema original em um sistema mais simples de resolver, portanto, diminuindo o custo computacional, acelerando a convergência de um algoritmo também. Temos exemplos de muitos precondicionadores na literatura, [2], [4], [8], porém ainda não existe uma teoria justificando o sucesso de seu uso com quaisquer matrizes e aplicado ao GMRES(m). Dessa forma, podemos tentar fazer o uso de determinados precondicionadores para certos problemas e tentar encontrar algum padrão de convergência. bolsista de Iniciação Cientıfica PROPESQ-IC Realizamos alguns testes numéricos no software Matlab, como exemplo, usamos uma matriz de ordem 479 mal condicionada (número de condição igual a 1.4244  1012 , estabelecemos uma tolerância com precisão de 108 e realizamos os testes usando os algoritmos GMRES, GMRES com precondionador ILU (LU incompleta), GMRES(10) e com o GMRES(10) com precondicionador ILU. Notamos que o GMRES(10) não convergiu com a tolerância desejada. O número de iterações do GMRES foi 477 enquanto que o GMRES(10) com precondicionador convergiu em 1 iteração e teve o menor CPUtime(s). Existem outros tipos de precondicionadores na literatura que podem ser testados. Em geral, fatorações incompletas, inversa aproximada, são alguns exemplos clássicos de classes de precondicionadores na literatura, [1], [8].