What is the advantages of successive over-relaxation and conjugate gradient methods over each other? When should I use one of them over the other? Here the discussion is limited to solving linear systems, since to my knowledge conjugate gradient method could also be extended to nonlinear programming.
Asked
Active
Viewed 904 times
1 Answers
0
Basically this boils down to: how long does a step take and how many steps are required?
In CG, the number of steps required scales with the square root of the condition number of the matrix. The vast majority of the work in a step is spent on one multiplication by the original matrix.
In SOR, the vast majority of the work in one step is spent solving a triangular system and multiplying by another triangular matrix. The overall sparsity structure of these two triangular matrices is the same as that of the original matrix, so an SOR step and a CG step will take about the same amount of time. In SOR, the number of steps required in the worst case is proportional to $\frac{-1}{\log(1-1/k)} \approx k$ for large condition numbers $k$. Thus SOR will typically perform worse than CG, except in certain special problems where it is particularly appropriate. (My understanding is that SOR performs rather well in solving Poisson-type equations.)
Ian
- 101,645