next up previous contents
Next: Coupling between the topological Up: Complexity and speeding up Previous: Discrete cosine transform   Contents

Preconditioned conjugate gradient

Then, the solution of all previously detailed problems comes from the resolution of a perturbed problem. For the last resolution of a direct problem with a non constant coefficient $ c$ , we can rewrite the problem in the following way:

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

where $ u$ is the unknown image. If $ c$ is constant, equation (2.57) is easy to solve. The idea is to precondition equation (2.57) with the DCT solver used in the first resolution. Problem (2.57) is equivalent to

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

As $ c$ is close to $ c_0$ ($ c$ is indeed equal to $ c_0$ , except in a negligible part of the domain), the system matrix $ [A(c_0)^{-1}A(c)]$ is close to the identity operator, and the resolution of (2.58) is then easy: we use a preconditioned conjugate gradient (PCG) method to solve this problem. As the coefficient $ c$ is close to $ c_0$ , we can expect a $ \mathcal{O}(n.\log(n))$ complexity for the resolution of the perturbed problem. The numerical experiments clearly confirm this complexity, both for small and large problems.

The main advantage is that it allows us to process images in a very short time (e.g. $ 1600\times 1200$ images in less than one second) and movies in real time (provided the movie is split into short sequences of a few seconds) with a c++ code.

next up previous contents
Next: Coupling between the topological Up: Complexity and speeding up Previous: Discrete cosine transform   Contents
Back to home page