Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)
Um Método para a Solução de Sistemas Lineares Através do Gradiente Conjugado Cooperativo
Guilherme da Silva Niedu
Março/2012
| Programa: |
Engenharia Elétrica |
Essa dissertação explora a idéia de cooperação entre agentes (ou tarefas) no contexto do algoritmo Gradiente Conjugado (CG). Esse famoso algoritmo apresenta uma série de propriedades interessantes, tanto como algoritmo em aritmética exata quanto como em aritmética de precisão finita. No entanto, é amplamente conhecido que, devido à sua estrutura, o algoritmo CG tradicional não pode ser paralelizado de maneira comum. Neste trabalho, o algoritmo CG é revisto, de uma perspectiva multi-tarefa, que pode ser vista como uma generalização direta da abordagem de controle do algoritmo CG proposta anteriormente na literatura, na qual os parâmetros escalares de controle (= passos nas direções gradientes e gradientes conjugadas) são substituídos por matrizes. A cooperação entre agentes reside no fato dos cálculos de cada entrada da matriz de parâmetros de controle agora envolvem informação vinda dos outros agentes. O método pode também ser visto como uma generalização do algoritmo CG tradicional na qual múltiplas direções de descida e direções gradientes conjugadas são atualizadas simultaneamente. Além disso, é uma generalização que permite implementação multi-tarefa de baixa complexidade em aritmética exata. Um passo adicional de cooperação, envolvendo uma projeção afim, projetado para acelerar a computação também é discutido posteriormente. São apresentados experimentos numéricos que ilustram os resultados teóricos.
