A supernodal block factorized sparse approximate inverse for non-symmetric linear systems. (English) Zbl 1391.65058
Summary: The concept of supernodes, originally developed to accelerate direct solution methods for linear systems, is generalized to block factorized sparse approximate inverse (Block FSAI) preconditioning of non-symmetric linear systems. It is shown that aggregating the unknowns in clusters that are processed together is particularly useful both to reduce the cost for the preconditioner setup and accelerate the convergence of the iterative solver. A set of numerical experiments performed on matrices arising from the meshfree discretization of 2D and 3D potential problems, where a very large number of nodal contacts is usually found, shows that the supernodal Block FSAI preconditioner outperforms the native algorithm and exhibits a much more stable behavior with respect to the variation of the user-specified parameters.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
| 65Y05 | Parallel numerical computation |
References:
| [1] | Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418-477 (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176 |
| [2] | Ferronato, M.: Preconditioning for sparse linear systems at the dawn of the 21st century: history, current developments, and future perspectives. ISRN Appl. Math. doi:10.5402/2012/127647 (2012) · Zbl 1264.65037 |
| [3] | Raghavan, P., Teranishi, K.: Parallel hybrid preconditioning: incomplete factorization with selective sparse approximate inversion. SIAM J. Sci. Comput. 32, 1323-1345 (2010) · Zbl 1213.65052 · doi:10.1137/080739987 |
| [4] | Helfenstein, R., Koko, J.: Parallel preconditioned conjugate gradient algorithm on GPU. J. Comput. Appl. Math. 236, 3584-3590 (2012) · Zbl 1245.65034 · doi:10.1016/j.cam.2011.04.025 |
| [5] | Janna, C., Ferronato, M., Gambolati, G.: Enhanced block FSAI preconditioning using domain decomposition techniques. SIAM J. Sci. Comput. 35, S229-S249 (2013) · Zbl 1288.65034 · doi:10.1137/120880860 |
| [6] | Chow, E., Patel, A.: Fine-grained parallel incomplete LU factorization. SIAM J. Sci. Comput. 37, C169-C193 (2015) · Zbl 1320.65048 · doi:10.1137/140968896 |
| [7] | Janna, C., Ferronato, M., Sartoretto, F., Gambolati, G.: FSAIPACK: A software package for high performance FSAI preconditioning. ACM Transactions on Mathematical Software 41, paper no. 10 (2015) · Zbl 1369.65052 |
| [8] | Grigori, L., Moufawad, S.: Communication avoiding ILU0 preconditioner. SIAM J. Sci. Comput. 37, C217-C246 (2015) · Zbl 1328.65076 · doi:10.1137/130930376 |
| [9] | Janna, C., Ferronato, M., Gambolati, G.: A Block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems. SIAM J. Sci. Comput. 32, 2468-2484 (2010) · Zbl 1220.65037 · doi:10.1137/090779760 |
| [10] | Ferronato, M., Janna, C., Pini, G.: A generalized Block FSAI preconditioner for nonsymmetric linear systems. J. Comput. Appl. Math. 256, 230-241 (2014) · Zbl 1314.65044 · doi:10.1016/j.cam.2013.07.049 |
| [11] | Ferronato, M., Janna, C., Pini, G.: Efficient parallel solution to large-size sparse eigenproblems with block FSAI preconditioning. Numer. Linear Algebra Appl. 19, 797-815 (2012) · Zbl 1274.65106 · doi:10.1002/nla.813 |
| [12] | Ferronato, M., Janna, C., Pini, G.: Parallel Jacobi-Davidson with block FSAI preconditioning and controlled inner iterations. Numer. Linear Algebra Appl. 23, 394-409 (2016) · Zbl 1413.65093 · doi:10.1002/nla.2030 |
| [13] | Janna, C., Ferronato, M.: Adaptive pattern research for Block FSAI preconditioning. SIAM J. Sci. Comput. 33, 3357-3380 (2011) · Zbl 1273.65045 · doi:10.1137/100810368 |
| [14] | Chow, E.: A priori sparsity patterns for parallel sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21, 1804-1822 (2000) · Zbl 0957.65023 · doi:10.1137/S106482759833913X |
| [15] | Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9, 302-325 (1983) · Zbl 0515.65022 · doi:10.1145/356044.356047 |
| [16] | Ashcraft, C., Grimes, R.G.: The influence of relaxed supernode partitions on the multifrontal method. ACM Trans. Math. Softw. 15, 291-309 (1989) · Zbl 0900.65061 · doi:10.1145/76909.76910 |
| [17] | Ashcraft, C.: Compressed graphs and the minimum degree algorithm. SIAM J. Sci. Comput. 16, 1404-1411 (1995) · Zbl 0837.65015 · doi:10.1137/0916081 |
| [18] | Gupta, A., George, T.: Adaptive techniques for improving the performance of incomplete factorization preconditioning. SIAM J. Sci. Comput. 32, 84-110 (2010) · Zbl 1209.65036 · doi:10.1137/080727695 |
| [19] | Vannieuwenhoven, N., Meerbergen, K.: IMF: An Incomplete multifrontal LU-factorization for element-structured sparse linear systems. SIAM J. Sci. Comput. 35, A270-A293 (2013) · Zbl 1264.65039 · doi:10.1137/100818996 |
| [20] | Janna, C., Ferronato, M., Gambolati, G.: The use of supernodes in factored sparse approximate inverse preconditioning. SIAM J. Sci. Comput. 37, C72-C94 (2015) · Zbl 1327.65062 · doi:10.1137/140956026 |
| [21] | Huckle, T.: Approximate sparsity patterns for the inverse of a matrix and preconditioning. Appl. Numer. Math. 30, 291-303 (1999) · Zbl 0927.65045 · doi:10.1016/S0168-9274(98)00117-2 |
| [22] | Lin, C., Moré, J.J.: Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21, 24-45 (1999) · Zbl 0941.65033 · doi:10.1137/S1064827597327334 |
| [23] | Janna, C., Castelletto, N., Ferronato, M.: The effect of graph partitioning techniques on parallel Block FSAI preconditioning: a computational study. Numer. Algorithms 68, 813-836 (2015) · Zbl 1312.65037 · doi:10.1007/s11075-014-9873-5 |
| [24] | Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [25] | Mirzaei, D., Schaback, R.: Direct meshless local Petrov-Galerkin (DMLPG) method: A generalized MLS approximation. Appl. Numer. Math. 68, 73-82 (2013) · Zbl 1263.65118 · doi:10.1016/j.apnum.2013.01.002 |
| [26] | Atluri, S.N., Zhu, T.: The meshless local Petrov-Galerkin (MLPG) method: A simple and less costly alternative to the finite element methods. Comput. Model. Eng. Sci. 3, 11-51 (2002) · Zbl 0996.65116 |
| [27] | Mirzaei, D., Schaback, R., Dehghan, M.: On generalized moving least squares and diffuse derivatives. IMA J. Numer. Anal. 32, 983-1000 (2012) · Zbl 1252.65037 · doi:10.1093/imanum/drr030 |
| [28] | Mazzia, A., Pini, G., Sartoretto, F.: A DMPLG refinement technique for 2D and 3D potential problems. Comput. Model. Eng. Sci. 108, 239-262 (2015) |
| [29] | Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1-25 (2011) · Zbl 1365.65123 |
| [30] | van der Vorst, H.A.: Bi-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 13, 631-644 (1992) · Zbl 0761.65023 · doi:10.1137/0913035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
