Description (générale)

Un "spectre multifractal" est une façon de résumer des statistiques particulières, concernant la régularité des données. Les multi-fractales sont maintenant utilisées dans de nombreux domaines de physique, biologie, finance, géologie... Cet algorithme calcule le “spectre” très vite. Il peut aussi le mettre à jour quand de nouvelles données sont disponibles.

Description (détaillée)

Un algorithme est présenté, capable de mettre à jour le spectre multi-fractal d'une série temporelle en temps constant quand de nouvelles données arrivent. La transformée discrète en ondelettes de la série temporelle est d'abord mise à jour pour les nouvelles valeurs. Ceci est effectué de façon optimale en ce qui concerne la réutilisation des calculs précédents, en temps constant O(L), avec L le nombre de niveaux de décomposition. Le spectre multi-fractal est ensuite lui-aussi mis à jour en temps constant. De nouveaux pré-calculs sont présentés afin d'accélérer encore le procédé. Les 2^L alignements de données possibles sont tous pris en compte successivement au cours des mises à jour incrémentales. L'estimation du spectre qui en résulte est plus stable, comparée à la méthode actuelle basée sur transformée discrète en ondelettes qui n'utilise qu'un seul alignement. L'estimation reste aussi précise, tout en étant plus rapide. Cet algorithme est adapté pour des mises à jour en temps réel d'une série temporelle.

Un article en "pre-print" est disponible. Il décrit en détails le fonctionnement de l'algorithme.

Code source

Le code source qui implémente cet algorithme peut être téléchargé ici. Merci de consulter l'historique des rêvisions si vous dêsirez obtenir une version plus ancienne.

Les programmes suivants sont inclus:

• incremfa: Procède à une analyse sur un fichier de données. Entrez "incremfa" sans paramètres pour obtenir de l'aide. Ce programme calcule le spectre sur l'intégralité du fichier de données. La phase d'initialisation utilise la version non-incrémentale de l'algorithme, et le reste des points est pris en compte incrémentalement.
• numericalStability: Code pour l'expérience correspondante dans l'article. 30 exécutions indépendantes de 10 millions de mises à jour sont effectuées. Le but est de mesurer la dérive due aux calculs flottants lors des mises à jours incrémentales, par rapport à la version non-incrémentale.
• performanceTest: Code pour l'expérience correspondante dans l'article. Différentes configurations sont testées avec le nombre de niveaux de décomposition et la taille du plus haut niveau. Le temps nécessaire pour effectuer une mise à jour est mesuré pour les 2 versions de l'algorithme (incrémentale et non-incrémentale). Cette mesure peut varier d'une mise à jour à l'autre en fonction du système d'exploitation multi-tâches. Les mesures sont donc moyennées sur un large nombre de mises à jour.
• performanceTestReducedNq: Idem, mais en réduisant le nombre d'exposants à q=-5..5 au lieu de q=-10..10.
• precisionExperiment: Test de la précision de l'analyse multi-fractale, en utilisant des séries mono-fractales dont le résultat est connu: H=0.5 pour un mouvement Brownien, H=1.0 pour du bruit "rose" intégré. L'influence de plusieurs paramètres est testée: nombre de niveaux de décomposition, taille du plus haut niveau, moyennage des résultats sur différents alignements, pondération, etc. La moyenne et la variance de chaque résultat sont calculées sur 30 exécutions indépendantes.
• memVSCPUValidation: Teste les différences entre les versions de l'algorithme utilisant principalement la mémoire (plus rapide) ou le CPU (plus lent). Ces différences apparaissent en raison du fait que le CPU utilise 80 en interne pour représenter les nombres flottants, alors que les stocker en mémoire se fait sur 64 bits. Il est possible d'utiliser un type long double pour la mémoire, mais malheureusement ceci entraine de sévères pénalités de performances sur certains systèmes, qui annule l'avantage de la version mémoire par rapport à la version CPU de l'algorithme. Les différences ne sont non-négligeables que pour les grands q-exposants négatifs.

Historique des révisions

Plusieurs versions du code se sont succédées depuis la rédaction de l'article en preprint. Le code original correspond à la version 1.0, il est nécessaire pour reprosuire exactement les expériences décrites dans l'article. La version 1.2 peut ne pas donner les mêmes résultats en raison de la différence d'encodage des nombres flottants sur 64bits ou 80bits (cf. ce commentaire).

• 1.3: Nettoyage du code et dépôt de sources.
• 1.2:
  • L'erreur moyenne a été remplacée par le coefficient de correlation, qui est un indicateur plus fiable pour la qualité de l'estimation des h(q) par régression exponentielle. La détection des valeurs NaN a été implémentée, donnant lieu à une correlation de 0.0.
  • La version mémoire de l'algorithme a été implémentée, et est maintenant le défaut. Ceci entraîne une amélioration de performance de 25% à 30% par rapport aux versions précédentes.
  • Nettoyage du code, rendant plus facile la spécification des q-exposants considérés.
• 1.1: Ajout du calcul de la moyenne du carré de l'erreur commise lors de la régression exponentielle des h(q).
• 1.0: Code initial, correspondant à l'article en preprint.