Métodos iterativos para solução de sistemas lineares: aceleração usando reflexões circuncentradas e GPU

Abstract

Este projeto teve como objetivo principal realizar um estudo da teoria de métodos iterativos que se utilizam de projeções ortogonais para solução de sistemas lineares esparsos. Os métodos estudados foram o método de projeções sequenciais de Kaczmarz (KACZ) e os métodos de projeções simultâneas de Cimmino (CIM) e método de média de componentes (CAV). Para compreender estes métodos, foi realizado um estudo de algumas ferramentas de cunho matemático, tais como: espaços vetoriais, operadores, sequências, entre outros, bem como de ferramentas usuais da área de métodos computacionais de otimização, tais como: análise numérica e otimização convexa: convergência de algoritmos, condições para convergência, entre outros. Implementamos computacionalmente os métodos iterativos de KACZ, CIM e CAV em CPU. Na sequência, foi realizado um estudo de técnicas de implementação em paralelo, utilizando GPUs, por fim, implementamos os métodos paralelizáveis de CIM e CAV, recorrendo à linguagem de programação Julia e sua biblioteca CUDA.jl específica para trabalhar com GPUs do tipo CUDA e placas NVIDIA. Por fim, realizamos testes computacionais aplicando os algoritmos de CIM e CAV em sete matrizes esparsas de grande porte da coleção de problemas SuiteSparse Matrix Collection e comparamos a velocidade de tais algoritmos na GPU e na CPU. Após tais experiências, averiguou-se que os algoritmos tiveram um tempo consideravelmente superior de iteração em GPU.