Dissertação

A Parallel Algorithm based on Monte Carlo for Computing the Inverse and other Functions of a Large Sparse Matrix EVALUATED

Atualmente, a inversão de matrizes desempenha um papel importante em várias áreas do conhecimento. Por exemplo, quando analisamos características específicas de uma rede complexa como a centralidade do nó ou comunicabilidade. Por forma a evitar a computação explícita da matriz inversa, ou outras operações computacionalmente pesadas sobre matrizes, existem vários métodos eficientes que permitem resolver sistemas de equações algébricas lineares que têm como resultado a matriz inversa ou outras funções matriciais. Contudo, estes métodos, sejam eles diretos ou iterativos, têm um elevado custo quando a dimensão da matriz aumenta. Neste contexto, apresentamos um algoritmo baseado nos métodos de Monte Carlo, como uma alternativa à obtenção da matriz inversa e outras funções duma matriz esparsa de grandes dimensões. A principal vantagem deste algoritmo é o facto de permitir calcular apenas uma linha da matriz resultado, evitando explicitar toda a matriz. Esta solução foi paralelizada usando OpenMP. Entre as versões paralelizadas desenvolvidas, foi desenvolvida uma versão escalável, para as matrizes testadas, que usa a diretiva omp declare reduction.
métodos de Monte Carlo, OpenMP, algoritmo paralelo, operações sobre uma matriz, redes complexas

Novembro 9, 2016, 16:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

José Carlos Alves Pereira Monteiro

Departamento de Engenharia Informática (DEI)

Professor Associado

ORIENTADOR

Juan António Acebron de Torres

ISCTE

Professor Auxiliar