×

Consistent treatment of incompletely converged iterative linear solvers in reverse-mode algorithmic differentiation. (English) Zbl 1469.65073

Summary: Algorithmic differentiation (AD) is a widely-used approach to compute derivatives of numerical models. Many numerical models include an iterative process to solve non-linear systems of equations. To improve efficiency and numerical stability, AD is typically not applied to the linear solvers. Instead, the differentiated linear solver call is replaced with hand-produced derivative code that exploits the linearity of the original call. In practice, the iterative linear solvers are often stopped prematurely to recompute the linearisation of the non-linear outer loop. We show that in the reverse-mode of AD, the derivatives obtained with partial convergence become inconsistent with the original and the tangent-linear models, resulting in inaccurate adjoints. We present a correction term that restores consistency between adjoint and tangent-linear gradients if linear systems are only partially converged. We prove the consistency of this correction term and show in numerical experiments that the accuracy of adjoint gradients of an incompressible flow solver applied to an industrial test case is restored when the correction term is used.

MSC:

65F10 Iterative numerical methods for linear systems
65D25 Numerical differentiation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bischof, C.; Khademi, P.; Mauer, A.; Carle, A., ADIFOR 2.0: automatic differentiation of Fortran 77 programs, IEEE Comput. Sci. Eng., 3, 3, 18-32 (1996) · doi:10.1109/99.537089
[2] Bischof, C.H., Bücker, H., Lang, B., Rasch, A., Vehreschild, A.: Combining source transformation and operator overloading techniques to compute derivatives for Matlab programs. In: Proceedings of the Second IEEE International Workshop on Source Code Analysis and Manipulation, Montreal, QC, Canada, pp. 65-72. IEEE (2002). 10.1109/SCAM.2002.1134106
[3] Capriotti, L., Giles, M.B.: Fast correlation Greeks by adjoint algorithmic differentiation. arXiv.org, Quantitative Finance Papers (2010). 10.2139/ssrn.1587822
[4] Christianson, B., Reverse accumulation and attractive fixed points, Optim. Methods Softw., 3, 4, 311-326 (1994) · doi:10.1080/10556789408805572
[5] Courty, F.; Dervieux, A.; Koobus, B.; Hascoët, L., Reverse automatic differentiation for optimum design: from adjoint state assembly to gradient computation, Optim. Methods Softw., 18, 5, 615-627 (2003) · Zbl 1142.90524 · doi:10.1080/10556780310001610501
[6] Davies, AJ; Christianson, DB; Dixon, LCW; Roy, R.; van der Zee, P., Reverse differentiation and the inverse diffusion problem, Adv. Eng. Softw., 28, 4, 217-221 (1997) · doi:10.1016/S0965-9978(97)00005-7
[7] Ferziger, J.; Perić, M., Computational Methods for Fluid Dynamics (2002), New York: Springer, New York · Zbl 0869.76003
[8] Giering, R.; Kaminski, T.; Slawig, T., Generating efficient derivative code with TAF: adjoint and tangent linear Euler flow around an airfoil, Fut. Gen. Comput. Syst., 21, 8, 1345-1355 (2005) · doi:10.1016/j.future.2004.11.003
[9] Giles, MB; Bischof, C.; Bücker, H.; Hovland, P.; Naumann, U.; Utke, J., Collected matrix derivative results for forward and reverse mode algorithmic differentiation, Advances in Automatic Differentiation. Lecture Notes in Computational Science and Engineering, 35-44 (2008), Berlin: Springer, Berlin · Zbl 1154.65308
[10] Giles, MB; Duta, MC; Müller, JD; Pierce, NA, Algorithm developments for discrete adjoint methods, AIAA J., 41, 2, 198-205 (2003) · doi:10.2514/2.1961
[11] Giles, MB; Pierce, NA, An introduction to the adjoint approach to design, Flow Turbul. Combust., 65, 3, 393-415 (2000) · Zbl 0996.76023 · doi:10.1023/A:1011430410075
[12] Giles, MB; Süli, E., Adjoint methods for PDEs: a posteriori error analysis and postprocessing by duality, Acta Numer., 11, 145-236 (2002) · Zbl 1105.65350 · doi:10.1017/S096249290200003X
[13] Griewank, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation (2008), Philadelphia: SIAM, Philadelphia · Zbl 1159.65026
[14] Griewank, A.; Juedes, D.; Utke, J., Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++, ACM Trans. Math. Softw., 22, 2, 131-167 (1996) · Zbl 0884.65015 · doi:10.1145/229473.229474
[15] Hascoët, L.; Pascual, V., The Tapenade automatic differentiation tool: principles, model, and specification, ACM Trans. Math. Softw. (2013) · Zbl 1295.65026 · doi:10.1145/2450153.2450158
[16] Heimbach, P.; Bugnion, V., Greenland ice-sheet volume sensitivity to basal, surface and initial conditions derived from an adjoint model, Ann. Glaciol., 50, 52, 67-80 (2009) · doi:10.3189/172756409789624256
[17] Jones, D.; Müller, JD; Christakopoulos, F., Preparation and assembly of discrete adjoint CFD codes, Comput. Fluids, 46, 1, 282-286 (2011) · Zbl 1433.76131 · doi:10.1016/j.compfluid.2011.01.042
[18] Lotz, J., Leppkes, K., Naumann, U.: DCO/C++ : Derivative Code by Overloading in C++, Introduction and Summary of Features. Tech. rep., Department of Computer Science, RWTH Aachen University, Aachen, Germany (2016). Report No.: AIB-2016-08
[19] Mavriplis, DJ, Discrete adjoint-based approach for optimization problems on three-dimensional unstructured meshes, AIAA J., 45, 4, 740 (2007) · doi:10.2514/1.22743
[20] Meyer, C.D.: Matrix Analysis and Applied Linear Algebra, chap. 5. SIAM, Philadelphia (2000) · Zbl 0962.15001
[21] Moré, JJ; Wild, SM, Do you trust derivatives or differences?, Comput. Phys., 273, 268-277 (2014) · Zbl 1352.65668 · doi:10.1016/j.jcp.2014.04.056
[22] Müller, J., Essentials of Computational Fluid Dynamics (2015), Boca Raton: CRC Press, Boca Raton
[23] Naumann, U., The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation (2012), Philadelphia: SIAM, Philadelphia · Zbl 1275.65015
[24] Nielsen, EJ; Diskin, B.; Yamaleev, NK, Discrete adjoint-based design optimization of unsteady turbulent flows on dynamic unstructured grids, AIAA J., 48, 6, 1195 (2010) · doi:10.2514/1.J050035
[25] Patankar, SV; Spalding, DB, A calculation procedure for heat, mass and momentum transfer in three-dimensional parabolic flows, Heat Mass Transf., 15, 10, 1787-1806 (1972) · Zbl 0246.76080 · doi:10.1016/B978-0-08-030937-8.50013-1
[26] Queen Mary University of London: AboutFlow, an EU-Funded Project: Adjoint-based Optimisation of Industrial and Unsteady Flows. https://aboutflow.sems.qmul.ac.uk/. Accessed 30 Oct 2019
[27] Rausch, RD; Batina, JT; Yang, HT, Three-dimensional time-marching aeroelastic analyses using an unstructured-grid Euler method, AIAA J., 31, 9, 1626-1633 (1993) · doi:10.2514/3.11824
[28] Saad, Y.: Sparskit: A Basic Tool Kit for Sparse Matrix Computations—Version 2 User Manual (1994)
[29] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelphia: SIAM, Philadelphia · Zbl 1002.65042
[30] Sagebaum, M., Albring, T., Gauger, N.R.: High-performance derivative computations using CoDiPack. CoRR abs/1709.07229 (2017). arXiv:1709.07229 · Zbl 1486.65029
[31] Taftaf, A.: Extensions of Algorithmic Differentiation by Source Transformation Inspired by Modern Scientific Computing. Ph.D. thesis, General Mathematics, Université Côte d’Azur, France (2017)
[32] Towara, M.; Naumann, U., Simple adjoint message passing, Optim. Methods Softw., 33, 4-6, 1232-1249 (2018) · Zbl 1453.65397 · doi:10.1080/10556788.2018.1435653
[33] Venditti, DA; Darmofal, DL, Adjoint error estimation and grid adaptation for functional outputs: application to quasi-one-dimensional flow, Comput. Phys., 164, 1, 204-227 (2000) · Zbl 0995.76057 · doi:10.1006/jcph.2000.6600
[34] Xu, S.; Jahn, W.; Müller, JD, CAD-based shape optimisation with CFD using a discrete adjoint, Numer. Methods Fluids, 74, 3, 153-68 (2013) · Zbl 1455.74075 · doi:10.1002/fld.3844
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.