Complexitée des algorithmes

Complexitée des algorithmes

Algorithmes explicites

Dans ce document nous ne rappelons pas la construction du schéma Tacite, qui est présenté dans [26] et que nous avons utilisé tout au long de ce travail (voir [10, 8, 9, 4]). Nous nous contentons de reporter ici les résultats de l’analyse des schémas, qui sont présentés dans les figures 11.1 et 11.2 dans lesquelles K représente le nombre de constituants. Par le terme “évaluations des lois de fermetures”, nous entendons tous les calcul des fonctions pression et glissement ainsi que leur dérivées. Comme nous ne connaissons par la complexité de ces opérations (qui impliquent généralement des méthodes de Newton), nous ne pouvons rentrer dans le détail de ces calculs et nous nous contentons de comparer le nombre d’appels `a ces lois.On constate que le nombre d’évaluations des lois de fermeture est sensiblement le même, bien que l’avantage reviennent tout de même à la méthode de relaxation.C’est bien naturel car la méthode de relaxation ne nécessite de calcul de dérivée que pour le calcul des coefficients de relaxation a et b alors que la méthode Tacite nécessite de calculer la Jacobienne complète du système. La différence fondamentale entre les deux schémas est le nombre d’opérations qui évolue comme K3 dans le schéma Tacite et comme K dans le schéma de relaxation. Le gain en nombre d’opération évolue alors comme K2 , ce qui est considérable (voir figure 11.3). La raison de cette différence est bien évidement dans le fait que la méthode Tacite nécessite une décomposition en éléments propres, dont la complexité varie selon le cube du nombre de constituants.

Algorithmes semi-implicite linéaires

Nous comparons dans les figures 11.4 et 11.5 la complexité des schémas semi-implicite linéaires relaxation et Tacite. Rappelons que la complexité de ces schémas implicites dépend du nombre de mailles noté I.On constate que le nombre d’évaluations des lois de fermeture est sensiblement le même. La différence fondamentale est le nombre d’opérations qui évolue comme K3 dans le schéma Tacite et comme K2 dans le schéma de relaxation. On constate que la complexité du schéma de relaxation a augmenté (dans le schéma explicite, elle évoluait comme K). En réalité, c’est bien naturel puisqu’on doit construire le système linéaire à inverser et donc calculer de l’ordre de K2 termes. Le gain en nombre d’opération par rapport au schéma Tacite évolue alors comme K, ce qui est très intéressant (voir figure 11.6). Notons que nous présentons par la suite les résultats du schéma pour seulement 2 constituants, ce qui ne permet pas de constater des gains très intéressants. Ce ne sera pas le cas dans la pratique, auquel cas on utilise entre 5 et 10 constituants. Les gains seront alors plus attractifs pour la méthode de relaxation.

Conclusion

Nous avons analysé la complexité des schémas de relaxation explicite et semi-implicite linéaire. Comparée à celle du schéma Tacite, le schéma de relaxation s’avère peu couteux ˆ et le gain varie comme K2 pour le schéma explicite et comme K pour le schéma semi-implicite linéaire, avec K le nombre de constituants. Dans la pratique, cet avantage pourrait être très intéressant. Rappelons enfin que la méthode de relaxation présente souvent des pas de temps deux fois plus grands que la méthode Tacite (liée à une diffusion numérique importante dans le schéma Tacite) et que cela réduit encore le temps de simulation.