It highly depends on the problem which method will be better. And then you also need to define what you actually mean by "better": Better convergence? Better speed? Sometimes a slightly better convergence is not important because of bad performance. Currently, in our simulation software we are using BiCGSTAB(2). But, we have several problems which we cannot simulate because the solver will not converge. We will try AMG methods for these kinds of problems. But probably it will be too slow in the general case.
Thanks, Prof. Mittal! However, I supposed to know if does exists another iterative method that may be considered better than BiCGStab or BiCGStab(2) for solving linear systems. I have parallelized (on GPU) these both methods and published a few papers showing that the parallelized version is better than the sequential one. Currently, I wonder if I could show that they are better than others in terms of convergence.
Parallelised methods are always better than sequential if they are properly implemented. GMRES based method is better than BICGStab ones
GMRES needs to be restarted if an effective computational/storage cost is of essence. However, this may lead to a significant deterioration in convergence properties (and leads to the divergence is some complicated cases, even if a good preconditioner is available). In principle, if an inplace Krylov method is used, the main problem is how to parallelise the sparse matrix-vector multiplication. All other operations are of lower complexity order.
Sparse matrices are stored in the compressed storage form. Incomplete LU form along with GMRES it could be effective. I do not know about rationalization.
Thank you, Professor Mittal and Professor Milan! Your comments were very useful. However, the reason of my question is about parallelization. I just would like to know if another parallelized iterative method could be better, in terms of computational time, than BiCGStab or BiCGStab(2). Best regards!!!
Computational time will depend on the number of iterations and the cost per iteration (this includes the cost of applying a preconditioner). So, the best way to try this is to test serial performance of several Krylov methods with the preconditioner of your choice applied to your target problem, and measure time per iteration and the total execution time. Then try to parallelise the method that gives best overall serial performance (of course you need to check first that there are no inherent difficulties with the parallisation of that method.
Note that the convergence rate of an iterative linear system solver heavily depends on the properties of the matrix. For a good overview of such methods you could consult the book "Iterative methods for sparse linear systems" by Y. Saad.
To answer your question: Depending on your problem there might be a big chance that there exists a better method than BiCG. However, finding the right one might not be a trivial choice. And general statements are probably not possible.
With PETSc, there are many iterative methods parallelized with MPI
Please refer to the papers of Tong-Xiang Gu, Xian-Yu Zuo, Xing-Ping Liu. They had finished many paper about the parellelized iterative solvers, such as QMRCGSTAB and GPBiCG(m,\ell) (DOI: 10.1016/j.camwa.2013.11.008). I want to some details of your problems, wichi field does your linear systems come from?
Thank you, Xian-Ming Gu! I believe your suggestions may be useful. I just have parallelized the BiCGStab and BiCGStab(2) methods. Both are iterative methods and have provided viable outcomes for solution of large and sparse linear systems.
As you can see on my profile, I have some papers (but only one in english) that show the parallelized (on GPU) version of these methods. Until now, I have only used CUDA-C and the integration CUDA-Matlab for developing the algorithms. If you wish to contact me directly, please feel free: [email protected].
Best regards!
Yes, in fact, GPBiCG(m,\ell) has been included some established iterative method, when m = 1, \ell = 0, GPBiCG(1,0) = BiCGSTAB, m = 1, \ell = 1, GPBiCG(1,1) = BiCGSTAB(2). Please refer to the ogrinial paper of GPBiCG(m,\ell). Thank you.
Thank you again, Xian-Ming Gu! Certainly, I will refer to the original paper you suggested. It would be a pleasure for me if my two answers were voted up by you.
Best Wishes!
It highly depends on the problem which method will be better. And then you also need to define what you actually mean by "better": Better convergence? Better speed? Sometimes a slightly better convergence is not important because of bad performance. Currently, in our simulation software we are using BiCGSTAB(2). But, we have several problems which we cannot simulate because the solver will not converge. We will try AMG methods for these kinds of problems. But probably it will be too slow in the general case.
Thank you, Simon! You are right. I have not asked correctly. I was supposed to know if there is any iterative method that was parallelized and was shown to be better (in relation to computational performance) than BiCGStab or BiCGStab(2).
I think for parallel computing Chebyshev iteration will better than all Krylove subspace methods because this does not required any inner product. For reference you can go through the article by Martin H. Gutknecht, Stefan Rollin, "The Chebyshev iteration revisited", Parallel Computing, 28 (2002) 263–283. Also you can see the PDF file attached here. I will be very happy for in-depth discussion on this if any.
Thank you very much, Nachiketa! Your answer were very useful. I am available for any discussion about this subject too. Please, feel free to contact me whenever you want.
For certain types of problems, you might want to try our (Dan & Rachel Gordon) CARP-CG algorithm:
http://cs.haifa.ac.il/~gordon/carp-cg.pdf
It was found to be useful for strongly convection-dominated elliptic PDEs, high-frequency Helmholtz equation, discontinuous coefficients.
- Badges
- Science topic