Mesh deformation is a key point in fluid structure interaction problems. The efficiency of such simulations relies on the efficiency of the mesh deformation algorithms used for as long periods of time as possible without degenerating the mesh. Many solutions are well described in the literature, from those based on the solutions of elliptic PDEs to those based on both explicit and implicit interpolations [3]. The approach considered here is based on the solution of an algebraic linear system raised from Radial Basis Function (RBF) interpolation. At an extreme scale, the resolution of such linear systems is very expensive [1]. The present work aims to speed-up the solving of such systems by using randomized linear algebra [2]. Over the past decade, a new paradigm has emerged introducing randomization to speed-up linear algebra operations [2]. The efficiency of such an approach can reach linear complexity O(N) regarding the problem size and this has been confirmed on several dense linear systems from integral equations, statistics, and machine learning. This talk investigates the extension of this approach to complex systems resulting from Fluid-Structure interaction problems that are sparse and ill-conditioned [3]. The focus will be on how to speed-up the algebraic solvers used to deform the mesh in FSI simulations. 2D and 3D applications will be presented to assess the new paradigm.