Sparsified Randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation

Abstract: Sparsified Randomization Monte Carlo (SRMC) algorithms introduced in our recent paper for solving systems of linear algebraic equations are extended to construct the SVD-based randomized low rank approximations for large matrices. We suggest some efficient implementations of SRMC based on low rank approximations, and give different applications. In particular, an important application we present in this paper is a fast simulation algorithm for a randomized approximation of non-homogeneous random fields based on a discrete version of the Karhunen-Loéve expansion. We present two examples of non-homogeneous random field simulation which include a long-correlated Lorenzian random field and the fractional Wiener process. Another application we deal in this paper concerns the randomized solvers for large linear systems. We suggest a hybrid method which combines SRMC with an algorithm for solving boundary integral equations based on a separation representation of the kernel. This method is illustrated in this paper by solving a 2D boundary integral equation from potential theory governing the Dirichlet problem for the Laplace equation. [Copyright &y& Elsevier]