A non-intrusive parallel-in-time adjoint solver with the XBraid library | Computing and Visualization in Science Skip to main content
Springer Nature Link
Log in

A non-intrusive parallel-in-time adjoint solver with the XBraid library

  • Original Article
  • Published:
Computing and Visualization in Science

Abstract

In this paper, an adjoint solver for the multigrid-in-time software library XBraid is presented. XBraid provides a non-intrusive approach for simulating unsteady dynamics on multiple processors while parallelizing not only in space but also in the time domain (XBraid: Parallel multigrid in time, http://llnl.gov/casc/xbraid). It applies an iterative multigrid reduction in time algorithm to existing spatially parallel classical time propagators and computes the unsteady solution parallel in time. Techniques from Automatic Differentiation are used to develop a consistent discrete adjoint solver which provides sensitivity information of output quantities with respect to design parameter changes. The adjoint code runs backwards through the primal XBraid actions and accumulates gradient information parallel in time. It is highly non-intrusive as existing adjoint time propagators can easily be integrated through the adjoint interface. The adjoint code is validated on advection-dominated flow with periodic upstream boundary condition. It provides similar strong scaling results as the primal XBraid solver and offers great potential for speeding up the overall computational costs for sensitivity analysis using multiple processors.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. In this work, the application of \(\Phi ^i_{\rho }\) represents the approximate inversion of an operator (implicit scheme), but in principle, explicit schemes may be considered as well.

References

  1. Albring, T., Dick, T., Gauger, N.R.: Assessment of the recursive projection method for the stabilization of discrete adjoint solvers. In: 18th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, AIAA Aviation (2017)

  2. Barker, A.T., Stoll, M.: Domain decomposition in time for PDE-constrained optimization. Comput. Phys. Commun. 197, 136–143 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  3. Beyer, H.G., Sendhoff, B.: Robust optimization—a comprehensive survey. Comput. Methods Appl. Mech. Eng. 196(33), 3190–3218 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  4. Blazek, J.: Computational Fluid Dynamics: Principles and Applications, 2nd edn. Elsevier Ltd., New York (2005)

    MATH  Google Scholar 

  5. Bosse, T., Gauger, N.R., Griewank, A., Günther, S., Schulz, V.: One-shot approaches to design optimzation. In: Leugering, G., Benner, P., Engell, S., Griewank, A., Harbrecht, H., Hinze, M., Rannacher, R., Ulbrich, S. (eds.) Trends in PDE Constrained Optimization, pp. 43–66. Springer, Berlin (2014)

    Google Scholar 

  6. Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comput. 31(138), 333–390 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  7. CoDiPack—Code Differentiation Package (version 1.0). http://www.scicomp.uni-kl.de/software/codi/ (2017). Accessed 1 May 2017

  8. Du, X., Sarkis, M., Schaerer, C., Szyld, D.B.: Inexact and truncated parareal-in-time krylov subspace methods for parabolic optimal control problems. ETNA 40, 36–57 (2013)

    MathSciNet  MATH  Google Scholar 

  9. Economon, T., Palacios, F., Alonso, J.: Unsteady aerodynamic design on unstructured meshes with sliding interfaces. In: 51st AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition, p. 632 (2013)

  10. Emmett, M., Minion, M.: Toward an efficient parallel in time method for partial differential equations. Commun. Appl. Math. Comput. Sci. 7(1), 105–132 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Falgout, R., Friedhoff, S., Kolev, T.V., MacLachlan, S., Schroder, J., Vandewalle, S.: Multigrid methods with space-time concurrency. SIAM J. Sci. Comput. 18(4–5), 123–143 (2015)

    MathSciNet  MATH  Google Scholar 

  12. Falgout, R.D., Friedhoff, S., Kolev, T.V., MacLachlan, S.P., Schroder, J.B.: Parallel time integration with multigrid. SIAM J. Sci. Comput. 36(6), C635–C661 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  13. Falgout, R.D., Katz, A., Kolev, T.V., Schroder, J.B., Wissink, A., Yang, U.M.: Parallel time integration with multigrid reduction for a compressible fluid dynamics application. Tech. Rep. LLNL-JRNL-663416, Lawrence Livermore National Laboratory (2015)

  14. Falgout, R.D., Manteuffel, T.A., O’Neill, B., Schroder, J.B.: Multigrid reduction in time for nonlinear parabolic problems: a case study. SIAM J. Sci. Comput. 39(5), S298–S322 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  15. Farhat, C., Chandesris, M.: Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications. Int. J. Numer. Meth. Eng. 58, 1397–1434 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  16. Ferziger, J., Peric, M.: Computational Methods for Fluid Dynamics, 3rd edn. Springer, Berlin (2002)

    Book  MATH  Google Scholar 

  17. Fischer, P., Hecht, F., Maday, Y.: A parareal in time semi-implicit approximation of the Navier–Stokes equations. In: Proceedings of the Fifteenth International Conference on Domain Decomposition Methods, pp. 433–440. Springer (2005)

  18. Gander, M.J.: 50 years of time parallel time integration. In: Carraro, T., Geiger, M., Krkel, S., Rannacher, R. (eds.) Multiple Shooting and Time Domain Decomposition, pp. 69–114. Springer, Berlin (2015)

    Chapter  Google Scholar 

  19. Gander, M.J., Kwok, F.: Schwarz methods for the time-parallel solution of parabolic control problems. In: Domain Decomposition Methods in Computational Science and Engineering XXII, Lecture Notes in Computational Science and Engineering, vol. 104, pp. 207–216. Springer (2016)

  20. Gander, M.J., Vandewalle, S.: Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput. 29(2), 556–578 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  21. Gauger, N., Griewank, A., Hamdi, A., Kratzenstein, C., Özkaya, E., Slawig, T.: Automated extension of fixed point PDE solvers for optimal design with bounded retardation. In: Leugering, G., Engell, S., Griewank, A., Hinze, M., Rannacher, R., Schulz, V., Ulbrich, M., Ulbrich, S. (eds.) Constrained Optimization and Optimal Control for Partial Differential Equations, pp. 99–122. Springer, Basel (2012)

    Chapter  Google Scholar 

  22. Giles, M., Pierce, N., Giles, M., Pierce, N.: Adjoint equations in CFD: duality, boundary conditions and solution behaviour. In: 13th Computational Fluid Dynamics Conference, p. 1850 (1997)

  23. Giles, M.B., Pierce, N.A.: An introduction to the adjoint approach to design. Flow Turbul. Combust. 65(3), 393–415 (2000)

    Article  MATH  Google Scholar 

  24. Giles, M.B., Süli, E.: Adjoint methods for PDEs: a posteriori error analysis and postprocessing by duality. Acta Numer. 11, 145–236 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Götschel, S., Minion, M.: Parallel-in-time for parabolic optimal control problems using pfasst. Tech. Rep. 17-51, ZIB (2017)

  26. Griewank, A.: Projected hessians for preconditioning in one-step one-shot design optimization. In: Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 151–171. Springer, Berlin (2006)

    Chapter  Google Scholar 

  27. Griewank, A., Faure, C.: Reduced functions, gradients and hessians from fixed-point iterations for state equations. Numer. Algorithms 30, 113–139 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  28. Griewank, A., Ponomarenko, A.: Time-lag in derivative convergence for fixed point iterations. In: Proceedings of CARI’04, 7th African Conference on Research in Computer Science, pp. 295–304 (2004)

  29. Griewank, A., Walther, A.: Evaluating derivatives, 2nd edn. Society for Industrial and Applied Mathematics (2008)

  30. Günther, S., Gauger, N.R., Wang, Q.: Simultaneous single-step one-shot optimization with unsteady pdes. J. Comput. Appl. Math. 294, 12–22 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  31. Heinkenschloss, M.: A time-domain decomposition iterative method for the solution of distributed linear quadratic optimal control problems. J. Comput. Appl. Math. 173(1), 169–198 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  32. Jameson, A.: Aerodynamic design via control theory. J. Sci. Comput. 3(3), 233–260 (1988)

    Article  MATH  Google Scholar 

  33. Jameson, A.: Time dependent calculations using multigrid, with applications to unsteady flows past airfoils and wings. In: Proceedings of 10th Computational Fluid Dynamics Conference, Honolulu, USA, June 24-26, AIAA-Paper 91-1596 (1991)

  34. Josuttis, N.M.: The C++ Standard Library: A Tutorial and Reference. Addison-Wesley, Boston (2012)

    Google Scholar 

  35. Kanamaru, T.: Van der pol oscillator. Scholarpedia 2(1), 2202 (2007)

    Article  Google Scholar 

  36. Krause, R., Ruprecht, D.: Hybrid space-time parallel solution of Burgers equation. In: Sassi, T., Halpern, L., Pichot, G., Widlund, O.B. (eds.) Domain Decomposition Methods in Science and Engineering XXI, pp. 647–655. Springer, Berlin (2014)

    Google Scholar 

  37. Kwok, F.: On the time-domain decomposition of parabolic optimal control problems. In: Lee, C.-O., Cai, X.-C., Hansford, V., Kim, H.H., Klawonn, A., Park, E.-J., Widlund, O.B. (eds.) Domain Decomposition Methods in Science and Engineering XXIII, pp. 55–67. Springer, Berlin (2017)

    Chapter  Google Scholar 

  38. Korrektur der Referenzangabe: Lions, J.L.: Optimal control of systems governed by partial differential equations (Grundlehren der Mathematischen Wissenschaften), vol. 170. Springer, Berlin (1971)

  39. Lions, J.L., Maday, Y., Turinici, G.: Résolution d’EDP par un schéma en temps pararéel. C. R. Acad. Sci. Paris Sér. I Math. 332, 661–668 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  40. Mathew, T.P., Sarkis, M., Schaerer, C.E.: Analysis of block parareal preconditioners for parabolic optimal control problems. SIAM J. Sci. Comput. 32(3), 1180–1200 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  41. Mavriplis, D.: Solution of the unsteady discrete adjoint for three-dimensional problems on dynamically deforming unstructured meshes. In: 46th AIAA Aerospace Sciences Meeting and Exhibit, p. 727 (2008)

  42. Mohammadi, B., Pironneau, O.: Applied Shape Optimization for Fluids. Oxford University Press, Oxford (2010)

    MATH  Google Scholar 

  43. Nadarajah, S.K., Jameson, A.: Optimum shape design for unsteady flows with time-accurate continuous and discrete adjoint method. AIAA J. 45(7), 1478–1491 (2007)

    Article  Google Scholar 

  44. Naumann, U.: The art of differentiating computer programs: an introduction to algorithmic differentiation. Environments, and Tools. Society for Industrial and Applied Mathematics, Software (2012)

  45. Navon, I.: Practical and theoretical aspects of adjoint parameter estimation and identifiability in meteorology and oceanography. Dyn. Atmos. Oceans 27(1), 55–79 (1998)

    Article  Google Scholar 

  46. Nielsen, E.J., Diskin, B., Yamaleev, N.K.: Discrete adjoint-based design optimization of unsteady turbulent flows on dynamic unstructured grids. AIAA J. 48(6), 1195–1206 (2010)

    Article  Google Scholar 

  47. Nievergelt, J.: Parallel methods for integrating ordinary differential equations. Commun. ACM 7, 731–733 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  48. Pierce, N.A., Giles, M.B.: Adjoint recovery of superconvergent functionals from PDE approximations. SIAM Rev. 42(2), 247–264 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  49. Pironneau, O.: On optimum design in fluid mechanics. J. Fluid Mech. 64(1), 97–110 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  50. Ries, M., Trottenberg, U.: MGR-ein blitzschneller elliptischer löser. Tech. Rep. Preprint 277 SFB 72, Universität Bonn (1979)

  51. Ries, M., Trottenberg, U., Winter, G.: A note on MGR methods. Linear Algebra Appl. 49, 1–26 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  52. Rumpfkeil, M., Zingg, D.: A general framework for the optimal control of unsteady flows with applications. In: 45th AIAA Aerospace Sciences Meeting and Exhibit, p. 1128 (2007)

  53. Ruprecht, D., Krause, R.: Explicit parallel-in-time integration of a linear acoustic-advection system. Comput. Fluids 59, 72–83 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  54. Shroff, G.M., Keller, H.B.: Stabilization of unstable procedures: the recursive projection method. SIAM J. Numer. Anal. 30(4), 1099–1120 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  55. Steiner, J., Ruprecht, D., Speck, R., Krause, R.: Convergence of parareal for the Navier-Stokes equations depending on the Reynolds number. In: Abdulle, A., Deparis, S., Kressner, D., Nobile, F., Picasso, M. (eds.) Numerical Mathematics and Advanced Applications—ENUMATH 2013: Proceedings of ENUMATH 2013, the 10th European Conference on Numerical Mathematics and Advanced Applications, Lausanne, August 2013, pp. 195–202. Springer International Publishing, Cham (2015)

  56. Trottenberg, U., Oosterlee, C., Schüller, A.: Multigrid. Academic Press, San Diego (2001)

    MATH  Google Scholar 

  57. Tucker, P.: Unsteady Computational Fluid Dynamics in Aeronautics. Springer, Berlin (2014)

    Book  Google Scholar 

  58. Dobrev, V.A., Kolev, T., Petersson, N.A., Schroder, J.B.: Two-level convergence theory for multigrid reduction in time (MGRIT). SIAM SIAM J. Sci. Comput. 39(5), S501–S527 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  59. Venditti, D.A., Darmofal, D.L.: Grid adaptation for functional outputs: application to two-dimensional inviscid flows. J. Comput. Phys. 176(1), 40–69 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  60. XBraid: Parallel multigrid in time. http://llnl.gov/casc/xbraid. Accessed 1 Feb 2017

Download references

Acknowledgements

The authors thanks Max Sagebaum (SciComp, TU Kaiserslautern) and Johannes Lotz (STCE, RWTH Aachen University) who provided insight and expertise on the implementation of AD.

Author information

Authors and Affiliations

  1. Chair for Scientific Computing, TU Kaiserslautern, Paul-Ehrlich-Straße 34 – 36, 67663, Kaiserslautern, Germany

    Stefanie Günther & Nicolas R. Gauger

  2. Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, P.O. Box 808, L-561, Livermore, CA, 94551, USA

    Jacob B. Schroder

Authors
  1. Stefanie Günther
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicolas R. Gauger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jacob B. Schroder
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stefanie Günther.

Additional information

This work performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52–07NA27344, LLNL-JRNL-730159.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Günther, S., Gauger, N.R. & Schroder, J.B. A non-intrusive parallel-in-time adjoint solver with the XBraid library. Comput. Visual Sci. 19, 85–95 (2018). https://doi.org/10.1007/s00791-018-0300-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00791-018-0300-7

Keywords

Search

Navigation