Matrix-equation-based strategies for convection-diffusion equations. (English) Zbl 1341.65042
Summary: We are interested in the numerical solution of nonsymmetric linear systems arising from the discretization of convection-diffusion partial differential equations with separable coefficients, dominant convection and rectangular or parallelepipedal domain. Preconditioners based on the matrix equation formulation of the problem are proposed, which naturally approximate the original discretized problem. For the considered setting, we show that the explicit solution of the matrix equation can effectively replace the linear system solution. Numerical experiments with data stemming from two and three dimensional problems are reported, illustrating the potential of the proposed methodology.
MSC:
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 35J25 | Boundary value problems for second-order elliptic equations |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
Keywords:
convection-diffusion equations; iterative solvers; preconditioning; matrix equations; finite difference method; finite element method; nonsymmetric linear system; numerical experimentReferences:
| [1] | Axelsson, O., Karátson, J.: Symmetric part preconditioning for the conjugate gradient method in Hilbert space. Numer. Funct. Anal. Optim. 24(5-6), 455-474 (2003) · Zbl 1054.65055 · doi:10.1081/NFA-120023867 |
| [2] | Axelsson, O., Karátson, J.: Mesh independent superlinear PCG rates via compact-equivalent operators. SIAM J. Numer. Anal. 45(4), 1945-1516 (2007) · Zbl 1151.65081 · doi:10.1137/06066391X |
| [3] | Bartels, R.H., Stewart, G.W.: Algorithm 432: solution of the matrix equation \[AX+XB=C\] AX+XB=C. Commun. ACM 15(9), 820-826 (1972) · Zbl 1372.65121 · doi:10.1145/361573.361582 |
| [4] | Benner, Peter, Damm, Tobias: Lyapunov equations, energy functionals, and model order reduction of bilinear and stochastic systems. SIAM J. Control Optim. 49(2), 686-711 (2011) · Zbl 1217.93158 · doi:10.1137/09075041X |
| [5] | Bickley, W.G., McNamee, J.: Matrix and other direct methods for the solution of linear difference equation. Philos. Trans. Roy. Soc. Lond. Ser. A 252, 69-131 (1960) · Zbl 0092.13001 · doi:10.1098/rsta.1960.0001 |
| [6] | Boyle, J., Mihajlović, M.D., Scott, J.A.: HSL_MI20: an efficient AMG preconditioner for finite element problems in 3D. Int. J. Numer. Meth. Eng. 82(1), 64-98 (2010) · Zbl 1183.76799 |
| [7] | Breiten, T., Simoncini, V., Stoll, M.: Fast iterative solvers for fractional differential equations. Technical report, Alma Mater Studiorum - Università di Bologna (2014) · Zbl 1338.65071 |
| [8] | Chin, R.C.Y., Manteuffel, T.A., De Pillis, J.: ADI as a preconditioning for solving the convection-diffusion equation. SIAM J. Sci. Stat. Comput. 5(2), 281-299 (1984) · Zbl 0549.65068 · doi:10.1137/0905020 |
| [9] | Dolgov, S.V., Savostyanov, D.V.: Alternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems (2013). arXiv:1304.1222v2 |
| [10] | Dolgov, S.V., Savostyanov, D.V.: Alternating minimal energy methods for linear systems in higher dimensions. SIAM J. Sci. Comput. 36(5), A2248-A2271 (2014) · Zbl 1307.65035 · doi:10.1137/140953289 |
| [11] | Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Clarendon Press, Oxford (1989) · Zbl 0666.65024 |
| [12] | Ellner, N.S., Wachspress, E.L.: New ADI model problem applications. In: Proceedings of 1986 ACM Fall Joint Computer Conference, Dallas, Texas, United States, pp. 528-534. IEEE Computer Society Press, Los Alamitos (1986) · Zbl 1217.93158 |
| [13] | Elman, H.C., Golub, G.H.: Iterative methods for cyclically reduced non-self-adjoint linear systems. Math. Comput. 54(190), 671-700 (1990) · Zbl 0699.65021 |
| [14] | Elman, H.C., Ramage, A.: A characterisation of oscillations in the discrete two-dimensional convection-diffusion equation. Math. Comput. 72(241), 263-288 (2001) · Zbl 1008.65083 · doi:10.1090/S0025-5718-01-01392-8 |
| [15] | Elman, H.C., Ramage, A.: An analysis of smoothing effects of upwinding strategies for the convection-diffusion equation. SIAM J. Numer. Anal. 40(1), 254-281 (2002) · Zbl 1017.65090 · doi:10.1137/S0036142901374877 |
| [16] | Elman, H.C., Ramage, A., Silvester, D.J.: IFISS: a matlab toolbox for modelling incompressible flow. ACM Trans. Math. Softw. 33(2) Article 14, (2007) · Zbl 1365.65326 |
| [17] | Elman, H.C., Schultz, M.H.: Preconditioning by fast direct methods for nonself-adjoint nonseparable elliptic equations. SIAM J. Numer. Anal. 23(1), 44-57 (1986) · Zbl 0619.65093 · doi:10.1137/0723004 |
| [18] | Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite elements and fast iterative solvers, with applications in incompressible fluid dynamics. In: Numerical Mathematics and Scientific Computation, 2 edn, vol. 21. Oxford University Press, NY (2014) · Zbl 1304.76002 |
| [19] | George, A., Liu, J.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Inc., Englewood Cliffs (1981) · Zbl 0516.65010 |
| [20] | Grasedyck, L.: Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure. Computing 72, 247-265 (2004) · Zbl 1058.65036 · doi:10.1007/s00607-003-0037-z |
| [21] | Grasedyck, L., Kressner, D., Tobler, Ch.: A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen 36(1), 53-78 (2013) · Zbl 1279.65045 · doi:10.1002/gamm.201310004 |
| [22] | Gunn, J.E.: The numerical solution of \[\nabla \cdot a \nabla u = f\]∇·a∇u=f by a semi-explicit alternating-direction iterative technique. Numer. Math. 6, 181-184 (1964) · Zbl 0131.14902 · doi:10.1007/BF01386066 |
| [23] | Hackbusch, W., Khoromskij, B.N., Tyrtyshnikov, E.E.: Hierarchical Kronecker tensor-product approximations. J. Numer. Math. 13(2), 119-156 (2005) · Zbl 1081.65035 · doi:10.1515/1569395054012767 |
| [24] | Khoromskij, B.N.: Tensors-structured numerical methods in scientific computing: survey on recent advances. Chemom. Intell. Lab. Syst. 110, 1-19 (2012) · doi:10.1016/j.chemolab.2011.09.001 |
| [25] | Kressner, D., Tobler, C.: Krylov subspace methods for linear systems with tensor product structure. SIAM J. Matrix Anal. Appl. 31(4), 1688-1714 (2010) · Zbl 1208.65044 · doi:10.1137/090756843 |
| [26] | Kressner, D., Uschmajew, A.: On low-rank approximability of solutions to high-dimensional operator equations and eigenvalue problem (2014). arXiv:1406.7026v1 · Zbl 1336.65093 |
| [27] | Manteuffel, T., Otto, J.: Optimal equivalent preconditioners. SIAM J. Numer. Anal. 30(3), 790-812 (1993) · Zbl 0782.65048 · doi:10.1137/0730040 |
| [28] | Manteuffel, T.A., Parter, S.V.: Preconditioning and boundary conditions. SIAM J. Numer. Anal. 27(3), 656-694 (1990) · Zbl 0713.65064 · doi:10.1137/0727040 |
| [29] | Matthies, H.G., Zander, E.: Solving stochastic systems with low-rank tensor compression. Linear Algebra Appl. 436, 3819-3838 (2012) · Zbl 1241.65016 · doi:10.1016/j.laa.2011.04.017 |
| [30] | Notay, Y.: Users Guide to AGMG, 3rd edn. In: Service de Métrologie Nucléaire Universitè Libre de Bruxelles (C.P. 165/84), 50, Av. F.D. Roosevelt, B-1050 Brussels, Belgium (2010) · Zbl 0782.65048 |
| [31] | Notay, Y.: Aggregation-based algebraic multigrid for convection-diffusion equations. SIAM J. Sci. Comput. 34(4), A2288-A2316 (2012) · Zbl 1250.76139 |
| [32] | Palitta, D.: Preconditioning strategies for the numerical solution of convection-diffusion partial differential equations. Master’s thesis, Alma Mater Studiorum - Università di Bologna (2014) |
| [33] | Saad, Y.: A flexible inner-outer preconditioned GMRES. SIAM J. Sci. Comput. 14, 461-469 (1993) · Zbl 0780.65022 · doi:10.1137/0914028 |
| [34] | Saad, Y.: Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics, Philadelphia (2003) · Zbl 1031.65046 |
| [35] | Saad, Y., Schultz, M.H.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058 |
| [36] | Shank, S.D., Simoncini, V., Szyld, D.B.: Efficient low-rank solutions of generalized Lyapunov equations. Tech.Rep. 14-11-10, Department of Mathematics, Temple University (2014) · Zbl 1348.65078 |
| [37] | Simoncini, V.: On the numerical solution of \[{AX-XB=C}\] AX-XB=C. BIT 36(4), 814-830 (1996) · Zbl 0863.65022 · doi:10.1007/BF01733793 |
| [38] | Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268-1288 (2007) · Zbl 1146.65038 · doi:10.1137/06066120X |
| [39] | Simoncini, V.: Computational methods for linear matrix equations. Technical report, Alma Mater Studiorum - Università di Bologna (2013) · Zbl 1386.65124 |
| [40] | Starke, G.: Optimal alternating direction implicit parameters for nonsymmetric systems of linear equations. SIAM J. Numer. Anal. 28(5), 1431-1445 (1991) · Zbl 0739.65029 · doi:10.1137/0728074 |
| [41] | Stynes, M.: Numerical methods for convection-diffusion problems or the 30 years war. Department of Mathematics, National University of Ireland (2013). arXiv:1306.5172v1 · Zbl 0549.65068 |
| [42] | Wachspress, E.L.: Iterative Solution of Elliptic Systems. Prentice-Hall Inc., Englewood Cliffs (1966) · Zbl 0161.12203 |
| [43] | Wachspress, E.L.: Extended application of alternating direction implicit iteration model problem theory. J. Soc. Ind. Appl. Math. 11(4), 994-1016 (1963) · Zbl 0244.65045 · doi:10.1137/0111073 |
| [44] | Wachspress, E.L.: Generalized ADI preconditioning. Comput. Math. Appl. 10(6), 405-477 (1984) · Zbl 0578.65027 · doi:10.1016/0898-1221(84)90070-1 |
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.
