I have a collection of large sparse matrices of the order of 1 million x 1million and above obtained from CFD based application problems. The matrix A (in CSR) is normalised with respect to the diagonal and is non-symmetric. I am solving the Ax=b system using SOR+BiCGSTAB and ILU(0)+BiCGSTAB. But when I tried SSOR+BiCGSTAB it showed a faster convergence than ILU(0)+BiCGSTAB. I expected it to be slower. And in all the cases it guaranteed convergence. Why this is happening ? Is it because the matrix A is highly sparse so ILU(A)=LU - E, where the error matrix (E) could be significant ? Or does ILU(0) always give superior convergence when compared to SSOR preconditioner ?
The direct answer is "no": When you have an unsymmetric matrix, your preconditioner does not need to be symmetric.
Regarding the other questions, it has been demonstrated several times that SSOR, respectively SGS, is a good preconditioner for flow problems and comparable with ILU(0) in performance. One example is: https://www.researchgate.net/publication/258795685_Preconditioning_for_modal_discontinuous_Galerkin_methods_for_unsteady_3D_Navier-Stokes_equations
Essentially, for a good ordering of the unknowns following the characteristic flow of information, SGS exploits this flow.
Article Preconditioning for modal discontinuous Galerkin methods for...
No at all! There is no necessity the matrix being symmetric to apply SSOR, or SGS (Symmetric Gauss-Seidel). Here the adjective 'symmetric' refers to the fact that a forward swap is first applied and after a backward swap for the next iteration. That is, first one performs an iteration as
x(k+1) = ( D - E )-1 ( F x(k) + b )
and after this one
x(k+1) = ( D - F )-1 ( E x(k) + b )
where D is the diagonal part of A and -E and -F are the strict lower and upper parts, respectively, of the coefficient matrix A; b is the right hand side vector.
This is the SGS case, the SSOR case can be defined similarly by introducing the relaxation factor. Although when SSOR is used as preconditioner no great improvement has been observed compared with plain SGS (I think this is mentioned in the Saad's book about Krylov subspace methods, but I do not remember the exact place, I am sorry. Although I have observed this fact several times), then it is not very worthy to spent much time in computing a good relaxation parameter.
About the superiority of SGS over ILU(0), I shall not dare to claim that this is always the case. I have also observed this phenomenon not only with flow problems but also while working with the Maxwell's equations discretized by finite elements and generally this happens. Unfortunately I have not a formal explanation, it is only a fact I have observed.
You can even improve the convergence rate of the preconditioned system if a reordering is first applied to the coefficient matrix. I have found the Reverse Cuthill-McKee can considerably accelerate the convergence rate. But again, even after reordering SGS behaves better than ILU(0), when this was the case before reordering.
ILU preconditioning starts beating SGS when some fill-in is allowed, this is even more drastic after reordering is applied. MILU can be useful when dealing with a system coming form the discretization of a PDE. Other more sophisticated ILU preconditioners have been developed. Deciding which best fits an specific problem is not always obvious and could be an iterative process by itself.
I guess that your matrices should be very sparse, so I also suggest you try to use some subroutine of preconditioning, such as multigrid preconditioning techniques, i.e. AGMG and HSL_MI20. More precisely,
AGMG: http://homepages.ulb.ac.be/~ynotay/AGMG/
HSL_MI20: http://www.hsl.rl.ac.uk/catalogue/hsl_mi20.html
I hope you can do successfully.
- Badges
- Science topic
- Similar topics
- Medicine
- Physiology
- Biosignals
- Biomedical Signal Processing
- Statistical Analysis