Fast hierarchical algorithms for generating Gaussian random fields

Abstract : Low-rank approximation (LRA) techniques have become crucial tools in scientific computing in order to reduce the cost of storing matrices and compute usual matrix operations. Since standard techniques like the SVD do not scale well with the problem size N, there has been recently a growing interest for alternative methods like randomized LRAs. These methods are usually cheap, easy to implement and optimize, since they involve only very basic operations like Matrix Vector Products (MVPs) or orthogonalizations. More precisely, randomization allows for reducing the cubic cost required to perform a standard matrix factorization to the quadratic cost required to apply a few MVPs, namely O(r × N^2) operations where r is the numerical rank of the matrix. First of all, we present a new efficient algorithm for performing MVPs in O(N) operations called the Uniform FMM (ufmm). It is based on a hierarchical (data sparse) representation of a kernel matrix combined with polynomial interpolation of the kernel on equispaced grids. The latter feature allows for FFT-acceleration and consequently reduce both running time and memory footprint but has implications on accuracy and stability. Then, the ufmm is used to speed-up the MVPs involved in the randomized SVD, thus reducing its cost to O(r^2 × N) and exhibiting very competitive performance when the distribution of points is large and highly heterogeneous. Finally, we make use of this algorithm to efficiently generate spatially correlated multivariate Gaussian random variables.
Complete list of metadatas

Cited literature [48 references]  Display  Hide  Download

https://hal.inria.fr/hal-01228519
Contributor : Pierre Blanchard <>
Submitted on : Thursday, February 18, 2016 - 3:19:55 PM
Last modification on : Thursday, January 11, 2018 - 6:22:35 AM

File

RR-8811.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01228519, version 2

Citation

Pierre Blanchard, Olivier Coulaud, Eric Darve. Fast hierarchical algorithms for generating Gaussian random fields. [Research Report] 8811, Inria Bordeaux Sud-Ouest. 2015. ⟨hal-01228519v2⟩

Share

Metrics

Record views

701

Files downloads

640