Ultra-Scalable Randomized Algorithms for Current and Future High Performance Supercomputers (URA-HPC)
Type: National Project Project
Duration: from 2023 Feb 01 to 2026 Jan 31
Financed by: FCT
Prime Contractor: R - INESC-ID Lisboa (Other) - Lisboa, Portugal
Many problems of paramount importance in diverse fields can be described by matrices and their direct solution involves the computation of some function over these matrices. Examples are: the solution of integer or fractional partial differential equations; analysis of complex networks; etc. For many real instances , classic algorithms cannot be employed as they do not scale well to solve these problems. We aim to make fundamental contributions to a method for computing matrix functions based on their Neumann series, consisting of weighted sums of powers of the matrix. We use a Monte Carlo algorithm where a matrix to the power k is computed using random walks of length k over the matrix. Monte Carlo methods have the preeminent facet of being embarrassingly parallel, achieving a high degree of efficiency on a parallel system. In our method, each walk is independent from one another and can be computed completely in parallel. This class of algorithms positions itself as the most appropriate to exploit the computational power of new exascale machines to the fullest. A second, crucially important feature of this Monte Carlo method, that sets it apart from the classic algorithms, is that it allows calculating individual entries of the result, avoiding the computation of the entire matrix. While real-world matrices are typically sparse, the result matrix will, in general, be dense. Thus, for large problems the representation of the output matrix in memory is in itself unfeasible, rendering its computation using classic methods impractical. With our approach we can, for instance, compute the trajectory of a single state variable in a dynamic system (eg, the voltage of a node in an electrical network) or the communicability of a single node in a network. In yet another research avenue, we have found that using this Monte Carlo approach with some modifications we are able to efficiently solve systems with derivatives of fractional order. Fractional calculus has a wide range of practical applications, and has not yet seen a more widely spread adoption due to its intrinsic computational difficulty. Our expectation is that our idea can have a broad impact and be a significant contribution from this project, and we plan to apply it to both Magnetic Resonance Imaging (MRI) and the modeling of chemical reactions.