×

Effective matrix-free preconditioning for the augmented immersed interface method. (English) Zbl 1349.65112

Summary: We present effective and efficient matrix-free preconditioning techniques for the augmented immersed interface method (AIIM). AIIM has been developed recently and is shown to be very effective for interface problems and problems on irregular domains. GMRES is often used to solve for the augmented variable(s) associated with a Schur complement A in AIIM that is defined along the interface or the irregular boundary. The efficiency of AIIM relies on how quickly the system for A can be solved. For some applications, there are substantial difficulties involved, such as the slow convergence of GMRES (particularly for free boundary and moving interface problems), and the inconvenience in finding a preconditioner (due to the situation that only the products of A and vectors are available). Here, we propose matrix-free structured preconditioning techniques for AIIM via adaptive randomized sampling, using only the products of A and vectors to construct a hierarchically semiseparable matrix approximation to A. Several improvements over existing schemes are shown so as to enhance the efficiency and also avoid potential instability. The significance of the preconditioners includes: (1) they do not require the entries of A or the multiplication of \(\mathbf{A}^T\) with vectors; (2) constructing the preconditioners needs only \(O(\log N)\) matrix-vector products and \(O(N)\) storage, where \(N\) is the size of A; (3) applying the preconditioners needs only \(O(N)\) flops; (4) they are very flexible and do not require any a priori knowledge of the structure of A. The preconditioners are observed to significantly accelerate the convergence of GMRES, with heuristical justifications of the effectiveness.comprehensive tests on several important applications are provided, such as Navier-Stokes equations on irregular domains with traction boundary conditions, interface problems in incompressible flows, mixed boundary problems, and free boundary problems. The preconditioning techniques are also useful for several other problems and methods.

MSC:

65F08 Preconditioners for iterative methods
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N06 Finite difference methods for boundary value problems involving PDEs

Software:

IIMPACK; SPIKE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bell, J. B.; Colella, P.; Glaz, H. M., A second-order projection method for the incompressible Navier-Stokes equations, J. Comput. Phys., 85, 257-283 (1989) · Zbl 0681.76030
[2] Bellavia, S.; Gondzio, J.; Morini, B., A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems, SIAM J. Sci. Comput., 35, A192-A211 (2013) · Zbl 1264.65036
[3] Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034
[4] Cullum, J.; Tůma, M., Matrix-free preconditioning using partial matrix estimation, BIT Numer. Math., 46, 711-729 (2006) · Zbl 1105.65046
[5] Le Borne, S.; Grasedyck, L., \(H\)-matrix preconditioners in convection-dominated problems, SIAM J. Matrix Anal. Appl., 27, 1172-1183 (2006) · Zbl 1102.65051
[6] Chandrasekaran, S.; Dewilde, P.; Gu, M.; Pals, T., A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl., 28, 603-622 (2006) · Zbl 1120.65031
[7] Duintjer Tebbens, J.; Tůma, M., Preconditioner updates for solving sequences of linear systems in matrix-free environment, Numer. Linear Algebra Appl., 17, 997-1019 (2010) · Zbl 1240.65092
[8] Engquist, B.; Ying, L., Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation, Pure Appl. Math., LXIV, 0697-0735 (2011)
[9] Giraud, L.; Haidar, A., Parallel algebraic hybrid solvers for large 3D convection-diffusion problems, Numer. Algorithms, 51, 151-177 (2009) · Zbl 1167.65355
[10] Gondzio, J., Matrix-free interior point method, Comput. Optim. Appl., 51, 457-480 (2012) · Zbl 1241.90179
[11] Grasedyck, L.; Kriemann, R.; Le Borne, S., Parallel black box \(H\)-LU preconditioning for elliptic boundary value problems, Comput. Vis. Sci., 11, 273-291 (2008)
[12] Greenbaum, A.; Pták, V.; Strakoš, Z., Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17, 465-469 (1996) · Zbl 0857.65029
[13] Gu, M.; Eisenstat, S. C., Efficient algorithms for computing a strong-rank revealing QR factorization, SIAM J. Sci. Comput., 17, 848-869 (1996) · Zbl 0858.65044
[14] Gu, M.; Li, X. S.; Vassilevski, P. S., Direction-preserving and Schur-monotonic semiseparable approximations of symmetric positive definite matrices, SIAM J. Matrix Anal. Appl., 31, 2650-2664 (2010) · Zbl 1209.65033
[15] Halko, N.; Martinsson, P. G.; Tropp, J., Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 217-288 (2011) · Zbl 1269.65043
[16] Hou, T.; Li, Z.; Osher, S.; Zhao, H., A hybrid method for moving interface problems with application to the Hele-Shaw flow, J. Comput. Phys., 134, 236-252 (1997) · Zbl 0888.76067
[17] Hunter, J.; Li, Z.; Zhao, H., Autophobic spreading of drops, J. Comput. Phys., 183, 335-366 (2002) · Zbl 1046.76036
[18] Li, R.; Saad, Y., Divide and conquer low-rank preconditioners for symmetric matrices, SIAM J. Sci. Comput., 35, A2069-A2095 (2013) · Zbl 1362.65036
[19] Li, Z., A fast iterative algorithm for elliptic interface problems, SIAM J. Numer. Anal., 35, 230-254 (1998) · Zbl 0915.65121
[20] Li, Z.; Cai, Q.; Zhao, H.; Luo, R., A semi-implicit augmented IIM for Navier-Stokes equations with open and traction boundary conditions, J. Comput. Phys., 297 (2015) · Zbl 1349.76498
[21] Li, Z.; Ito, K., The Immersed Interface Method - Numerical Solutions of PDEs Involving Interfaces and Irregular Domains, SIAM Frontier Series in Applied Mathematics, vol. FR33 (2006)
[22] Li, Z.; Ito, K.; Lai, M.-C., An augmented approach for Stokes equations with a discontinuous viscosity and singular forces, Comput. Fluids, 36, 622-635 (2007) · Zbl 1177.76291
[23] Li, Z.; Lai, M.-C.; He, G.; Zhao, H., An augmented method for free boundary problems with moving contact lines, Comput. Fluids, 39, 1033-1040 (2010) · Zbl 1242.76047
[24] Li, Z.; Lai, M.-C., New finite difference methods based on IIM for inextensible interfaces in incompressible flows, ESIAM Appl. Math., 1, 155-171 (2011) · Zbl 1302.76131
[26] Li, Z.; Zhao, H.; Gao, H., A numerical study of electro-migration voiding by evolving level set functions on a fixed Cartesian grid, J. Comput. Phys., 152, 281-304 (1999) · Zbl 0956.78016
[27] Liberty, E.; Woolfe, F.; Martinsson, P. G.; Rokhlin, V.; Tygert, M., Randomized algorithms for the low-rank approximation of matrices, Proc. Natl. Acad. Sci. USA, 104, 20167-20172 (2007) · Zbl 1215.65080
[28] Lin, L.; Lu, J.; Ying, L., Fast construction of hierarchical matrix representation from matrix-vector multiplication, J. Comput. Phys., 230, 4071-4087 (2011) · Zbl 1218.65038
[29] Liu, J., Open and traction boundary conditions for the incompressible Navier-Stokes equations, J. Comput. Phys., 228, 7250-7267 (2009) · Zbl 1386.76114
[30] Liu, X.; Xia, J.; de Hoop, M. V., Parallel randomized and matrix-free direct solvers for large structured dense linear systems, SIAM J. Sci. Comput. (2015), submitted for publication
[31] Lukšan, L.; Vlček, Jan, Efficient tridiagonal preconditioner for the matrix-free truncated Newton method, Appl. Math. Comput., 235, 394-407 (2014) · Zbl 1334.65113
[32] Martinsson, P. G., A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix, SIAM J. Matrix Anal. Appl., 32, 1251-1274 (2011) · Zbl 1237.65028
[33] Pan, V. Y.; Ivolgin, D.; Murphy, B.; Rosholt, R. E.; Tang, Y.; Yan, X., Additive preconditioning for matrix computations, Linear Algebra Appl., 432, 1070-1089 (2010) · Zbl 1191.65024
[34] Pan, V. Y.; Qian, G., Randomized preprocessing of homogeneous linear systems of equations, Linear Algebra Appl., 432, 3272-3318 (2010) · Zbl 1202.65038
[35] Peskin, C. S., The immersed boundary method, Acta Numer., 11, 479-517 (2002) · Zbl 1123.74309
[36] Polizzi, E.; Sameh, A. H., A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Comput., 32, 177-194 (2006)
[37] Saad, Y., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[38] Vecharynski, E.; Langou, J., Any admissible cycle-convergence behavior is possible for restarted GMRES at its initial cycles, Numer. Linear Algebra Appl., 18, 499-511 (2011) · Zbl 1249.65073
[39] Vogel, J.; Xia, J.; Cauley, S.; Balakrishnan, V., Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions, SIAM J. Sci. Comput. (2015), submitted for publication
[40] Woolfe, F.; Liberty, E.; Rokhlin, V.; Tygert, M., A fast randomized algorithm for approximation of matrices, Appl. Comput. Harmon. Anal., 25, 335-366 (2008) · Zbl 1155.65035
[41] Wu, G.; Xu, W.; Zhang, Y.; Wei, Y., A preconditioned conjugate gradient algorithm for GeneRank with application to microarray data mining, Data Min. Knowl. Discov., 26, 27-56 (2013) · Zbl 1260.68351
[42] Xi, Y.; Xia, J.; Chan, R., A fast randomized eigensolver with structured LDL factorization update, SIAM J. Matrix Anal. Appl., 35, 974-996 (2014) · Zbl 1305.65125
[43] Xia, J., On the complexity of some hierarchical structured matrix algorithms, SIAM J. Matrix Anal. Appl., 33, 388-410 (2012) · Zbl 1250.65050
[44] Xia, J., Randomized sparse direct solvers, SIAM J. Matrix Anal. Appl., 34, 197-227 (2013) · Zbl 1269.65029
[45] Xia, J., Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput., 35, A832-A860 (2013) · Zbl 1266.15022
[46] Xia, J.; Chandrasekaran, S.; Gu, M.; Li, X. S., Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17, 953-976 (2010) · Zbl 1240.65087
[47] Xia, J.; Gu, M., Robust approximate Cholesky factorization of rank-structured symmetric positive definite matrices, SIAM J. Matrix Anal. Appl., 31, 2899-2920 (2010) · Zbl 1217.65061
[48] Xia, J.; Xi, Y.; Gu, M., A superfast structured solver for Toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl., 33, 837-858 (2012) · Zbl 1258.65030
[49] Ying, W.-J.; Henriquez, C. S., A kernel-free boundary integral method for elliptic boundary value problems, J. Comput. Phys., 227, 1046-1074 (2007) · Zbl 1128.65102
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.