This paper presents a parallel preconditioning approach based on incomplete LU (ILU) factorizations in the framework of Domain Decomposition (DD) for general sparse linear systems. We focus on distributed memory parallel architectures, specifically, those that are equipped with graphic processing units (GPUs). In addition to block-Jacobi, we present general purpose two-level ILU Schur complement-based approaches, where different strategies are presented to solve the coarse-level reduced system. These strategies are combined with modified ILU methods in the construction of the coarse-level operator, in order to effectively remove smooth errors by targeting an algebraically smooth vector. We leverage available GPU-based sparse matrix kernels to accelerate the setup and the solve phases of the proposed ILU preconditioner. We evaluate the efficiency of the proposed methods as a smoother for algebraic multigrid (AMG) and as a preconditioner for Krylov subspace methods on challenging anisotropic diffusion problems and a collection of general sparse matrices.
AndersonRAndrejJBarkerA, et al. (2020) MFEM: a modular finite element methods library. Computers & Mathematics with Applications81: 42–74. DOI: 10.1016/j.camwa.2020.06.009.
2.
AnztHTomovSDongarraJ (2015) Accelerating the LOBPCG method on GPUs using a blocked sparse matrix vector product. In: Proceedings of the Symposium on High Performance Computing, HPC ’15. San Diego, CA, USA: Society for Computer Simulation International, pp. 75–82.
3.
AurentzJLKalantzisVSaadY (2017) Cucheb: a GPU implementation of the filtered Lanczos procedure. Computer Physics Communications220(Supplement C): 332–340. DOI: 10.1016/j.cpc.2017.06.016.
4.
BakerAHFalgoutRDKolevTV, et al. (2011) Multigrid smoothers for ultraparallel computing. SIAM Journal on Scientific Computing33(5): 2864–2887. DOI: 10.1137/100798806.
5.
BankREWagnerC (1999) Multilevel ILU decomposition. Numerische Mathematik82(4): 543–576. DOI: 10.1007/s002110050430.
6.
BottaEWubsFW (1999) Matrix renumbering ILU: an effective algebraic multilevel ILU preconditioner for sparse matrices. SIAM Journal on Matrix Analysis and Applications20(4): 1007–1026. DOI: 10.1137/S0895479897319301.
BrannickJJFalgoutRD (2010) Compatible relaxation and coarsening in algebraic multigrid. SIAM Journal on Scientific Computing32(3): 1393–1416. DOI: 10.1137/090772216.
9.
BuatoisLCaumonGLévyB (2009) Concurrent number cruncher: a GPU implementation of a general sparse linear solver. International Journal of Parallel, Emergent and Distributed Systems24(3): 205–223. DOI: 10.1080/17445760802337010.
10.
BuiQMHamonFPCastellettoN, et al. (2021) Multigrid reduction preconditioning framework for coupled processes in porous and fractured media. Computer Methods in Applied Mechanics and Engineering387: 114111. DOI: 10.1016/j.cma.2021.114111.
11.
CaiXCSarkisM (1999) A restricted additive schwarz preconditioner for general sparse linear systems. SIAM Journal on Scientific Computing21(2): 792–797. DOI: 10.1137/S106482759732678X.
12.
CarvalhoLMGiraudLLe TallecP (2001) Algebraic two-level preconditioners for the schur complement method. SIAM Journal on Scientific Computing22(6): 1987–2005. DOI: 10.1137/S1064827598340809.
13.
CatalyurekUAykanatC (1999) Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems10(7): 673–693. DOI: 10.1109/71.780863.
14.
CerdánJMarínJMasJ (2017) A two-level ILU preconditioner for electromagnetic applications. Journal of Computational and Applied Mathematics309: 371–382. DOI: 10.1016/j.cam.2016.03.012.
15.
ChowEPatelA (2015) Fine-grained parallel incomplete LU factorization. SIAM Journal on Scientific Computing37(2): C169–C193. DOI: 10.1137/140968896.
16.
ChowESaadY (1997) Experimental study of ILU preconditioners for indefinite matrices. Journal of Computational and Applied Mathematics86(2): 387–414. DOI: 10.1016/S0377-0427(97)00171-4.
17.
ClarkMBabichRBarrosK, et al. (2010) Solving lattice qcd systems of equations using mixed precision solvers on GPUs. Computer Physics Communications181(9): 1517–1528. DOI: 10.1016/j.cpc.2010.05.002.
18.
DillonGKalantzisVXiY, et al. (2018) A hierarchical low rank schur complement preconditioner for indefinite linear systems. SIAM Journal on Scientific Computing40(4): A2234–A2252. DOI: 10.1137/17M1143320.
19.
DziekonskiARewienskiMSypekP, et al. (2017) GPU-accelerated LOBPCG method with inexact null-space filtering for solving generalized eigenvalue problems in computational electromagnetics analysis with higher-order fem. Communications in Computational Physics22(4): 997–1014. DOI: 10.4208/cicp.OA-2016-0168.
20.
ErlanggaYAOosterleeCWVuikC (2006a) A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM Journal on Scientific Computing27(4): 1471–1492. DOI: 10.1137/040615195.
21.
ErlanggaYAVuikCOosterleeCW (2006b) Comparison of multigrid and incomplete LU shifted-laplace preconditioners for the inhomogeneous Helmholtz equation. Applied Numerical Mathematics56(5): 648–666. DOI: 10.1016/j.apnum.2005.04.039.
22.
FalgoutRDVassilevskiPS (2004) On generalizing the algebraic multigrid framework. SIAM Journal on Numerical Analysis42(4): 1669–1693. DOI: 10.1137/S0036142903429742.
23.
FalgoutRDYangUM (2002) hypre: a library of high performance preconditioners. In: International Conference on Computational Science, Amsterdam, The Netherlands, 21–24 April, 2002, pp. 632–641, Springer.
24.
FarhatCLesoinneMLeTallecP, et al. (2001) Feti-dp: a dual–primal unified feti method—part I: a faster alternative to the two-level feti method. International Journal for Numerical Methods in Engineering50(7): 1523–1544.
25.
GaidamourJHénonP (2008) HIPS: a parallel hybrid direct/iterative solver based on a Schur complement approach. In: Sparse Days at CERFACS, Workshop of Vecpar 08, Toulouse, France, 23–24 June, 2008.
26.
GandhamREslerKZhangY (2014) A GPU accelerated aggregation algebraic multigrid method. Computers & Mathematics with Applications68(10): 1151–1160. DOI: 10.1016/j.camwa.2014.08.022.
GeorgeA (1973) Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis10(2): 345–363. DOI: 10.1137/0710032.
29.
GibbsNEPooleWGJrStockmeyerPK (1976) An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM Journal on Numerical Analysis13(2): 236–250.
30.
HeinleinAKlawonnALanserM, et al. (2021) Combining machine learning and adaptive coarse spaces—a hybrid approach for robust feti-dp methods in three dimensions. SIAM Journal on Scientific Computing43(5): S816–S838.
HysomDPothenA (1999) Efficient parallel computation of ILU(k) preconditioners. In: Proceedings of the 1999 ACM/IEEE Conference on Supercomputing, SC ’99. New York, NY, USA: Association for Computing Machinery, p. 29. DOI: 10.1145/331532.331561.
33.
KarypisGKumarV (1997) Parallel threshold-based ILU factorization. In: SC’97: Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, San Jose, CA, USA, 15–21 November, 1997, p. 28, IEEE.
34.
KarypisGKumarV (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing20(1): 359–392. DOI: 10.1137/S1064827595287997.
LeónEA (2017) Mpibind: a memory-centric affinity algorithm for hybrid applications. In: Proceedings of the International Symposium on Memory Systems, MEMSYS ’17. New York, NY, USA: Association for Computing Machinery, 262–264. DOI: 10.1145/3132402.3132415.
40.
LiRSaadY (2013) GPU-accelerated preconditioned iterative linear solvers. The Journal of Supercomputing63: 443–466. DOI: 10.1007/s11227-012-0825-3.
41.
LiZSaadYSosonkinaM (2003) parms: a parallel version of the algebraic recursive multilevel solver. Numerical Linear Algebra with Applications10(5-6): 485–509.
42.
LiRXiYErlandsonL, et al. (2019) The eigenvalues slicing library (EVSL): algorithms, implementation, and software. SIAM Journal on Scientific Computing41(4): C393–C415. DOI: 10.1137/18M1170935.
43.
LiuXXiYSaadY, et al. (2020) Solving the three-dimensional high-frequency Helmholtz equation using contour integration and polynomial preconditioning. SIAM Journal on Matrix Analysis and Applications41(1): 58–82. DOI: 10.1137/18M1228128.
44.
LuoLZhaoYCaiXC (2012) A hybrid implementation of two-level domain decomposition algorithm for solving elliptic equation on CPU/GPUs. In: 2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies, Beijing, China, 14-16 December 2012, pp. 474–477, IEEE.
45.
Magolu Monga MadeMBeauwensRWarzéeG (2000) Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix. Communications in Numerical Methods in Engineering16(11): 801–817. DOI: 10.1016/j.apnum.2009.09.003.
46.
MandelJDohrmannCR (2003) Convergence of a balancing domain decomposition by constraints and energy minimization. Numerical Linear Algebra with Applications10(7): 639–659.
47.
ManteuffelTA (1980) An incomplete factorization technique for positive definite linear systems. Mathematics of Computation34(150): 473–497.
48.
NaumovM (2011) Parallel solution of sparse triangular linear systems in the preconditioned iterative methods on the GPU. NVIDIA Corp., Westford, MA, USA, Tech. Rep. NVR-2011 1.
49.
NaumovMArsaevMCastonguayP, et al. (2015a) AmgX: a library for GPU accelerated algebraic multigrid and preconditioned iterative methods. SIAM Journal on Scientific Computing37(5): S602–S626. DOI: 10.1137/140980260.
50.
NaumovMCastonguayPCohenJ (2015b) Parallel graph coloring with applications to the incomplete-LU factorization on the GPU. Nvidia White Paper.
51.
NievinskiICLSouzaMGoldfeldP, et al. (2018) Parallel implementation of a two-level algebraic ILU(k)-based domain decomposition preconditioner. TEMA19(1): 59–77.
PothenASimonHDLiouKP (1990) Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analysis and Applications11: 430–452. DOI: 10.1137/0611030.
54.
RajamanickamSBomanEGHerouxMA (2012) Shylu: a hybrid-hybrid solver for multicore platforms. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium, Shanghai, China, 21–25 May 2012, pp. 631–643, IEEE.
RichterCSchöpsSClemensM (2014) GPU acceleration of algebraic multigrid preconditioners for discrete elliptic field problems. IEEE Transactions on Magnetics50(2): 461–464. DOI: 10.1109/TMAG.2013.2283099.
57.
RuppKTilletPRudolfF, et al. (2016) ViennaCL—linear algebra library for multi- and many-core architectures. SIAM Journal on Scientific Computing38(5): S412–S439. DOI: 10.1137/15M1026419.
58.
SaadY (2003) Iterative Methods for Sparse Linear Systems, volume 82. Philadelphia: SIAM.
59.
SaadYSosonkinaM (1999) Distributed schur complement techniques for general sparse linear systems. SIAM Journal on Scientific Computing21(4): 1337–1356.
60.
SaadYZhangJ (1999) BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices. SIAM Journal on Matrix Analysis and Applications21(1): 279–299. DOI: 10.1137/S089547989834126.
61.
SaoPVuducRLiXS (2014) A distributed CPU-GPU sparse direct solver. In: European Conference on Parallel Processing, Porto, Portugal, 25–29 August, 2014, Springer, 487–498.
62.
ŠístekJOberhuberT (2023) Acceleration of a parallel bddc solver by using graphics processing units on subdomains. The International Journal of High Performance Computing Applications37(2): 151–164.
63.
SpillaneNDoleanVHauretP, et al. (2014) Abstract robust coarse spaces for systems of pdes via generalized eigenproblems in the overlaps. Numerische Mathematik126(4): 741–770.
64.
van GijzenMBErlanggaYAVuikC (2007) Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted laplacian. SIAM Journal on Scientific Computing29(5): 1942–1958. DOI: 10.1137/060661491.
65.
VassilevskiPSYangUM (2014) Reducing communication in algebraic multigrid using additive variants. Numerical Linear Algebra with Applications21(2): 275–296. DOI: 10.1002/nla.1928.
66.
WallisJR (1983) Incomplete Gaussian elimination as a preconditioning for generalized conjugate gradient acceleration. In: SPE Reservoir Simulation Symposium, San Francisco, California, November 1983, Society of Petroleum Engineers. DOI: 10.2118/12265-ms.
67.
WallisJRKendallRPLittleLE (1985) Constrained residual acceleration of conjugate residual methods. In: SPE Reservoir Simulation Symposium, Dallas, Texas, February 1985, Society of Petroleum Engineers (SPE). DOI: 10.2118/13536-MS.
68.
WangMKlieHParasharM, et al. (2009) Solving sparse linear systems on nvidia tesla GPUs. In: International Conference on Computational Science, Baton Rouge, LA, USA, 25–27 May, 2009, pp. 864–873, Springer.
69.
WangLOsei-KuffuorDFalgoutRD, et al. (2017) Multigrid reduction for coupled flow problems with application to reservoir simulation. In: SPE Reservoir Simulation Conference, Montgomery, Texas, USA, February 2017, Society of Petroleum Engineers (SPE). DOI: 10.2118/182723-MS.
70.
XiYSaadY (2017) A rational function preconditioner for indefinite sparse linear systems. SIAM Journal on Scientific Computing39(3): A1145–A1167. DOI: 10.1137/16M1078409.
71.
YamazakiI (2011) Pdslin user guide.
72.
YamazakiIHeinleinARajamanickamS (2023) An experimental study of two-level schwarz domain-decomposition preconditioners on gpus. In: 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 15–19 May, 2023, St. Petersburg, FL, USA, pp. 680–689, IEEE.
