A new approximate inverse preconditioner based on the Vaidya’s maximum spanning tree for matrix equation AXB = C

Document Type : Research Article

Authors

• K. Rezaei
• F. Rahbarnia
• F. Toutounian

Ferdowsi University of Mashhad

10.22067/ijnao.v9i2.70454

Abstract

We propose a new preconditioned global conjugate gradient (PGL-CG) method for the solution of matrix equation AXB = C, where A and B are sparse Stieltjes matrices. The preconditioner is based on the support graph preconditioners. By using Vaidya’s maximum spanning tree precon ditioner and BFS algorithm, we present a new algorithm for computing the approximate inverse preconditioners for matrices A and B and constructing a preconditioner for the matrix equation AXB = C. This preconditioner does not require solving any linear systems and is highly parallelizable. Numerical experiments are given to show the efficiency of the new algorithm on CPU and GPU for the solution of large sparse matrix equation.

Keywords

• Krylov subspace methods
• matrix equation
• approximate inverse preconditioner
• global conjugate gradient
• support graph preconditioner
• Vaidya's maximum spanning tree preconditioner

20.1001.1.24236977.2019.9.2.1.6

---

References

1. Bai, Z.Z. On Hermitian and skew-Hermitian splitting iteration methods for continuous Sylvester equations, J. Comput. Math. 29(2) (2011), 185–198.

2. Baur, U., Benner, P. Cross-gramian based model reduction for data-sparse systems, Electron. Trans. Numer. Anal. 31 (2008), 256–270.

3. Beauwens, R. Upper eigenvalue bounds for pencils of matrices, Linear Algebra Appl. 62 (1984), 87–104.

4. Beauwens, R. Approximate factorizations with modified S/P consistently ordered M-factors, Numer. Linear Algebra Appl. 1(1) (1994), 3–17.

5. Benzi, M., Meyer, C.D. and Tuma, M. A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Com put.17(5) (1996), 1135–1149.

6. Benzi, M. and Tuma, M. A robust incomplete factorization preconditioner for positive definite matrices, Preconditioning, 2001 (Tahoe City, CA). Numer. Linear Algebra Appl.10(5-6) (2003), 385–400.

7. Bern, M., Gilbert, J.R., Hendrickson, B., Nguyen, N. and Toledo, S. Support-graph preconditioners, SIAM J. Matrix Anal. Appl. 27(4) (2006),930–951.

8. Bouhamidi, A., Jbilou, K., Reichel, L. and Sadok, H. An extrapolated TSVD method for linear discrete ill-posed problems with kronecker structure, Linear Algebra Appl. 434(7) (2011), 1677–1688.

9. Calvetti, D. and Reichel, L. Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl. 17(1) (1996), 165–186.

10. Datta, B.N. Numerical methods for linear control systems: design and analysis, Elsevier, Academic Press, 2004.

11. Deng, Y.B., Bai, Z.Z. and Gao, Y.H. Iterative orthogonal direction methods for hermitian minimum norm solutions of two consistent matrix equations, Numer. Linear Algebra Appl. 13(10) (2006), 801–823.

12. George, J.A. Computer implementation of the finite element method, Technical report, Department of Computer Science, Stanford University, 1971.

13. George, J.A. and Liu, J.W.H. Computer Solution of Large Sparse Positive Definite System, Prentice-Hall, 1981.

14. Gremban, K. D. Combinatorial preconditioners for sparse, symmetric, diagonally dominant linear systems, PhD thesis, Carnegie Mellon University, 1996.

15. Gremban, K.D., Miller, G.L. and Zagha, M. Performance evaluation of a new parallel preconditioner, 9th International Parallel Processing Symposium, IEEE, (1995), 65–69.

16. Guennouni, A.E., Jbilou, K. and Riquet, A.J. Block Krylov subspace methods for solving large Sylvester equations, Matrix iterative analysis and biorthogonality (Luminy, 2000).Numer. Algorithms, 29(1-3) (2002), 75–96.

17. Horn, R.A., and Johnson, C.R. Topics in matrix analysis, Cambridge University Press, 1991.

18. Khojasteh-Salkuyeh, D. Cg-type algorithms to solve symmetric matrix equations, Appl. Math. Comput. 172(2) (2006), 985–999.

19. Khojasteh-Salkuyeh, D. and Toutounian, F. New approaches for solving large Sylvester equations, Appl. Math. Comput. 173(1) (2006), 9–18.

20. Matrix Market, Available at http//math.nist.gov/Matrix Market, May 2007.

21. Notay, Y. Solving positive (semi) definite linear systems by preconditioned iterative methods, Preconditioned Conjugate Gradient Methods, Lectures Notes in Mathematics, Springer, 1990.

22. Notay, Y. Conditioning analysis of modified block incomplete factorizations, Linear Algebra Appl. 154 (1991), 711–722.

23. Notay, Y. Conditioning of Stieltjes matrices by S/P consistently ordered approximate factorizations, Appl. Numer. Math. 10(5) (1992), 381–396.

24. Saad, Y. Iterative methods for sparse linear systems, SIAM, 2003.

25. Skiena, S.S. The algorithm design manual: Text, Springer Science & Business Media, 1998.

26. Vaidya, P.M. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners, Unpublished manuscript UIUC, A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, 1991.

27. Wang, M. and Feng, Y. An iterative algorithm for solving a class of matrix equations, J. Control Theory Appl. 7(1) (2009), 68–72.

28. Xie, L., Ding, J. and Ding, F. Gradient based iterative solutions for general linear matrix equations, Comput. Math. Appl. 58(7) (2009), 1441–1448.