Some Preconditioners for Block Pentadiagonal Linear Systems Based on New Approximate Factorization Methods
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:65374", author = "Xian Ming Gu and Ting Zhu Huang and Hou Biao Li", title = "Some Preconditioners for Block Pentadiagonal Linear Systems Based on New Approximate Factorization Methods", 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.", volume = "7", number = "4", pages = "727-8", }
