Ciência-IUL
Publicações
Descrição Detalhada da Publicação
A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks
Título Revista
Future Generation Computer Systems
Ano (publicação definitiva)
2022
Língua
Inglês
País
Países Baixos (Holanda)
Mais Informação
Web of Science®
Scopus
Google Scholar
Abstract/Resumo
Methods based on Monte Carlo for solving linear systems have some interesting properties which make them, in many instances, preferable to classic methods. Namely, these statistical methods allow the computation of individual entries of the output, hence being able to handle problems where the size of the resulting matrix would be too large. In this paper, we propose a distributed linear algebra solver based on Monte Carlo. The proposed method is based on an algorithm that uses random walks over the system’s matrix to calculate powers of this matrix, which can then be used to compute a given matrix function. Distributing the matrix over several nodes enables the handling of even larger problem instances, however it entails a communication penalty as walks may need to jump between computational nodes. We have studied different buffering strategies and provide a solution that minimizes this overhead and maximizes performance. We used our method to compute metrics of complex networks, such as node centrality and resolvent Estrada index. We present results that demonstrate the excellent scalability of our distributed implementation on very large networks, effectively providing a solution to previously unreachable problem instances.
Agradecimentos/Acknowledgements
--
Palavras-chave
Matrix inverse,Monte Carlo,Distributed computation,Network metrics
Classificação Fields of Science and Technology
- Ciências da Computação e da Informação - Ciências Naturais
Registos de financiamentos
Referência de financiamento | Entidade Financiadora |
---|---|
UIDB/50021/2020 | Fundação para a Ciência e a Tecnologia |
PID2019-107255GB | Generalitat de Catalunya |
PID2019-107255GB | Spanish Ministry of Science and Technology |
Contribuições para os Objetivos do Desenvolvimento Sustentável das Nações Unidas
Com o objetivo de aumentar a investigação direcionada para o cumprimento dos Objetivos do Desenvolvimento Sustentável para 2030 das Nações Unidas, é disponibilizada no Ciência-IUL a possibilidade de associação, quando aplicável, dos artigos científicos aos Objetivos do Desenvolvimento Sustentável. Estes são os Objetivos do Desenvolvimento Sustentável identificados pelo(s) autor(es) para esta publicação. Para uma informação detalhada dos Objetivos do Desenvolvimento Sustentável, clique aqui.