Communication avoiding ILU0 preconditioner. (English) Zbl 1328.65076
Summary: In this paper we present a communication avoiding ILU0 preconditioner for solving large linear systems of equations by using iterative Krylov subspace methods. Recent research has focused on communication avoiding Krylov subspace methods based on so-called \(s\)-step methods. However, there are not many communication avoiding preconditioners yet, and this represents a serious limitation of these methods. Our preconditioner allows us to perform \(s\) iterations of the iterative method with no communication, through ghosting some of the input data and performing redundant computation. To avoid communication, an alternating reordering algorithm is introduced for structured and well partitioned unstructured matrices, which requires the input matrix to be ordered by using a graph partitioning technique such as \(k\)-way or nested dissection. We show that the reordering does not affect the convergence rate of the ILU0 preconditioned system as compared to \(k\)-way or nested dissection ordering, while it reduces data movement and is expected to reduce the time needed to solve a linear system. In addition to communication avoiding Krylov subspace methods, our preconditioner can be used with classical methods such as GMRES to reduce communication.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 65Y05 | Parallel numerical computation |
| 68W10 | Parallel algorithms in computer science |
References:
| [1] | Y. Achdou and F. Nataf, {\it Low frequency tangential filtering decomposition}, Numer. Linear Algebra Appl., 14 (2007), pp. 129-147. · Zbl 1199.65087 |
| [2] | C. Aykanat, B. B. Cambazoglu, and B. Uçar, {\it Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices}, J. Parallel Distrib. Comput., 68 (2008), pp. 609-625. · Zbl 1243.68222 |
| [3] | G. Ballard, J. Demmel, O. Holtz, and O. Schwartz, {\it Minimizing communication in numerical linear algebra}, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 866-901. · Zbl 1246.68128 |
| [4] | M. Benzi, {\it Preconditioning techniques for large linear systems: A survey}, J. Comput. Phys., 182 (2002), pp. 418-477. · Zbl 1015.65018 |
| [5] | M. Benzi, D. B. Szyld, and A. van Duin, {\it Orderings for incomplete factorization preconditioning of nonsymmetric problems}, SIAM J. Sci. Comput., 20 (1999), pp. 1652-1670. · Zbl 0940.65033 |
| [6] | E. Carson, N. Knight, and J. Demmel, {\it Avoiding communication in nonsymmetric Lanczos-based Krylov subspace methods}, SIAM J. Sci. Comput., 35 (2013), pp. S42-S61. · Zbl 1281.65057 |
| [7] | E. Carson, N. Knight, and J. Demmel, {\it Hypergraph partitioning for computing matrix powers}, extended abstract, in 5th SIAM Workshop on Combinatorial Scientific Computing, Darmstadt, Germany, 2011, pp. 31-33. |
| [8] | U. Catalyurek and C. Aykanat, {\it Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication}, IEEE Trans. Parallel Distrib. Systems, 10 (1999), pp. 673-693. |
| [9] | A. T. Chronopoulos and W. Gear, {\it s-step iterative methods for symmetric linear systems}, J. Comput. Appl. Math., 25 (1989), pp. 153-168. · Zbl 0669.65021 |
| [10] | T. A. Davis, {\it The University of Florida Sparse Matrix Collection}, 1994, available online at http://www.cise.ufl.edu/research/sparse/matrices/. · Zbl 1365.65123 |
| [11] | H. C. Elman, {\it Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems}, BIT, 29 (1989), pp. 890-915. · Zbl 0694.65011 |
| [12] | J. Demmel, L. Grigori, M. Hoemmen, and J. Langou, {\it Communication-optimal parallel and sequential QR factorizations}, SIAM J. Sci. Comput., 34 (2012), pp. A206-A239. · Zbl 1241.65028 |
| [13] | J. Demmel, M. Hoemmen, M. Mohiyuddin, and K. Yelick, {\it Avoiding communication in sparse matrix computations}, in Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2008), IEEE, Piscataway, NJ, 2008, pp. 1-12. |
| [14] | S. Doi and T. Washio, {\it Ordering strategies and related techniques to overcome the trade-off between parallelism and convergence in incomplete factorizations}, Parallel Comput., 25 (1999), pp. 1995-2014. |
| [15] | J. Erhel, {\it A parallel GMRES version for general sparse matrices}, Electron. Trans. Numer. Anal., 3 (1995), pp. 160-176. · Zbl 0860.65021 |
| [16] | M. Garey, D. Johnson, and L. Stockmeyer, {\it Some simplified NP-complete graph problems}, Theoret. Comput. Sci., 1 (1976), pp. 237-267. · Zbl 0338.05120 |
| [17] | A. George, {\it Nested dissection of a regular finite element mesh}, SIAM J. Numer. Anal., 10 (1973), pp. 345-363. · Zbl 0259.65087 |
| [18] | P. Ghysels, T. J. Ashby, K. Meerbergen, and W. Vanroose, {\it Hiding global communication latency in the GMRES algorithm on massively parallel machines}, SIAM J. Sci. Comput., 35 (2013), pp. C48-C71. · Zbl 1273.65050 |
| [19] | J. R. Gilbert and T. Peierls, {\it Sparse partial pivoting in time proportional to arithmetic operations}, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 862-874. · Zbl 0656.65036 |
| [20] | L. Grigori, J. W. Demmel, and H. Xiang, {\it CALU: A communication optimal LU factorization algorithm}, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1317-1350. · Zbl 1242.65089 |
| [21] | L. Grigori and S. Moufawad, {\it Communication Avoiding ILU0 Preconditioner}, Technical Report, ALPINES - INRIA Paris-Rocquencourt, Paris, France, 2013. · Zbl 1328.65076 |
| [22] | F. Hecht, {\it New development in freefem\textup++}, J. Numer. Math., 20 (2012), pp. 251-265. · Zbl 1266.68090 |
| [23] | M. R. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. Natl. Bur. Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901 |
| [24] | M. Hoemmen, {\it Communication-Avoiding Krylov Subspace Methods}, Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2010. |
| [25] | G. Karypis and V. Kumar, {\it Metis \textup4.0: Unstructured Graph Partitioning and Sparse Matrix Ordering System}, technical report, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1998. |
| [26] | B. W. Kernighan and S. Lin, {\it An efficient heuristic procedure for partitioning graphs}, Bell Syst. Tech. J., 49 (1970), pp. 291-307. · Zbl 0333.05001 |
| [27] | M. S. Khaira, G. L. Miller, and T. J. Sheffler, {\it Nested Dissection: A Survey and Comparison of Various Nested Dissection Algorithms}, Technical report, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1992. |
| [28] | J. A. Meijerink and H. A. van der Vorst, {\it An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix}, Math. Comput., 31 (1977), pp. 148-162. · Zbl 0349.65020 |
| [29] | M. Mohiyuddin, M. Hoemmen, J. Demmel, and K. Yelick, {\it Minimizing communication in sparse matrix solvers}, in Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, SC 09, ACM, New York, 2009, pp. 1-12. |
| [30] | Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046 |
| [31] | Y. Saad and M. H. Schultz, {\it GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems}, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018 |
| [32] | J. Scott and M. Tuma, {\it On positive semidefinite modification schemes for incomplete Cholesky factorization}, SIAM J. Sci. Comput., 36 (2014), pp. A609-A633. · Zbl 1298.65049 |
| [33] | H. F. Walker, {\it Implementation of the GMRES method using Householder transformations}, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 152-163. · Zbl 0698.65021 |
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.
