×

Domain decomposition techniques for the parallel solution of nonsymmetric systems of elliptic boundary value problems. (English) Zbl 0694.65048

Authors’ summary: Parallel block-preconditioned domain-decomposed Krylov methods for sparse linear systems are described and illustrated on large two-dimensional model problems and Jacobian matrices from different stages of a nonlinear multicomponent problem in chemically reacting flows. The main motivation of the work is to examine the practicality of parallelization, under the domain decomposition paradigm, of the solution of systems of equations typical of implicit finite difference applications from fluid dynamics. Such systems presently lie beyond the realm of most of the theory for domain-decomposed symmetric or nonsymmetric scalar operators.
We describe techniques depending formally only on the sparsity structure of the linear operator and thus of broad applicability. Results of tests run on an Encore Multimax with up to 16 processors demonstrate their utility in the coarse-granularity parallelization of hydrocodes: parallel efficiencies in the 40 to 100 percent range are available on the largest number of processors employed over a mix of problems, relative to a serial approach employing the same iterative technique (GMRES) and preconditioner (ILU) on a single domain. These efficiencies are already competitive with results from undecomposed parallel implementations of ILU-preconditioned GMRES on the same multiprocessor, and many avenues for their improvement remain unexplored.
Reviewer: J.Albrycht

MSC:

65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
80A32 Chemically reacting flows
35J25 Boundary value problems for second-order elliptic equations

Software:

LSODA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ashcraft, C., Domain decoupled incomplete factorizations, Tech. Rept. ETA-TR-49 (1987), Boeing Computer Services
[2] Ashcraft, C.; Grimes, R., On vectorizing incomplete factorizations and SSOR preconditioners, SIAM J. Sci. Statist. Comput., 9, 122-151 (1988) · Zbl 0641.65028
[3] Axelsson, O.; Polman, B., Block preconditioning and domain decomposition methods, I, Tech. Rept. 8735 (1987), Department of Mathematics, Catholic University: Department of Mathematics, Catholic University Nijmegen, Netherlands · Zbl 0658.65094
[4] Axelsson, O.; Polman, B., Block preconditioning and domain decomposition methods, II, J. Comput. Appl. Math., 24, 55-72 (1988) · Zbl 0658.65094
[5] Baxter, D. J.; Saltz, J. H.; Schultz, M. H.; Eisenstat, S. C.; Crowley, K., An experimental study of methods for parallel preconditioned Krylov methods, Tech. Rept. 629 (1988), Computer Science Department, Yale University: Computer Science Department, Yale University New Haven, CT
[6] Bjørstad, P. E.; Widlund, O. B., Iterative methods for the solution of elliptic problems on regions partitioned into substructures, SIAM J. Numer. Anal., 23, 1097-1120 (1986) · Zbl 0615.65113
[7] Börgers, C., The Neumann-Dirichlet domain decomposition method with inexact solvers on the subdomains, Numer. Math., 55, 123-136 (1989) · Zbl 0652.65080
[8] Bramble, J. H.; Pasciak, J. E.; Schatz, A. H., The construction of preconditioners for elliptic problems by substructuring, I, Math. Comp., 47, 103-134 (1986) · Zbl 0615.65112
[9] Brown, P. N.; Hindmarsh, A. C., Matrix-free methods for stiff systems of ODEs, SIAM J. Numer. Anal., 23, 610-638 (1986) · Zbl 0615.65078
[10] Brown, P. N.; Hindmarsh, A. C., Reduced storage matrix methods in stiff ODE systems, Tech. Rept. UCRL-95088 (1987), Lawrence Livermore Nat. Lab: Lawrence Livermore Nat. Lab Livermore, CA
[11] Chan, T. F., Analysis of preconditioners for domain decomposition, SIAM J. Numer. Anal., 24, 382-390 (1987) · Zbl 0625.65100
[12] Chan, T. F., Boundary probe preconditioners for fourth order elliptic problems, (Chan, T. F.; Glowinski, R.; Périaux, J.; Widlund, O., Second International Symposium on Domain Decomposition Methods (1989), SIAM: SIAM Philadelphia, PA)
[13] Chan, T. F.; Goovaerts, D., Domain decomposition beneficial even sequentially, Tech. Rept. 88-18 (1988), UCLA: UCLA Los Angeles, CA
[14] Chan, T. F.; Hou, T. Y., Domain decomposition preconditioners for general second order elliptical operators, Tech. Rept. 88-16 (1988), UCLA: UCLA Los Angeles, CA
[15] Chan, T. F.; Jackson, K. R., Nonlinearity preconditioned Krylov subspace methods for discrete Newton algorithms, SIAM J. Sci. Statist. Comput., 5, 533-542 (1984) · Zbl 0574.65043
[16] Chan, T. F.; Keyes, D. E., Spectral versus probe interface preconditioning for convective-diffusive problems, Tech. Rept., RIACS (1989), NASA-Ames
[17] Chan, T. F.; Resasco, D., A survey of preconditioners for domain decomposition, Tech. Rept. 414. Tech. Rept. 414, Proceedings IV Coloquio de Matemáticas del CINVESTAV (1985), Computer Science Department, Yale University: Computer Science Department, Yale University New Haven, CT, Workshop in Numerical Analysis and Its Applications, Taxco, Mexico
[18] Chan, T. F.; Resasco, D., A domain-decomposed fast Poisson solver on a rectangle, SIAM J. Sci. Statist. Comput., 8, s14-s26 (1987) · Zbl 0624.65100
[19] Concus, P.; Golub, G. H.; Meurant, G., Block preconditioning for the conjugate gradient method, Tech. Rept. 14856 (1975), Lawrence Berkeley Laboratory: Lawrence Berkeley Laboratory Berkeley, CA · Zbl 0556.65022
[20] Cottle, R. W., Manifestations of the Schur complement, Linear Algebra Appl., 8, 189-211 (1974) · Zbl 0284.15005
[21] Curtis, A. R.; Powell, M. J.; Reid, J. K., On the estimation of sparse Jacobian matrices, J. Inst. Math. Appl., 13, 117-119 (1974) · Zbl 0273.65036
[22] Dryja, M., A capacitance matrix method for Dirichlet problem on polygonal region, Numer. Math., 39, 51-64 (1982) · Zbl 0478.65062
[23] Dryja, M.; Proskurowski, W., Capacitance matrix method using strips with alternating Neumann and Dirichlet boundary conditions, Appl. Numer. Math., 1, 285-298 (1985) · Zbl 0619.65094
[24] Dupont, T.; Kendall, R.; Rachford, H. H., An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal., 5, 559-573 (1968) · Zbl 0174.47603
[25] Ecder, A.; Keyes, D. E., A parametric study of the spectra and convergence rates of preconditioned generalized minimum residual schemes for convective-diffusive problems (1988)
[26] Elman, H. C.; Agrón, E., Ordering techniques for the preconditioned conjugate gradient method on parallel computers, Comput. Phys. Comm., 53, 253-269 (1989) · Zbl 0798.65038
[27] Golub, G. H.; Mayers, D., The use of preconditioning over irregular regions, (Glowinski, R.; Lions, J. L., Computing Methods in Applied Sciences and Engineering, VI (1984), North-Holland: North-Holland Amsterdam), 3-14
[28] Golub, G. H.; Overton, M. L., The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems, Numer. Math., 53, 571-594 (1988) · Zbl 0661.65033
[29] Gropp, W. D.; Keyes, D. E., Complexity of parallel implementation of domain decomposition techniques for elliptic partial differential equations, SIAM J. Sci. Statist. Comput., 9, 312-326 (1988) · Zbl 0645.65069
[30] Keyes, D. E., Domain decomposition methods for the parallel computation of reacting flows, Comput. Phys. Comm., 53, 181-200 (1989) · Zbl 0804.76066
[31] Keyes, D. E.; Gropp, W. D., A comparison of domain decomposition techniques for elliptic partial differential equations and their parallel implementation, SIAM J. Sci. Statist. Comput., 8, s166-s202 (1987) · Zbl 0619.65088
[32] Keyes, D. E.; Gropp, W. D., Domain decomposition techniques for nonsymmetric systems of elliptic boundary value problems: Examples from CFD, (Chan, T. F.; Glowinski, R.; Périaux, J.; Widlund, O., Second International Symposium on Domain Decomposition Methods (1989), SIAM: SIAM Philadelphia, PA) · Zbl 0694.65048
[33] Keyes, D. E.; Smooke, M. D., Flame sheet starting estimates for counterflow diffusion flame problems, J. Comput. Phys., 73, 267-288 (1987) · Zbl 0656.65111
[34] Keyes, D. E.; Smooke, M. D., A parallelized elliptical solver for reacting flows, (Noor, A. K., Parallel Computations and Their Impact on Mechanics (1987), ASME: ASME New York), 375-402
[35] Manteuffel, T. A., The Tchebychev iteration for nonsymmetric linear systems, Numer. Math., 28, 307-327 (1977) · Zbl 0361.65024
[36] Meijerink, J. A.; van der Vorst, H. A., Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems, J. Comput. Phys., 44, 134-155 (1981) · Zbl 0472.65028
[37] Meurant, G., Domain decomposition versus block preconditioning, (Glowinski, R.; Golub, G. H.; Meurant, G. A.; Périaux, J., First International Symposium on Domain Decomposition Methods for Partial Differential Equations (1988), SIAM: SIAM Philadelphia, PA), 231-249 · Zbl 0658.65035
[38] Przemieniecki, J. S., Matrix structural analysis of substructures, AIAA J., 1, 138-147 (1963) · Zbl 0114.17102
[39] Saad, Y.; Schultz, M., Parallel implementations of preconditioned conjugate gradient methods, Tech. Rept. YALEU/DCS/RR-425 (1985), Computer Science Department, Yale University: Computer Science Department, Yale University New Haven, CT
[40] Saad, Y.; Schultz, M. H., GMRES: A generalized minimum residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[41] Smooke, M. D., Solution of burner-stabilized pre-mixed laminar flames by boundary value methods, J. Comput. Phys., 48, 72-105 (1982) · Zbl 0492.65065
[42] Underwood, R. R., An approximate factorization procedure based on the block Cholesky decomposition and its use with the conjugate gradient method, Tech. Rept. NEDO-11386 (1976), General Electric Co., Nuclear Energy Div
[43] Walker, H. F., Implementation of the GMRES method using Householder transformations, SIAM J. Sci. Statist. Comput., 9, 152-163 (1988) · Zbl 0698.65021
[44] Watts, J. W., A conjugate gradient-truncated direct method for the iterative solution of the reservoir simulation pressure equation, Soc. Petrol. Engrs. J., 21, 345-353 (1981)
[45] Widlund, O. B., Iterative substructuring methods: Algorithms and theory for elliptic problems in the plane, (Glowinski, R.; Golub, G. H.; Meurant, G. A.; Périaux, J., First International Symposium on Domain Decomposition Methods for Partial Differential Equations (1988), SIAM: SIAM Philadelphia, PA), 113-128
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.