Prova de Doutoramento do aluno Nicolas Lee Guidotti
Área: Engenharia Informática e de Computadores
Título da Tese: Efficient Stochastic Algorithms for Computing Matrix Functions
Local da Prova: Anfiteatro PA-3 (Piso -1 do Pavilhão de Matemática) do IST
Data: 20/10/2025
Hora: 14h00
Abstract: Matrix functions arise naturally in many scientific and engineering applications, such as the solution of differential equations, the analysis of complex networks, or lattice quantum chromodynamics. Yet, computing a function f over a large matrix A is not an easy task. Direct methods are prohibitively expensive, while iterative methods only exist for f(A)b and may converge slowly depending on the spectrum of A and the function f. In recent years, randomisation has become a popular tool for accelerating or even replacing classical methods in Linear Algebra, greatly reducing their computational cost. In this thesis, we explored and developed new randomised methods for computing matrix functions. Our study started with a randomised Krylov method for constructing a well-conditioned, but not necessarily orthogonal basis for the Krylov subspace, working with only the random sketches of the basis. This greatly reduced the computational cost while preserving the accuracy and stability even for ill-conditioned problems. In fact, the randomised method often converged faster than its classical counterpart. In the second part, we developed the RandFunm algorithm that randomly samples entire rows and columns of the matrix as a way to approximate matrix functions using the power series. This contrasts sharply with existing Monte Carlo methods, which only work with one entry at a time. As a result, RandFunm is significantly more accurate than the original approach. Our numerical results show that RandFunm is particularly effective for the analysis of large networks. In the last part, we proposed a new stochastic method for solving time-fractional differential equations that describe anomalous diffusion. It consists in simulating random paths of a continuous-time Markov chain, whose sojourn times follow a Mittag-Leffler probability distribution. Our numerical experiments include a rigorous analysis of the error as well as a performance comparison against classical algorithms. This thesis also studied the parallel scalability of the numerical methods for high-performance systems.