Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations

Résumé : Dans cet article, nous améliorons le travail de Aupy et al. sur les algorithmes à plusieurs étages optimaux pour le calcul d'adjoints, avec deux niveaux de mémoire disponibles. L'algorithme optimal précédent avait un temps d'exécution quadratique. Ici, avec une analyse de la solution optimale, nous proposons un algorithme optimal en temps constant, avec précalculs. Nous proposons également un algorithme asymptotiquement optimal pour la version en ligne du problème, lorsque la taille du graphe adjoint n'est pas connue à l'avance. Ces algorithmes reposent sur la preuve que les solutions optimales pour le calcul d'adjoint sont périodiques. Nous conjecturons la formule close de cette période. Enfin, nous évaluons la vitesse de convergence du ratio d'approximation pour le problème en ligne, à travers une campagne de simulations. a travers une campagne de simulations.
Type de document :
Rapport
[Research Report] RR-8822, INRIA Grenoble - Rhône-Alpes. 2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01244584
Contributeur : Julien Herrmann <>
Soumis le : mercredi 16 décembre 2015 - 23:50:36
Dernière modification le : jeudi 4 octobre 2018 - 16:24:06
Document(s) archivé(s) le : jeudi 17 mars 2016 - 11:01:23

Fichiers

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

Identifiants

  • HAL Id : hal-01244584, version 1

Collections

Citation

Guillaume Aupy, Julien Herrmann. Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations. [Research Report] RR-8822, INRIA Grenoble - Rhône-Alpes. 2015. 〈hal-01244584〉

Partager

Métriques

Consultations de la notice

282

Téléchargements de fichiers

87