Fast hierarchical algorithms for generating Gaussian random fields

Résumé : Les approximations de rang faible (LRA) sont devenus des outils fondamentaux en calcul scientifique en vue de réduire les coûts liés au stockage et aux opérations matricielles. Le coût des méthodes standards comme la SVD croît très rapidement avec la taille du problème N, c'est pourquoi des méthodes alternatives comme les approches aléatoires (i.e. basées sur la projection ou la sélection de colonnes/l'échantillonnage aléatoire) se popularisent. Ces méthodes sont en général peu coûteuses et facile à implémenter et optimiser, car elles ne mettent en oeuvre que des opérations matricielles simples comme des produits ou des orthogonalisations. Plus précisemment, les LRA aléatoires permettent de réduire le coût cubique en N des méthodes standards de factorisation au coût quadratique nécessaire à la réalisation de quelques produits matrices vecteurs, i.e., O(r × N^2) opérations où r est le rang numérique de la matrice. Dans un premier temps, nous présentons un algorithme efficace pour réaliser des MVPs en O(N) opérations, que nous appelons Uniform FMM (ufmm). Il est basé sur la combinaison d'une représentation hiérachique d'une matrice noyau et l'interpolation polynomiale du noyau associé sur une grille régulière (uniforme). Cette dernière propriété permet une accélération par FFT réduisant ainsi le temps de calcul et la consommation mémoire mais a des répercussions sur la précision et la stabilité de l'algorithme. Ensuite, la ufmm est utilisée pour accélerer les MVPs intervenants dans la SVD aléatoire (i.e., SVD par projection aléatoire) diminuant son coût asymptotique à O(r^2 × N). La méthode est particulièrement compétitive pour des distributions de points hétérogènes. Enfin, nous utilisons cet algorithme pour générer des champs de variables Gaussiens de manière efficace.


https://hal.inria.fr/hal-01228519
Contributeur : Pierre Blanchard <>
Soumis le : jeudi 18 février 2016 - 15:19:55
Dernière modification le : vendredi 16 septembre 2016 - 15:18:23

Fichier

RR-8811.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

323

Téléchargements du document

178