×

An efficient preconditioned CG method for the solution of a class of layered problems with extreme contrasts in the coefficients. (English) Zbl 0945.76048

Summary: We present mathematical model for the prediction of fluid pressures by a time-dependent diffusion equation. Application of the finite element method leads to a system of linear equations. A complication is that the underground consists of layers with very large differences in permeability. This implies that the symmetric and positive definite coefficient matrix has a very large condition number. Bad convergence behavior of the CG method has been observed; moreover, a classical termination criterion is not valid in this problem. After diagonal scaling of the matrix, the number of extreme eigenvalues is reduced and is proved to be equal to the number of layers with a high permeability. For the IC preconditioner we observe the same behavior. To annihilate the effect of the extreme eigenvalues, a deflated CG method is used. The convergence rate improves considerably and the termination criterion becomes again reliable. Finally, we propose a cheap approximation of the eigenvectors.

MSC:

76M10 Finite element methods applied to problems in fluid mechanics
76S05 Flows in porous media; filtration; seepage
76R50 Diffusion
86A05 Hydrology, hydrography, oceanography
65F10 Iterative numerical methods for linear systems

Software:

DRIC; ILUM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alcouffe, R. E.; Brandt, A.; Dendy, J. E.; Painter, J. W., The multigrid method for diffusion equations with strongly discontinuous coefficients, SIAM J. Sci. Stat. Comput., 2, 430 (1981) · Zbl 0474.76082
[2] M. Arioli, and, D. Ruiz, Block Conjugate Gradient with subspace iteration for solving linear systems, in, Iterative Methods in Linear Algebra II, Proceedings of the Second IMACS International Symposium on Iterative Methods in Linear Algebra, Blagoevgrad, Bulgaria, June 17-20, 1995, edited by, S. D. Margenov and P. S. Vassilevski, IMACS Series in Computational and Applied Mathematics, IMACS, Piscataway, NJ, 1996, Vol, 3, p, 64.; M. Arioli, and, D. Ruiz, Block Conjugate Gradient with subspace iteration for solving linear systems, in, Iterative Methods in Linear Algebra II, Proceedings of the Second IMACS International Symposium on Iterative Methods in Linear Algebra, Blagoevgrad, Bulgaria, June 17-20, 1995, edited by, S. D. Margenov and P. S. Vassilevski, IMACS Series in Computational and Applied Mathematics, IMACS, Piscataway, NJ, 1996, Vol, 3, p, 64.
[3] Axelsson, O., Iterative Solution Methods (1994) · Zbl 0795.65014
[4] Axelsson, O.; Lindskog, G., On the eigenvalue distribution of a class of preconditioning methods, Numer. Math., 48, 479 (1986) · Zbl 0564.65016
[5] J. Baglama, D. Calvetti, G. H. Golub, and, L. Reichel, Adaptively preconditioned GMRES algorithms, SCCM-96-15, Stanford University, Stanford, 1996.; J. Baglama, D. Calvetti, G. H. Golub, and, L. Reichel, Adaptively preconditioned GMRES algorithms, SCCM-96-15, Stanford University, Stanford, 1996. · Zbl 0954.65026
[6] Bear, J., Dynamics of Fluids in Porous Media (1972) · Zbl 1191.76001
[7] Botta, E. F.F; Dekker, K.; Notay, Y.; van der Ploeg, A.; Vuik, C.; Wubs, F. W.; de Zeeuw, P. M., How fast the Laplace equation was solved in 1995, Appl. Numer. Meth., 24, 439 (1997) · Zbl 0891.65112
[8] Brown, P. N.; Walker, H. F., GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18, 37 (1997) · Zbl 0876.65019
[9] Burrage, K.; Erhel, J.; Pohl, B., A deflation technique for linear systems of equations, SIAM J. Sci. Comp. (1997) · Zbl 0914.65025
[10] Chapman, A.; Saad, Y., Deflated and augmented Krylov subspace techniques, Numer. Linear Algebra Appl., 4, 43 (1997) · Zbl 0889.65028
[11] Coomer, R. K.; Graham, I. G., Massively parallel methods for semiconductor device modelling, Computing, 56, 1 (1996) · Zbl 0861.65111
[12] Deuflhard, P.; Lipnikov, K., Domain decomposition with subdomain CCG for material jump elliptic problems, East-West J. Numer. Math., 6, 81 (1998) · Zbl 0921.65077
[13] Erhel, J.; Burrage, K.; Pohl, B., Restarted GMRES preconditioned by deflation, J. Comp. Appl. Math., 69, 303 (1996) · Zbl 0854.65025
[14] Giles, Melvyn R., Diagenesis: A Quantitative Perspective; Implications for Basin Modelling and Rock Property Prediction (1997)
[15] I. G. Graham, and, M. J. Hagger, Additive Schwarz, CG and discontinuous coefficients, in, Proceedings of 9th International Conference on Domain Decomposition, edited by, P. Bjorstad, M. Espedal, and D. Keyes, (to appear).; I. G. Graham, and, M. J. Hagger, Additive Schwarz, CG and discontinuous coefficients, in, Proceedings of 9th International Conference on Domain Decomposition, edited by, P. Bjorstad, M. Espedal, and D. Keyes, (to appear). · Zbl 0943.65147
[16] Graham, I. G.; Hagger, M. J., Unstructured additive Schwarz-CG method for elliptic problems with highly discontinuous coefficients Preprint 96/08, SIAM J. Sci. Comput. (1996) · Zbl 0943.65147
[17] Gustafsson, I., A class of first order factorization methods, BIT, 18, 142 (1978) · Zbl 0386.65006
[18] Hagger, M. J., Iterative Solution of Large, Sparse Systems of Equations, Arising in Groundwater Flow Models (1995)
[19] B. Heise, Parallel solvers for the FEM-BEM equations with applications to non-linear magnetic field problems, in, Numerical treatment of coupled systems, Proceedings of the Eleventh GAMM-Seminar, Kiel, January, 20-22, 1995, edited by, W. Hackbusch and G. Wittum, Notes on Numerical Fluid Mechanics, Vieweg, Brannschweig, 1995, Vol, 51, p, 73.; B. Heise, Parallel solvers for the FEM-BEM equations with applications to non-linear magnetic field problems, in, Numerical treatment of coupled systems, Proceedings of the Eleventh GAMM-Seminar, Kiel, January, 20-22, 1995, edited by, W. Hackbusch and G. Wittum, Notes on Numerical Fluid Mechanics, Vieweg, Brannschweig, 1995, Vol, 51, p, 73.
[20] Hestenes, M. R.; Stiefel, E., Methods of Conjugate Gradients for solving linear systems, J. Res. Nat. Bur. Stand., 49, 409 (1952) · Zbl 0048.09901
[21] Victoria, E. Howle, and, Stephen, A. Vavasis, Preconditioning complex-symmetric layered systems arising in electrical power modeling, in, Fifth Copper Mountain Conference on Iterative Methods, Copper Mountain, Colorado, March 30-April 3, 1998, edited by, T. A. Manteuffel and S. F. McCormick, 1998.; Victoria, E. Howle, and, Stephen, A. Vavasis, Preconditioning complex-symmetric layered systems arising in electrical power modeling, in, Fifth Copper Mountain Conference on Iterative Methods, Copper Mountain, Colorado, March 30-April 3, 1998, edited by, T. A. Manteuffel and S. F. McCormick, 1998.
[22] Kaasschieter, E. F., A practical termination criterion for the Conjugate Gradient method, BIT, 28, 308 (1988) · Zbl 0648.65026
[23] Kaasschieter, E. F., Preconditioned Conjugate Gradients for solving singular systems, J. Comp. Appl. Math., 24, 265 (1988) · Zbl 0659.65031
[24] Kharchenko, S. A.; Yeremin, A. Yu, Eigenvalue translation based preconditioners for the GMRES(k) method, Numer. Lin. Alg. Appl., 2, 51 (1995) · Zbl 0829.65036
[25] Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1973) · Zbl 0241.90052
[26] Meijerink, J. A.; Van der Vorst, H. A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comput., 31, 148 (1977) · Zbl 0349.65020
[27] Morgan, R. B., A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl., 16, 1154 (1995) · Zbl 0836.65050
[28] Mulyarchik, S. G.; Bielawski, S. S.; Popov, A. V., Efficient computational schemes of the Conjugate Gradient method for solving linear systems, J. Comput. Phys., 110, 201 (1994) · Zbl 0805.65035
[29] Nicolaides, R. A., Deflation of Conjugate Gradients with applications to boundary value problems, SIAM J. Numer. Anal., 24, 355 (1987) · Zbl 0624.65028
[30] Notay, Y., Incomplete factorizations of singular linear systems, BIT, 29, 682 (1989) · Zbl 0687.65028
[31] Notay, Y., DRIC: A dynamic version of the RIC method, J. Numer. Linear Algebra, 1, 511 (1994) · Zbl 0839.65030
[32] Saad, Y., ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput., 17, 830 (1996) · Zbl 0858.65029
[33] Saad, Y., Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 18, 435 (1997) · Zbl 0871.65026
[34] Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856 (1986) · Zbl 0599.65018
[35] Saad, Y.; Yeung, M.; Ehrel, J.; Guyomarc’h, F., A Deflated Version of the Conjugate Gradient Algorithm (1998)
[36] Shroff, G.; Keller, H. B., Stabilization of unstable procedures: The recursive projection method, SIAM J. Numer. Anal., 30, 1099 (1993) · Zbl 0789.65037
[37] van der Ploeg, A.; Botta, E. F.F; Wubs, F. W., Nested grids ILU-decomposition (NGILU), J. Comput. Appl. Math., 66, 515 (1996) · Zbl 0858.65028
[38] van der Sluis, A.; van der Vorst, H. A., The rate of convergence of Conjugate Gradients, Numer. Math., 48, 543 (1986) · Zbl 0596.65015
[39] H. van der Veen, K. Vuik, and, R. de Borst, Post-bifurcation behavior in soil plasticity: Eigenvector perturbation compared to deflation, in, Computational Plasticity; Fundamentals and Applications, Part 2, Proceedings of the Fifth International Conference on Computational Plasticity, Barcelona, Spain, 17-20 March, 1997, edited by, D. R. J. Owen, E. Onate, and E. Hinton, p, 1745, CIMNE, Barcelona, 1997.; H. van der Veen, K. Vuik, and, R. de Borst, Post-bifurcation behavior in soil plasticity: Eigenvector perturbation compared to deflation, in, Computational Plasticity; Fundamentals and Applications, Part 2, Proceedings of the Fifth International Conference on Computational Plasticity, Barcelona, Spain, 17-20 March, 1997, edited by, D. R. J. Owen, E. Onate, and E. Hinton, p, 1745, CIMNE, Barcelona, 1997.
[40] Vuik, C.; Segal, A.; Meijerink, J. A., An Efficient Preconditioned CG Method for the Solution of Layered Problems with Extreme Contrasts in the Coefficients (1998) · Zbl 0945.76048
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.