محاسبه شکل بلوکی پیش شرط ساز LU ناقص به عنوان محصول فرعی نسخه پیمایش چپ الگوریتم A-دو مزدوج سازی بلوکی
محورهای موضوعی : آمار
امین رفیعی
1
(دانشگاه حکیم سبزواری)
بهناز طلوع حقیقی
2
(دانشگاه حکیم سبزواری)
کلید واژه: block version of Gaussian elimination process, left-looking version of robust incomplete factorization preconditioner, Incomplete LU preconditioner,
چکیده مقاله :
در این مقاله، شکل بلوکی پیش شرط ساز LU ناقصی را ارائه می کنیم که به عنوان محصول فرعی الگوریتم بلوکی A-دو مزدوج سازی محاسبه می شود. عناصر لولای این پیش شرط ساز، بلوکهای یک در یک یا دو در دو می باشند. ماتریسهای L و U این پیش شرط ساز به صورت مستقل از یکدیگر محاسبه خواهند شد. محک انتخاب عناصر لولا در این پیش شرط ساز بلوکی، همان محک به کار رفته در یکی از نسخه های بلوکی فرایند حذفی گاوس است. مبنای ارائه این پیش شرط ساز بلوکی، ارتباط میان فرایند حذفی گاوس و الگوریتم A-دو مزدوج سازی است. در بخش مثالهای عددی این مقاله، ابتدا دستگاههای مصنوعی تولید کرده و سپس برای این دستگاهها هر دو شکل ساده و بلوکی این پیش شرط ساز را محاسبه کرده ایم. پس از آن دستگاههای پیش شرط شده راست را تشکیل داده و از روش (50) GMRES برای حل این دستگاههای پیش شرط شده استفاده گردیده است. نتایج عددی نشان می دهد که شکل بلوکی این پیش شرط ساز LU ناقص، روش (50)GMRES را در تعداد تکرارهای کمتری نسبت به شکل ساده این پیش شرط ساز همگرا می نماید و بنابراین دارای کیفیت بهتری است.
In this paper, we present a block version of incomplete LU preconditioner which is computed as the by-product of block A-biconjugation process. The pivot entries of this block preconditioner are one by one or two by two blocks. The L and U factors of this block preconditioner are computed separately. The block pivot selection of this preconditioner is inherited from one of the block versions of Gaussian elimination process. The main basis to propose such a block preconditioner is a connection between the Gaussian elimination process and the A-biconjugation algorithm. In the numerical experiment section, we have generated artificial linear systems. Then, we have computed the block and plain versions of this incomplete LU preconditioner. We have used these two preconditioners as the right preconditioner for linear systems. After that, the GMRES(50) method has been applied to solve the right preconditioned systems. The results indicate that the block preconditioner gives fewer number of iterations of GMRES(50) method than the plain version. Therefore, the block preconditioer has a better quality.
[1] Y. Saad, Iterative methods for sparse linear systems. SIAM Publications, Philadelphia, second edition (2003).
[2] M. Benzi, and M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19(3) (1998) 968-994.
[3] M. Benzi, and M. Tuma, M. A Robust Incomplete Factorization Preconditioner for Positive Definite Matrices, Numer. Linear Alg. Appl., 10 (2003) 385-400.
[4] A. Rafiei, B. Tolue, and M. Bollhoefer, Complete pivoting strategy for the left-looking Robust Incomplete Factorization preconditioner, Comput. Math. Appl., 67 (2014) 2055-2070.
[5] A. Rafiei, A complete pivoting strategy for the right-looking Robust Incomplete Factorization preconditioner. Comput. Math. Appl., 64 (2012) 2682-2694.
[6] Ch. Kruschel, Losen von positiv definiten, unsymmetrischen Matrizen mit Matching-Methoden am Beispiel von Konvektion-Diffusionsgleichungen. Bachelor of Sciences thesis, Technische Universitat Braunschweig (2009).
[7] A. Rafiei, M. Bollhoefer and F. Benkhaldoun, A block version of left-looking AINV preconditioner with one by one or two by two block pivots, Revised for Appl. Math. Comput., (2018).
[8] A. Rafiei, Left-looking version of AINV preconditioner with complete pivoting strategy, Linear Alg. Appl., 445 (2014) 103-126.
[9] T. Davis, The SuiteSparse Matrix Collection, http://www.cise.ufl.edu/research/sparse/matrices/. Accessed 2017.
[10] I. S. Duff, and J. Koster, The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Anal. Appl., 20(4) (1999) 889-901.
[11] I. S. Duff, and S. Parlett Strategies for scaling and pivoting for sparse symmetric indefinite problems. SIAM J. Matrix Anal. Appl., 27(2) (2005) 313-340.
[12] G. Karypis, and V. Kumar, METIS a Software Package for partitioning Unstructured Graphs and Computing Fill-Reduced Orderings of Sparse Matrices,
http://glaros.dtc.umn.edu/gkhome/metis/metis/download
[13] M. Bollhoefer, ILUPACK software package. http://www.icm.tu-bs.de/~bolle/ilupack.
[14] The HSL Mathematical Software Library, http://www.hsl.rl.ac.uk.
[15] Y. Saad, Sparskit and sparse examples, http://www-users.cs.umn.edu/~saad/software. Accessed 2017.
[16] Y. Saad, ITSOL software package. http://www-users.cs.umn.edu/~saad/software.