Some Preconditioners for Block Pentadiagonal Linear Systems Based on New Approximate Factorization Methods

Authors: Xian Ming Gu, Ting Zhu Huang, Hou Biao Li

Abstract:

In this paper, getting an high-efficiency parallel algorithm to solve sparse block pentadiagonal linear systems suitable for vectors and parallel processors, stair matrices are used to construct some parallel polynomial approximate inverse preconditioners. These preconditioners are appropriate when the desired target is to maximize parallelism. Moreover, some theoretical results about these preconditioners are presented and how to construct preconditioners effectively for any nonsingular block pentadiagonal H-matrices is also described. In addition, the availability of these preconditioners is illustrated with some numerical experiments arising from two dimensional biharmonic equation.

Keywords: Parallel algorithm, Pentadiagonal matrix, Polynomial approximate inverse, Preconditioners, Stair matrix.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088316

References:

[1] G. Rodrigue, R. S. Varga, ”Convergence rate estimate for iterative solutions of the biharmonic equation,” J. Comput. Appl. Math., vol. 24, no. 1-2, pp. 129-146, 1988.
[2] M. Vajtersic, ”A Direct Block-Five-Diagonal System Solver for the VLSI Parallel Model.” In Proceedings of the 10th International Parallel Processing Symposium (IPPS ’96). IEEE Computer Society, Washington, DC, USA, pp. 886-890, 1996.
[3] M. H. Koulaei, F. Toutounian, ”Factored sparse approximate inverse of block tridiagonal and block pentadiagonal matricies,” Appl. Math. Comput., vol. 184, no.2, pp. 223-234, 2007.
[4] V. Casulli, ”Numerical simulation of three-dimensional free surface flow in isopycnal co-ordinates,” Int. J. Numer. Meth. Fluids, vol. 25, no. 6, pp. 645-658, 1997.
[5] K. Benkert, R. Fischer, ”An Efficient Implementation of the Thomas- Algorithm for Block Penta-diagonal Systems on Vector Computers,” International Conference on Computational Science, Beijing, China, pp. 144-151, 2007.
[6] R. Samtaney, D. I. Pullin, ”On initial-value and self-similar solutions of the compressible Euler equations,” Phys. Fluids, vol. 8, no. 10, pp. 2650- 2655, 1996.
[7] A. Kaveh, H. Rahami, ”Tri-diagonal and penta-diagonal block matrices for efficient eigensolutions of problems in structural mechanics,” Acta Mechanica, vol. 192, no. 1-4, pp. 77-87, 2007.
[8] V. B. L. Boppana, J. S. B. Gajjar, ”Global flow instability in a lid-driven cavity,” Int. J. Numer. Meth. Fluids, vol. 62, no. 8, pp. 827-853, 2010.
[9] L. Adams, ”M-step preconditioned conjugate gradient methods”, SIAM J. Sci. Stat. Comput., vol. 6, no. 2, pp. 452-462, 1985.
[10] L. Adams, E. Ong, ”Additive polynomial preconditioners for parallel computers,” Parallel Comput., vol. 9, no.3, pp. 333-345, 1988/89.
[11] O. Axelsson, Iterative Solution Methods, Cambridge University Press, New York, USA., 1994.
[12] Z. Z. Bai, ”On the convergence of the multisplitting methods for the linear complementarity problem,” SIAM J. Matrix Anal. Appl., vol. 21, no.1, pp. 67-78, 2000.
[13] R. Barret, M. Berry, T. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM press, Philadelphia, PA, USA., 1994.
[14] R. Beauwens, M. Ben Bouzid, ”On sparse block factorization iterative methods,” SIAM J. Numer. Anal., vol. 24, no. 5, pp. 1066-1076, 1987.
[15] A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM Press, Philadelphia, USA., 1994.
[16] R. Bru, C. Corral, J. Mas, ”A preconditioned conjugate gradient method on a distributed memory multiprocessor,” Appl. Math. Lett., vol. 8, no. 3, pp. 49-53, 1995.
[17] R. Bru, C. Corral, A. Mart´ınez, J. Mas, ”Multisplitting preconditioners based on incomplete Choleski factorizations,” SIAM J. Matrix Anal. Appl., vol. 16, no. 4, pp. 121-1222, 1995.
[18] E. Chow, Y. Saad, ”Approximate inverse techniques for block-partitioned matrices,” SIAM J. Sci. Comput., vol. 18, no. 6, pp. 1657-1675, 1997.
[19] R. Fletcher, Conjugate gradient methods for indefinite systems, in: Lecture Notes in Mathematics, vol. 506, Springer, Berlin, 1976, pp. 73-89.
[20] M. J. Grote, T. Huckle, ”Parallel preconditioning with sparse approximate inverses,” SIAM J. Sci. Comput., vol. 18, no. 3, pp. 838-853, 1997.
[21] C. H. Guo, ”Some results on sparse block factorization iterative methods,” Linear Algebra Appl., vol. 145, pp. 187-199, 1991.
[22] C. H. Guo, ”Incomplete block factorization preconditioning for linear systems arising in the numerical solution of the Helmholtz equation,” Appl. Numer. Math., vol. 19, no. 4, pp. 495-508, 1996.
[23] J. G. Hu, ”The upper and lower bounds of the eigenvalues of M1−N,” Math. Numer. Sinica, vol. 8, no. 1, pp. 41-46, 1986. (in Chinese)
[24] T. Huckle, ”Approximate sparsity patterns for the inverse of a matrix and preconditioning,” Appl. Numer. Math., vol. 30, no. 2-3, pp. 291-303, 1999.
[25] H. B. Li, T. Z. Huang, H. Li, ”An improvement on a new upper bound for moduli of eigenvalues of iterative matrices,” Appl. Math. Comput., vol. 137, no. 2, pp. 977-984, 2006.
[26] H. B. Li, T. Z. Huang, H. Li, ”On some subclasses of P-matrices,” Numer. Lin. Alg. Appl., vol. 14, no. 5, pp. 391-405, 2007.
[27] H. B. Li, T. Z. Huang, S. Q. Shen, H. Li, ”Lower bounds for the minimum eigenvalue of Hadamard product of an M-matrix and its inverse,” Lin. Alg. Appl., vol. 421, no. 1, pp. 235-247, 2007.
[28] H. B. Li, T. Z. Huang, H. Li, ”Inclusion sets for singular values,” Lin. Alg. Appl., vol. 428 no. 8-9, pp. 2220-2235, 2008.
[29] H. Lu, ”Stair matrices and their generalizations with applications to iterative methods I: a generalization of the successive overrelaxation method,” SIAM J. Numer. Anal., vol. 37, no. 1, pp. 1-17, 2001.
[30] J. M. Ortega, Introduction to Parallel and Vector Solution of Linear Systems, Plenum Press, New York, USA., 1988.
[31] Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, Boston, MA, USA., 1996.
[32] Y. Saad, M. H. Schultz, ”GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems,” SIAM J. Sci. Statist. Comput., vol. 7, no.3, pp. 856-869, 1986.
[33] H. A. Van der Vorst, ”Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems,” SIAM J. Sci. Statist. Comput., vol. 13, no.2, pp. 631-644, 1992.
[34] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ, USA., 1962.
[35] J. H. Yun, ”Block ILU preconditioners for a nonsymmetric blocktridiagonal M-matrix”, BIT, vol. 40, no. 3, pp. 583-605, 2000.
[36] H. B. Li, T. Z. Huang, Y. Zhang, X. P. Liu, H. Li, ”On some new approximate factorization methods for block tridiagonal matrices suitable for vector and parallel processors,” Mathematics and Computers in Simulation, vol. 79, no. 7, pp. 2135-2147, 2009.