Estratégias para implementação paralela distribuída da dissecação aninhada cartesiana. - Fernandes, Hilton Garcia (1998)
A solução de sistemas de equações lineares é um problema que surge em vários algoritmos numéricos; neles a esparsidade das matrizes de coeficientes do sistema permite que se tratem sistemas de ordem muito elevada. Os métodos iterativos em geral são preferidos devido ao fato de que os métodos diretos, em sua versão mais simples, tendem a introduzir um número inaceitável de elementos não nulos na matriz do sistema, o que é chamado preenchimento, ou fill-in. No entanto, através de várias propriedades do grafo associado à matriz de coeficientes do sistema linear, é possível se reduzir drasticamente o preenchimento. O método de Cholesky, um algoritmo muito eficiente para a solução de sistemas lineares cuja matriz é simétrica e definida positiva, é sofisticado com técnicas da teoria dos grafos, em um algoritmo projetado especialmente para sistemas paralelos distribuídos. Faz-se aqui uma apresentação completa de estratégias para a implementação paralela distribuída do algoritmo da dissecação aninhada cartesiana para a ordenação de sistemas lineares esparsos, uma das fases da solução de sistemas lineares esparsos onde tem havido mais pesquisas, pois ela fornece informações sobre a organização do sistema para todas fases posteriores. O algoritmo e a estratégia proposta para sua implementação são então analisados.