6.1.3 : Comment éviter le problème de l'échelle ? (WIP)
Il faut favoriser l'utilisation d'algorithmes à faible complexité, ou modifier des algorithmes existant pour casser leur complexité.
Une méthode qui permet de réduire la complexité de certains algorithmes consiste à trier les données à traiter.
Pistes pour changer la complexité d'un algorithme
Lorsque le nombre d'éléments à traiter devient grand, il est alors utile de déterminer précisément quelles sont les données vraiment utiles au calcul. Il faut, d'une manière générale, réduire la quantité de données à traiter tout en garantissant leur pertinence.Trier les données
Le tri de données est un cas classique en simulation, par exemple lorsque des particules interagissent entre elles (voir section 6.2).En fonction de la complexité du problème, un tri simple des données peu suffire (voir section 6.3) :
Dans des cas plus complexes, on peut avoir recours à un tri explicite par arbre :
- Octree ou quadtree (voir section 6.2.3)
- Kd-tree
Diviser pour régner
Cette méthode est très utile lorsqu'un algorithme peu se décomposer en plusieurs autres sous-algorithmes qui ont des complexités différentes. Dans ce cas, il est intéressant de chercher une combinaison qui favorise l'algorithme qui a la plus petite complexité, ce qui aura pour effet de diminuer la complexité globale de l'algorithme de départ.Cette méthode est notamment utilisée dans la multiplication de matrice rapide (voir section 6.4).
Projeter le problème dans un espace plus petit
C'est un cas très utile, lorsque l'on doit calculer les $M$ premières valeurs propres d'une matrice de taille $N\times N$ , surtout si $M << N$ .Dans ce cas, un calcul explicite de toutes les valeurs propres serait bien trop coûteux en temps de calcul. Mais comment faire pour calculer les bonnes valeurs propres ?
La méthode de Krylov a été conçue dans ce but : projeter la matrice de départ $N\times N$ dans une matrice bien plus petit, typiquement de taille $2M\times 2M$ . L'avantage est que cette méthode garantie que les $M$ plus grandes (et les $M$ plus petites) valeurs propres de la matrice de départ se retrouvent dans la matrice projetée.
Une fois que cette projection est faite, il suffit d'utiliser un algorithme classique de calcul de valeurs propres, mais sur la petite matrice, ce qui sera bien plus rapide.
Exploiter les symétries du problème
Par exemple, dans le monde du traitement du signal, lorsqu'on peut faire la supposition qu'un signal est périodique, il est possible d'exploiter les propriétés magiques de la FFT (complexité $O\left(N \log N \right)$ pour transformer des convolutions (complexité $O\left(N\times M\right)$ en sandwiches FFT + multiplication + iFFT (complexité $O\left(N \log N \right)$ , ce qui est très intéressant quand $M$ grand.
Plus généralement, dès que l'on sait qu'un jeu de données possède une certaine structure ou une certaines symétrie,
cette propriété peut souvent être exploitée pour diminuer le temps de calcul a minima d'un facteur constant,
et parfois changer la complexité asymptotique.
 |
| On pourrait aussi parler des BVH (Bounding Volume Hierarchy) dans blender qui permettent de trier les objets et les vertices de ceux-ci afin d'optimiser le rendu, et il ya même des algos pour créer des BVH vectorisés... |
Nous examinerons dans la suite des exemples de problèmes à résoudre avec différents algorithmes.