×

zbMATH — the first resource for mathematics

A high performance level-block approximate LU factorization preconditioner algorithm. (English) Zbl 1460.65046
Summary: Many application problems that lead to solving linear systems make use of preconditioned Krylov subspace solvers to compute their solution. Among the most popular preconditioning approaches are incomplete factorization methods either as single-level approaches or within a multilevel framework. We will present a block incomplete factorization that is based on skillfully blocking the system initially and throughout the factorization. Our objective is to develop algebraic block preconditioners for the efficient solution of such systems by Krylov subspace methods. We will demonstrate how our level-block approximate algorithm outperforms a single level-block scalar method often by orders of magnitude on modern architectures, thus paving the way for its prospective use inside various multilevel incomplete factorization approaches or other applications where the core part relies on an efficient incomplete factorization algorithms.
Reviewer: Reviewer (Berlin)
MSC:
65F50 Computational methods for sparse matrices
65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajiz, M. A.; Jennings, A., A robust incomplete Choleski-conjugate gradient algorithm, Int. J. Numer. Methods Eng., 20, 5, 949-966 (1984) · Zbl 0541.65019
[2] Amestoy, P.; Davis, T. A.; Duff, I. S., An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl., 17, 4, 886-905 (1996) · Zbl 0861.65021
[3] Amestoy, P. R.; Duff, I. S.; Koster, J.; L’Excellent, J.-Y., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41 (2001) · Zbl 0992.65018
[4] Amestoy, P. R.; Duff, I. S.; L’Excellent, J.-Y.; Robert, Y.; Rouet, F.-H.; Uçar, B., On computing inverse entries of a sparse matrix in an out-of-core environment, SIAM J. Sci. Stat. Comput., 34, 4, A1975-A1999 (2012) · Zbl 1252.05108
[5] Benzi, M., Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 418-477 (2002) · Zbl 1015.65018
[6] Benzi, M.; Haws, J. C.; Tůma, M., Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. Sci. Comput., 22, 4, 1333-1353 (2000) · Zbl 0985.65036
[7] Bollhöfer, M.; Saad, Y., Multilevel preconditioners constructed from inverse-based ILUs, SIAM J. Sci. Comput., 27, 5, 1627-1650 (2006) · Zbl 1104.65037
[8] Bollhöfer, M.; Grote, M. J.; Schenk, O., Algebraic multilevel preconditioner for the Helmholtz equation in Heterogeneous Media, SIAM J. Sci. Comput., 31, 5, 3781-3805 (2009) · Zbl 1203.65273
[9] Carpentieri, B.; Liao, J.; Sosonkina, M., VBARMS: a variable block algebraic recursive multilevel solver for sparse linear systems, J. Comput. Appl. Math., 259, 164-173 (2014) · Zbl 1291.65095
[10] Chapman, A.; Saad, Y.; Wigton, L., High-order ILU preconditioners for CFD problems, Int. J. Numer. Methods Fluids, 33, 6, 767-788 (2000) · Zbl 0959.76077
[11] Chow, E.; Heroux, M. A., An object-oriented framework for block preconditioning, ACM Trans. Math. Softw., 24, 2, 159-183 (1998) · Zbl 0930.65052
[12] Curtis, F. E.; Huber, J.; Schenk, O.; Wächter, A., A note on the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations, Math. Program., 136, 1, 209-227 (2012) · Zbl 1255.49043
[13] Davis, T. A., Algorithm 832: UMFPACK V4.3—an unsymmetric-pattern multifrontal method, ACM Trans. Math. Softw., 30, 2, 196-199 (2004) · Zbl 1072.65037
[14] D’Azevedo, E. F.; Forsyth, P. A.; Tang, W.-P., Towards a cost-effective ILU preconditioner with high level fill, BIT Numer. Math., 32, 3, 442-463 (1992) · Zbl 0761.65017
[15] Dolan, D. E.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[16] Duff, I. S.; Koster, J., The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM J. Matrix Anal. Appl., 20, 4, 889-901 (1999) · Zbl 0947.65048
[17] Duff, I. S.; Pralet, S., Strategies for scaling and pivoting for sparse symmetric indefinite problems, SIAM J. Matrix Anal. Appl., 27, 2, 313-340 (2005) · Zbl 1092.65037
[18] Duff, I. S.; Pralet, S., Towards stable mixed pivoting strategies for the sequential and parallel solution of sparse symmetric indefinite systems, SIAM J. Matrix Anal. Appl., 29, 3, 1007-1024 (2007) · Zbl 1145.65021
[19] Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct Methods for Sparse Matrices (2017), Oxford University Press · Zbl 1364.65067
[20] Eisenstat, S. C.; Gursky, M. C.; Schultz, M. H.; Sherman, A. H., Yale sparse matrix package I: the symmetric codes, Int. J. Numer. Methods Eng., 18, 8, 1145-1151 (1982) · Zbl 0492.65012
[21] Gould, N. I.; Scott, J. A.; Hu, Y., A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM Trans. Math. Softw., 33, 10:1-10:31 (2007) · Zbl 1365.65129
[22] Gupta, A.; George, T., Adaptive techniques for improving the performance of incomplete factorization preconditioning, SIAM J. Sci. Comput., 32, 1, 84-110 (2010) · Zbl 1209.65036
[23] Hagemann, M.; Schenk, O., Weighted matchings for the preconditioning of symmetric indefinite linear systems, SIAM J. Sci. Comput., 28, 2, 403-420 (2006) · Zbl 1111.65042
[24] Hénon, P.; Ramet, P.; Roman, J., On finding approximate supernodes for an efficient ILU(k) factorization, Parallel Comput., 34, 345-362 (2008)
[25] Hysom, D.; Pothen, A., A scalable parallel algorithm for incomplete factor preconditioning, SIAM J. Sci. Comput., 22, 6, 2194-2215 (2001) · Zbl 0986.65048
[26] Hysom, D.; Pothen, A., Level-based incomplete LU factorization: Graph model and algorithms (November 2002), Tech. Rep. UCRL-JC-150789
[27] Jones, M. T.; Plassmann, P. E., An improved incomplete Cholesky factorization, ACM Trans. Math. Softw., 21, 1, 5-17 (1995) · Zbl 0886.65024
[28] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 1, 359-392 (1998) · Zbl 0915.68129
[29] Kershaw, D. S., The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, J. Comput. Phys., 26, 43-65 (1978) · Zbl 0367.65018
[30] Kurzak, J.; Gates, M.; YarKhan, A.; Yamazaki, I.; Wu, P.; Luszczek, P.; Finney, J.; Dongarra, J., Parallel BLAS performance report (2018), ICL-UT-18-01 (04-2018)
[31] LaSalle, D.; Karypis, G., Multi-threaded graph partitioning (2013), Department of Computer Science & Engineering, University of Minnesota,: Department of Computer Science & Engineering, University of Minnesota, Minneapolis, Tech. rep.
[32] Li, N.; Saad, Y.; Chow, E., Crout versions of ILU for general sparse matrices, SIAM J. Sci. Comput., 25, 2, 716-728 (2004) · Zbl 1042.65025
[33] Li, X. S., An overview of SuperLU: algorithms, implementation, and user interface, ACM Trans. Math. Softw., 31, 3, 302-325 (2005) · Zbl 1136.65312
[34] Li, X. S.; Shao, M., A supernodal approach to incomplete LU factorization with partial pivoting, ACM Trans. Math. Softw., 37, 4, 43:1-43:20 (2011) · Zbl 1365.65078
[35] Lin, C.-J.; Moré, J. J., Incomplete Cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21, 1, 24-45 (1999) · Zbl 0941.65033
[36] Maurer, H.; Mittelmann, H., Optimization techniques for solving elliptic control problems with control and state constraints: Part 1. Boundary control, Comput. Optim. Appl., 16, 1, 29-55 (2000) · Zbl 0961.93026
[37] Ng, E. G.; Peyton, B. W.; Raghavan, P., A blocked incomplete Cholesky preconditioner for hierarchical-memory computers, (Iterative Methods in Scientific Computation IV. Iterative Methods in Scientific Computation IV, IMACS Series in Computational and Applied Mathematics (1999), IMACS), 211-221
[38] Olschowka, M.; Neumaier, A., A new pivoting strategy for Gaussian elimination, Linear Algebra Appl., 240, 131-151 (1996) · Zbl 0852.65021
[39] Saad, Y., Finding exact and approximate block structures for ILU preconditioning, SIAM J. Sci. Comput., 24, 4, 1107-1123 (2003) · Zbl 1034.65020
[40] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM Publications: SIAM Publications Philadelphia · Zbl 1002.65042
[41] Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[42] Saad, Y.; Suchomel, B. J., ARMS: an algebraic recursive multilevel solver for general sparse linear systems, Numer. Linear Algebra Appl., 9, 359-378 (2002) · Zbl 1071.65001
[43] Schenk, O.; Gärtner, K., Solving unsymmetric sparse systems of linear equations with PARDISO, J. Futur. Gener. Comput. Syst., 20, 3, 475-487 (2004)
[44] Schenk, O.; Gärtner, K., On fast factorization pivoting methods for symmetric indefinite systems, Electron. Trans. Numer. Anal., 23, 1, 158-179 (2006) · Zbl 1112.65022
[45] Schenk, O.; Röllin, S.; Gupta, A., The effects of unsymmetric matrix permutations and scalings in semiconductor device and circuit simulation, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 23, 3, 400-411 (2004)
[46] Schenk, O.; Wächter, A.; Hagemann, M., Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization, Comput. Optim. Appl., 36, 2, 321-341 (2007) · Zbl 1146.90055
[47] Schenk, O.; Bollhöfer, M.; Römer, R. A., SIGEST: on large scale diagonalization techniques for the Anderson model of localization, SIAM Rev., 50, 91-112 (2008) · Zbl 1136.65044
[48] Schenk, O.; Wächter, A.; Weiser, M., Inertia revealing preconditioning for large-scale nonconvex constrained optimization, SIAM J. Sci. Comput., 31, 2, 939-960 (2008) · Zbl 1194.35029
[49] Schenk, O.; Wächter, A.; Weiser, M., Inertia-revealing preconditioning for large-scale nonconvex constrained optimization, SIAM J. Sci. Comput., 31, 2, 939-960 (2009) · Zbl 1194.35029
[50] Scott, J. A.; Tůma, M., The importance of structure in incomplete factorization preconditioners, BIT Numer. Math., 51, 2, 385-404 (2011) · Zbl 1221.65090
[51] Wächter, A.; Biegler, L. T., On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542
[52] Watts, J. W., A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation, Soc. Pet. Eng. J., 21, 345-353 (1981)
[53] Xi, Y.; Li, R.; Saad, Y., An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices, SIAM J. Matrix Anal. Appl., 37, 1, 235-259 (2016) · Zbl 1376.65036
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.