Exportar Publicação
A publicação pode ser exportada nos seguintes formatos: referência da APA (American Psychological Association), referência do IEEE (Institute of Electrical and Electronics Engineers), BibTeX e RIS.
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
F. Magalhães et al., "A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks", in Future Generation Computer Systems, vol. 127, pp. 220-230, 2022
@article{magalhães2022_1724526469271, author = "Magalhães, F. and Monteiro, J. and Acebron, J. A. and Herrero, J. R.", title = "A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks", journal = "Future Generation Computer Systems", year = "2022", volume = "127", number = "", doi = "10.1016/j.future.2021.09.014", pages = "220-230", url = "https://www.sciencedirect.com/journal/future-generation-computer-systems" }
TY - JOUR TI - A distributed Monte Carlo based linear algebra solver applied to the analysis of large complex networks T2 - Future Generation Computer Systems VL - 127 AU - Magalhães, F. AU - Monteiro, J. AU - Acebron, J. A. AU - Herrero, J. R. PY - 2022 SP - 220-230 SN - 0167-739X DO - 10.1016/j.future.2021.09.014 UR - https://www.sciencedirect.com/journal/future-generation-computer-systems AB - 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. ER -