The URA-HPC project, an acronym for Ultra-Scalable Randomized Algorithms for Current and Future High Performance Supercomputers, is an FCT sponsored project (reference 2022.08838.PTDC) starting on February 1st 2023 with a duration of 3 years.
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. 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.