Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10071/27154
Autoria: | Magalhães, F. Monteiro, J. Acebron, J. A. Herrero, J. R. |
Data: | 2022 |
Título próprio: | A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks |
Título da revista: | Future Generation Computer Systems |
Volume: | 127 |
Paginação: | 220 - 230 |
Referência bibliográfica: | Magalhães, F., Monteiro, J., Acebron, J. A., & Herrero, J. R. (2022). A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks. Future Generation Computer Systems, 127, 220-230. http://dx.doi.org/10.1016/j.future.2021.09.014 |
ISSN: | 0167-739X |
DOI (Digital Object Identifier): | 10.1016/j.future.2021.09.014 |
Palavras-chave: | Matrix inverse Monte Carlo Distributed computation Network metrics |
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. |
Arbitragem científica: | yes |
Acesso: | Acesso Aberto |
Aparece nas coleções: | CTI-RI - Artigos em revistas científicas internacionais com arbitragem científica |
Ficheiros deste registo:
Ficheiro | Tamanho | Formato | |
---|---|---|---|
article_83360.pdf | 585,67 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.