I recently learned about multi-grid methods and was trying to use them in an optic flow setting. I wasn't getting the speed-up that was suggested by a paper on the subject, so I figured that perhaps my reduction or prolongation operators were wrong. To test their correctness I decided to try and solve some simpler problems: a 1D Poisson problem; a 2D Poisson problem; and a 2D non-linear poison like problem. In all cases I used a Gauss-Siedel relaxation. In all my tests I simply ran a multi-grid solver (w-cycle) and then used only the relaxation (Gauss-Siedel) to solve the problem to the same residual.
For the linear problems (Poisson) I am not convinced that MG is the fastest approach. But in the 1D case, it was possible to get speed-ups of 3.3, 14.2, and 38 for problem sizes of 256, 512, and 1024 respectively.
For the 2D linear problem, on sizes of 64x64, 128x128, and 256x256 the speed-ups were 4.8, 14.6, and 51. I have yet to try and solve one of these sparse problems with a generic sparse linear equation solver, but I think the MG solver would be faster. For example, the 256^2 problem took roughly 3.5 seconds, a 512^2 takes about 18.2, and 1024^2 takes roughly 1 minute. Keep in mind the 1024^2 problem is a 1e6 x 1e6 linear system with a million unknowns.
For the nonlinear 2D problem (which is most similar to my target application) the gains were even more apparent. For problems of size 32x32 the Gauss-Siedel method with frozen coefficients had extremely poor convergence. In the same problem size it was possible to see 1000-fold speed-ups. Since the Gauss-Siedel solver alone was extremely slow, I was not able to get results on any larger systems. The non-linear versions also had some strange behaviour, where the residual of the equation system would actually increase after prolonging the coarse grid solution (this would of course decrease after the pre-smoothing for the next iteration).
Back to the optic flow problem. Confident after seeing the improvements in these toy examples, I went back to the optic flow problem. I think that the prolongation and restriction operators in this case are implemented correctly. I didn't see the speed-ups mentioned in the literature (close to 500 or so vs. a Gauss-Siedel solver); mine were closer to 15 or so. The good news is that a single wcycle gives almost real-time performance (as in the paper), where it is possible to get roughly 1 frame-per-second on 400x300 images.
