next up previous contents
suivant: Couplage du gradient topologique monter: Complexité des algorithmes précédent: Transformée de cosinus discrète   Table des matières

Gradient conjugué préconditionné

La solution des différents problèmes étudiés provient alors de la résolution d'un problème perturbé. Mais il faut noter que la perturbation est finalement assez faible au sens où la conductivité $ c$ est constante, sauf dans une zone généralement négligeable de l'image.

Le problème perturbé qu'il faut résoudre peut s'écrire sous la forme

$\displaystyle A(c)u = B,$ (2.57)

$ u$ est l'inconnue. Nous avons vu que le problème (2.57) se résout très rapidement dans le cas $ c$ constant. L'idée est de préconditionner le cas où $ c$ n'est pas constant à l'aide du cas constant. Le problème (2.57) est équivalent au problème suivant:

$\displaystyle \left[A(c_0)^{-1}A(c)\right] u = \left[ A(c_0)^{-1}B \right].$ (2.58)

L'intérêt est que pour $ c$ proche de $ c_0$ , ce qui est généralement le cas, la matrice du système à inverser est proche de l'identité, ce qui accélère la résolution. En utilisant un gradient conjugué préconditionné de cette façon, nous pouvons espérer rester en $ \mathcal{O}(n.\log(n))$ opérations pour résoudre le problème perturbé. Tous les tests numériques que nous avons réalisés, en petite comme en grande dimension, confirment cette complexité théorique.

L'avantage indéniable est que cela permet de traiter des films en temps réel, à condition toutefois de découper le film en séquences courtes (de l'ordre d'une à deux secondes) pour pouvoir utiliser une approche tri-dimensionnelle sans retarder la diffusion de plus que quelques secondes. Notre approche permet également de traiter des images de grande taille en un temps quasiment négligeable (par exemple, une image $ 1600\times 1200$ pixels en moins d'une seconde avec un code en c++).


next up previous contents
suivant: Couplage du gradient topologique monter: Complexité des algorithmes précédent: Transformée de cosinus discrète   Table des matières
Retour à la page principale