Otimizando a resolução de sistemas lineares: Uma abordagem paralela do algoritmo de Gauss-Jacobi em C
Introdução:
Softwares modernos precisam, cada vez mais, modelar e solucionar problemas mais complexos. O Uber precisa calcular, em tempo real, a melhor rota entre 2 pontos e recalcular caso o motorista não a siga. Modelos de dinâmica populacional podem ser usados para prever o crescimento/espalhamento de uma doença e nos dizer em qual região deve ser tratada primeiro. Sistemas de recomendação são utilizados em muitas plataformas para recomendações de livros, filmes e músicas e é um dos principais motivos do sucesso dessas plataformas, uma vez que é usado para reter os usuários nas mesmas. O algoritmo de PageRank do Google diz quais páginas da web são mais relevantes para a busca do usuário.
Os exemplos acima são uma pequena parte dos problemas da nossa realidade que foram resolvidos computacionalmente e todos têm um ponto em comum: são soluções de sistemas de equações lineares. Inúmeros problemas do cotidiano são modelados como um sistema de equações lineares, que é um conjunto de m equações de n variáveis lineares (ou seja, grau 1). Pode ser representado na forma:
Ax = b
Onde A é uma matriz mxn com os coeficientes das variáveis, x é o vetor nx1 das variáveis e b é um vetor mx1 com as constantes das equações. No entanto, vamos considerar no nosso escopo m=n.
Dessa forma, uma vez construído o modelo que representa o problema a ser resolvido, o próximo passo é encontrar a solução. Para isso, há algoritmos como a fatoração LU, quando existe uma solução exata, ou o método dos mínimos quadrados, quando não há. No entanto, essas soluções são computacionalmente custosas, principalmente porque as matrizes de problemas complexos costumam ser enormes — o que se torna um desafio quando o software precisa realizar os cálculos em tempo real. Por exemplo, em computação gráfica é comum renderizar os cenários de jogos online e é necessário que seja renderizado com bastante rapidez e fluidez, mesmo que alguns pixels sejam aproximados. A forma de reduzir os custos computacionais, apesar de carregar algum erro aceitável, é reescrever o sistema como um problema de ponto fixo. Ou seja:
Ax = b
Passa a ser
x = Mx + c
E agora serão necessários novos algoritmos que resolvem os modelos desta forma. Felizmente, há 2 conhecidos: Gauss-Seidel e Gauss-Jacobi, mas apenas o último permite que o cômputo do vetor resultante seja realizado de forma paralela.
Como trabalho da disciplina de Programação Concorrente e Paralela, implementei o algorimo de Gauss-Jacobi multi-threads em C. Caso a leitura acima tenha despertado interesse, o restante do relatório está disponível (.pdf) junto com os códigos fonte em: https://github.com/Natanf0/gauss-jacobi-c