Parallel solution methods and preconditioners for evolution equations
Abstract
The recent development of the high performance computer platforms shows a clear trend towards heterogeneity and hierarchy. In order to utilize the computational power, particular attention must be paid to finding new algorithms or adjust existing ones so that they better match the HPC computer architecture. In this work we consider an alternative to classical time-stepping methods based on use of time-harmonic properties and discuss solution approaches that allow efficient utilization of modern HPC resources. The method in focus is based on a truncated Fourier expansion of the solution of an evolutionary problem. The analysis is done for linear equations and it is remarked on the possibility to use two- or multilevel mesh methods for nonlinear problems, which can enable further, even higher degree of parallelization. The arising block matrix system to be solved admits a two-by-two block form with square blocks, for which a very efficient preconditioner exists. It leads to tight eigenvalue bounds for the preconditioned matrix and, hence, to a very fast convergence of a preconditioned Krylov subspace or iterative refinement method. The analytical background is shown as well as some illustrating numerical examples.
Keyword : parallel solution, evolution equation, preconditioning, PDE-constrained optimization
How to Cite
Axelsson, O., Neytcheva, M., & Liang, Z.-Z. (2018). Parallel solution methods and preconditioners for evolution equations. Mathematical Modelling and Analysis, 23(2), 287-308. https://doi.org/10.3846/mma.2018.018
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
[1] R. Alexander. Diagonally implicit Runge-Kutta methods for stiff ODEs. SIAM Journal on Numerical Analysis, 14(6):1006–1021, 1977. https://doi.org/10.1137/0714068
[2] V. Alexandrov, O. Esquivel-Flores, S. Ivanovska and A. Karaivanova. On the pre-conditioned quasi-Monte Carlo algorithm for matrix computations. In I. Lirkov, S. D. Margenov and J. Waśniewski(Eds.), International Conference on Large-Scale Scientific Computing, volume 9374, pp. 163–171, Cham, 2015. Springer. https://doi.org/10.1007/978-3-319-26520-9 17
[3] O. Axelsson. On mesh independence and Newton type methods. Applications of Mathematics, 38(4):249–265, 1993.
[4] O. Axelsson. Iterative Solution Methods. Cambridge University Press, Cambridge, 1994. https://doi.org/10.1017/CBO9780511624100
[5] O. Axelsson and V.A. Barker. Finite Element Solution of Boundary Value Problems: Theory and Computation. Society for Industrial and Applied Mathematics, 2001. https://doi.org/10.1137/1.9780898719253
[6] O. Axelsson, S. Farouq and M. Neytcheva. Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Poisson and convection-diffusion control. Numerical Algorithms, 73(3):631–663, 2016. https://doi.org/10.1007/s11075-016-0111-1
[7] O. Axelsson, S. Farouq and M. Neytcheva. Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Stokes control. Numerical Algorithms, 74(1):19–37, 2017. https://doi.org/10.1007/s11075-016-0136-5
[8] O. Axelsson, S. Farouq and M. Neytcheva. A preconditioner for optimal control problems, constrained by Stokes equation with a time-harmonic control. Journal of Computational and Applied Mathematics, 310(C):5–18, 2017. https://doi.org/10.1016/j.cam.2016.05.029
[9] O. Axelsson and W. Layton. A two-level method for the discretization of nonlinear boundary value problems. SIAM Journal on Numerical Analysis, 33(6):2359–2374, 1996. https://doi.org/10.1137/S0036142993247104
[10] O. Axelsson and D. Lukáš. Preconditioning methods for eddy current optimally controlled time-harmonic electromagnetic problems. Journal of Numerical Mathematics, 2018. https://doi.org/10.1515/jnma-2017-0064
[11] O. Axelsson and M. Neytcheva. Algebraic multilevel iteration method for Stieltjes matrices. Numerical Linear Algebra with Applications, 1(3):213–236, 1994. https://doi.org/10.1002/nla.1680010302
[12] O. Axelsson, M. Neytcheva and A. Ström. An efficient preconditioning method for state box-constrained optimal control problems. Technical report, Uppsala University, Department of Information Technology, 2017. Available from Internet: http://www.it.uu.se/research/publications/reports/2017-004/
[13] O. Axelsson and P.S. Vassilevski. Algebraic multilevel preconditioning methods. I. Numerische Mathematik, 56(2-3):157–177, 1989. https://doi.org/10.1007/BF01409783
[14] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. BMFEMe, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, D. A. May, L. Curfman McInnes, K. Rupp, B. F. Smith, S. Zampini, H. Zhang and H. Zhang. PETSc Web page, 2017. Available from Internet: http://www.mcs.anl.gov/ petsc
[15] T. V. Kolev et al. MFEM: Modular finite element methods. Available from Internet: http://mfem.org/
[16] M. Heroux, R. Bartlett, V. Howle, R Hoekstra, J. Hu, T. Kolda, R.Lehoucq, K. Long, R. Pawlowski, E. Phipps, A. Salinger, H. Thornquist, R. Tuminaro, J. Willenbring and A. Williams. An overview of Trilinos. Technical Report SAND2003-2927, Sandia National Laboratories, 2003.
[17] R. Herzog and E.W. Sachs. Preconditioned conjugate gradient method for optimal control problems with control and state constraints. SIAM Journal on Matrix Analysis and Applications, 31(5):2291–2317, 2010. https://doi.org/10.1137/090779127
[18] M. Hintermüller and M. Hinze. Moreau-Yosida regularization in state constrained elliptic control problems: error estimates and parameter adjustment. SIAM Journal on Numerical Analysis, 47(3):1666–1683, 2009. https://doi.org/10.1137/080718735
[19] G. Karypis and V. Kumar. ParMETIS-parallel graph partitioning and fill-reducing matrix ordering, 2013. Available from Internet: http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview
[20] T. V. Kolev and P.S. Vassilevski. Parallel auxiliary space AMG solver for H(curl) problems. Journal of Computational Mathematics, 27(5):604–623, 2009. https://doi.org/10.4208/jcm.2009.27.5.013
[21] M. Kollmann, M. Kolmbauer, U. Langer, M. Wolfmayr and W. Zulehner. A robust finite element solver for a multiharmonic parabolic optimal control problem. Computers & Mathematics with Applications, 65(3):469–486, 2013. https://doi.org/10.1016/j.camwa.2012.06.012
[22] M. Kolmbauer and U. Langer. A robust preconditioned MINRES solver for distributed time-periodic eddy current optimal control problems. SIAM Journal on Scientific Computing., 34(6):B785–B809, 2012. https://doi.org/10.1137/110842533
[23] U. Langer and M. Wolfmayr. Multiharmonic finite element analysis of a time-periodic parabolic optimal control problem. Journal of Numerical Mathematics, 21(4):265–300, 2013. https://doi.org/10.1515/jnum-2013-0011
[24] Lawrence Livermore National Laboratory. hypre: High Performance Preconditioners. Available from Internet: http://www.llnl.gov/CASC/hypre
[25] J.C. Nèdèlec. Mixed finite elements in R3. Numerische Mathematik, 35(3):315–341, 1980. https://doi.org/10.1007/BF01396415
[26] J.C. Nèdèlec. A new family of mixed finite elements in R3. Numerische Mathematik, 50(1):57–81, 1986. https://doi.org/10.1007/BF01389668
[27] Y. Notay. An aggregation-based algebraic multigrid method. Electronic Transactions on Numerical Analysis, 37:123–146, 2010.
[28] C.C. Paige and M.A. Saunders. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12(4):617–629, 1975. https://doi.org/10.1137/0712047
[29] J.W. Pearson, M. Stoll and A.J. Wathen. Preconditioners for state-constrained optimal control problems with Moreau-Yosida penalty function. Numerical Linear Algebra with Applications, 21(1):81–97, 2014. https://doi.org/10.1002/nla.1863
[30] A. Redlund and G. Cheng. Implementation and performance studies of a three-phase model solver. Technical report, Uppsala University, Department of Information Technology, 2013. Available from Internet: http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project13/
[31] Y. Saad. A flexible inner-outer preconditioned GMRES algorithm. SIAM Journal on Scientific Computing, 14(2):461–469, 1993. https://doi.org/10.1137/0914028
[32] Y. Saad. Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. https://doi.org/10.1137/1.9780898718003
[33] P.J. van der Houwen and B.P. Sommeijer. Analysis of parallel diagonally implicit iteration of Runge-Kutta methods. Applied Numerical Mathematics, 11(1-3):169–188, 1993. https://doi.org/10.1016/0168-9274(93)90047-U
[34] P.S. Vassilevski. Multilevel Block Factorization Preconditioners. Springer-Verlag, New York, 2008.
[35] R.Čiegis, V. Starikovičius and S. Margenov. On parallel numerical algorithms for fractional diffusion problems. In J. Carretero, J. Garsia Blas and S. Margenov(Eds.), Proceedings of the Third International Workshop on Sustainable Ultrascale Computing Systems (NESUS 2016). Universidad Carlos III de Madrid, 12 2016.
[36] R.Čiegis, V. Starikovičius, S. Margenov and R.Kriauzienė. Parallel solvers for fractional power diffusion problems. Concurrency and Computation: Practice and Experience, 29(24), 2017. https://doi.org/10.1002/cpe.4216
[37] J.-C. Xu. Two-grid discretization techniques for linear and nonlinear PDEs. SIAM Journal on Numerical Analysis., 33(5):1759–1777, 1996. https://doi.org/10.1137/S0036142992232949
[2] V. Alexandrov, O. Esquivel-Flores, S. Ivanovska and A. Karaivanova. On the pre-conditioned quasi-Monte Carlo algorithm for matrix computations. In I. Lirkov, S. D. Margenov and J. Waśniewski(Eds.), International Conference on Large-Scale Scientific Computing, volume 9374, pp. 163–171, Cham, 2015. Springer. https://doi.org/10.1007/978-3-319-26520-9 17
[3] O. Axelsson. On mesh independence and Newton type methods. Applications of Mathematics, 38(4):249–265, 1993.
[4] O. Axelsson. Iterative Solution Methods. Cambridge University Press, Cambridge, 1994. https://doi.org/10.1017/CBO9780511624100
[5] O. Axelsson and V.A. Barker. Finite Element Solution of Boundary Value Problems: Theory and Computation. Society for Industrial and Applied Mathematics, 2001. https://doi.org/10.1137/1.9780898719253
[6] O. Axelsson, S. Farouq and M. Neytcheva. Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Poisson and convection-diffusion control. Numerical Algorithms, 73(3):631–663, 2016. https://doi.org/10.1007/s11075-016-0111-1
[7] O. Axelsson, S. Farouq and M. Neytcheva. Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Stokes control. Numerical Algorithms, 74(1):19–37, 2017. https://doi.org/10.1007/s11075-016-0136-5
[8] O. Axelsson, S. Farouq and M. Neytcheva. A preconditioner for optimal control problems, constrained by Stokes equation with a time-harmonic control. Journal of Computational and Applied Mathematics, 310(C):5–18, 2017. https://doi.org/10.1016/j.cam.2016.05.029
[9] O. Axelsson and W. Layton. A two-level method for the discretization of nonlinear boundary value problems. SIAM Journal on Numerical Analysis, 33(6):2359–2374, 1996. https://doi.org/10.1137/S0036142993247104
[10] O. Axelsson and D. Lukáš. Preconditioning methods for eddy current optimally controlled time-harmonic electromagnetic problems. Journal of Numerical Mathematics, 2018. https://doi.org/10.1515/jnma-2017-0064
[11] O. Axelsson and M. Neytcheva. Algebraic multilevel iteration method for Stieltjes matrices. Numerical Linear Algebra with Applications, 1(3):213–236, 1994. https://doi.org/10.1002/nla.1680010302
[12] O. Axelsson, M. Neytcheva and A. Ström. An efficient preconditioning method for state box-constrained optimal control problems. Technical report, Uppsala University, Department of Information Technology, 2017. Available from Internet: http://www.it.uu.se/research/publications/reports/2017-004/
[13] O. Axelsson and P.S. Vassilevski. Algebraic multilevel preconditioning methods. I. Numerische Mathematik, 56(2-3):157–177, 1989. https://doi.org/10.1007/BF01409783
[14] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. BMFEMe, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, D. A. May, L. Curfman McInnes, K. Rupp, B. F. Smith, S. Zampini, H. Zhang and H. Zhang. PETSc Web page, 2017. Available from Internet: http://www.mcs.anl.gov/ petsc
[15] T. V. Kolev et al. MFEM: Modular finite element methods. Available from Internet: http://mfem.org/
[16] M. Heroux, R. Bartlett, V. Howle, R Hoekstra, J. Hu, T. Kolda, R.Lehoucq, K. Long, R. Pawlowski, E. Phipps, A. Salinger, H. Thornquist, R. Tuminaro, J. Willenbring and A. Williams. An overview of Trilinos. Technical Report SAND2003-2927, Sandia National Laboratories, 2003.
[17] R. Herzog and E.W. Sachs. Preconditioned conjugate gradient method for optimal control problems with control and state constraints. SIAM Journal on Matrix Analysis and Applications, 31(5):2291–2317, 2010. https://doi.org/10.1137/090779127
[18] M. Hintermüller and M. Hinze. Moreau-Yosida regularization in state constrained elliptic control problems: error estimates and parameter adjustment. SIAM Journal on Numerical Analysis, 47(3):1666–1683, 2009. https://doi.org/10.1137/080718735
[19] G. Karypis and V. Kumar. ParMETIS-parallel graph partitioning and fill-reducing matrix ordering, 2013. Available from Internet: http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview
[20] T. V. Kolev and P.S. Vassilevski. Parallel auxiliary space AMG solver for H(curl) problems. Journal of Computational Mathematics, 27(5):604–623, 2009. https://doi.org/10.4208/jcm.2009.27.5.013
[21] M. Kollmann, M. Kolmbauer, U. Langer, M. Wolfmayr and W. Zulehner. A robust finite element solver for a multiharmonic parabolic optimal control problem. Computers & Mathematics with Applications, 65(3):469–486, 2013. https://doi.org/10.1016/j.camwa.2012.06.012
[22] M. Kolmbauer and U. Langer. A robust preconditioned MINRES solver for distributed time-periodic eddy current optimal control problems. SIAM Journal on Scientific Computing., 34(6):B785–B809, 2012. https://doi.org/10.1137/110842533
[23] U. Langer and M. Wolfmayr. Multiharmonic finite element analysis of a time-periodic parabolic optimal control problem. Journal of Numerical Mathematics, 21(4):265–300, 2013. https://doi.org/10.1515/jnum-2013-0011
[24] Lawrence Livermore National Laboratory. hypre: High Performance Preconditioners. Available from Internet: http://www.llnl.gov/CASC/hypre
[25] J.C. Nèdèlec. Mixed finite elements in R3. Numerische Mathematik, 35(3):315–341, 1980. https://doi.org/10.1007/BF01396415
[26] J.C. Nèdèlec. A new family of mixed finite elements in R3. Numerische Mathematik, 50(1):57–81, 1986. https://doi.org/10.1007/BF01389668
[27] Y. Notay. An aggregation-based algebraic multigrid method. Electronic Transactions on Numerical Analysis, 37:123–146, 2010.
[28] C.C. Paige and M.A. Saunders. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12(4):617–629, 1975. https://doi.org/10.1137/0712047
[29] J.W. Pearson, M. Stoll and A.J. Wathen. Preconditioners for state-constrained optimal control problems with Moreau-Yosida penalty function. Numerical Linear Algebra with Applications, 21(1):81–97, 2014. https://doi.org/10.1002/nla.1863
[30] A. Redlund and G. Cheng. Implementation and performance studies of a three-phase model solver. Technical report, Uppsala University, Department of Information Technology, 2013. Available from Internet: http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project13/
[31] Y. Saad. A flexible inner-outer preconditioned GMRES algorithm. SIAM Journal on Scientific Computing, 14(2):461–469, 1993. https://doi.org/10.1137/0914028
[32] Y. Saad. Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. https://doi.org/10.1137/1.9780898718003
[33] P.J. van der Houwen and B.P. Sommeijer. Analysis of parallel diagonally implicit iteration of Runge-Kutta methods. Applied Numerical Mathematics, 11(1-3):169–188, 1993. https://doi.org/10.1016/0168-9274(93)90047-U
[34] P.S. Vassilevski. Multilevel Block Factorization Preconditioners. Springer-Verlag, New York, 2008.
[35] R.Čiegis, V. Starikovičius and S. Margenov. On parallel numerical algorithms for fractional diffusion problems. In J. Carretero, J. Garsia Blas and S. Margenov(Eds.), Proceedings of the Third International Workshop on Sustainable Ultrascale Computing Systems (NESUS 2016). Universidad Carlos III de Madrid, 12 2016.
[36] R.Čiegis, V. Starikovičius, S. Margenov and R.Kriauzienė. Parallel solvers for fractional power diffusion problems. Concurrency and Computation: Practice and Experience, 29(24), 2017. https://doi.org/10.1002/cpe.4216
[37] J.-C. Xu. Two-grid discretization techniques for linear and nonlinear PDEs. SIAM Journal on Numerical Analysis., 33(5):1759–1777, 1996. https://doi.org/10.1137/S0036142992232949