No Access

TIME-PARALLEL COMPUTATION OF PSEUDO-ADJOINTS FOR A LEAPFROG SCHEME

CHRISTIAN H. BISCHOF

Institute for Scientific Computing, Aachen University, 52056 Aachen, Germany

Search for more papers by this author

H. MARTIN BÜCKER

Institute for Scientific Computing, Aachen University, 52056 Aachen, Germany

Search for more papers by this author

, and

PO-TING WU

SUN Microsystems, 901 San Antonio Road, Palo Alto, CA 94303, USA

Search for more papers by this author

https://doi.org/10.1142/S0129053304000219Cited by:1 (Source: Crossref)

Abstract

The leapfrog scheme is a commonly used second-order difference scheme for solving differential equations. If Z(t) denotes the state of a system at a particular time step t, the leapfrog scheme computes the state at the next time step as Z(t+1)=H(Z(t),Z(t-1),W), where H is the nonlinear time-stepping operator and W represents parameters that are not time-dependent. In this note, we show how the associativity of the chain rule of differential calculus can be used to compute a so-called adjoint, the derivative of a scalar-valued function applied to the final state Z(T) with respect to some chosen parameters, efficiently in a parallel fashion. To this end, we (1) employ the reverse mode of automatic differentiation at the outermost level, (2) use a sparsity-exploiting version of the forward mode of automatic differentiation to compute derivatives of H at every time step, and (3) exploit chain rule associativity to compute derivatives at individual time steps in parallel. We report on experimental results with a 2-D shallow water equations model problem on an IBM SP parallel computer and a network of Sun SPARCstations.

Keywords:

References

, Proceedings of the 5th AIAA/NASA/USAF/ISSMO Symposium on Multidisciplinary Analysis and Optimization ( American Association of Aeronautics and Aerospace Engineers , Panama City, Florida , 1994 ) . Google Scholar
B. Avericket al., SIAM J. Sci. Comput. 15(2), 285 (1994). Crossref, Google Scholar
J. Benary, Computational Differentiation: Techniques, Applications, and Tools, Parallelism in the reverse mode, eds. M. Berzet al. (SIAM, Philadelphia, 1996) pp. 137–148. Google Scholar
M. Berz et al. , Computational Differentiation: Techniques, Applications, and Tools ( SIAM , Philadelphia , 1996 ) . Google Scholar
C. Bischofet al., INFORMS J. Comput. 9(2), 185 (1997). Crossref, Google Scholar
C. H. Bischof, H. M. Bücker and P.-T. Wu, Computational Optimization and Applications 24(1), 117 (2003). Crossref, Google Scholar
C. Bischofet al., IEEE Comput. Sci. & Eng. 3(3), 18 (1996). Crossref, Google Scholar
C. H. Bischof and M. R. Haghighat, Computational Differentiation: Techniques, Applications, and Tools, On hierarchical differentiation, eds. M. Berzet al. (SIAM, Philadelphia, 1996) pp. 83–94. Google Scholar
C. Bischofet al., Opt. Methods Software 7(1), 1 (1996). Crossref, Google Scholar
C. Bischof, G. Pusch and R. Knoesel, Comput. in Phys. 10(6), 605 (1996). Crossref, Google Scholar
C. Bischof, L. Roh and A. Mauer, Software: Practice and Experience 27(12), 1427 (1997). Crossref, Google Scholar
G. Corliss et al. , Automatic Differentiation: From Simulation to Optimization ( Springer , New York , 2002 ) . Crossref, Google Scholar
R. Giering and T. Kaminski, ACM Trans. Math. Software 24(4), 437 (1988). Crossref, Google Scholar
A. Griewank, Opt. Methods Software 1(1), 35 (1992). Crossref, Google Scholar
A. Griewank , Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation ( SIAM , Philadelphia , 2000 ) . Google Scholar
A. Griewank and G. Corliss , Automatic Differentiation of Algorithms ( SIAM , Philadelphia , 1991 ) . Google Scholar
A. Griewank, D. Juedes and J. Utke, ACM Trans. Math. Software 22(2), 131 (1996). Crossref, Google Scholar
U. Geitner, J. Utke and A. Griewank, Computational Differentiation: Techniques, Applications, and Tools, Automatic computation of sparse Jacobians by applying the method of Newsam and Ramsdell, eds. M. Berzet al. (SIAM, Philadelphia, 1996) pp. 161–172. Google Scholar
A. Griewank and A. Walther, ACM Trans. Math. Software 26(1), 19 (2000). Crossref, Google Scholar
J. Grimm, L. Pottier and N. Rostaing-Schmidt, Computational Differentiation, Techniques, Applications, and Tools, Optimal time and minimum space time product for reversing a certain class of programs, eds. M. Berzet al. (SIAM, Philadelphia, 1996) pp. 95–106. Google Scholar
W. Gropp , E. Lusk and A. Skjellum , Using MPI — Portable Parallel Programming with the Message Passing Interface , 2nd edn. ( MIT Press , Cambridge , 1999 ) . Crossref, Google Scholar
V. Herrarte and E. Lusk, Studying parallel program behavior with Upshot, Technical Report ANL-91/15, Mathematics and Computer Science Division, Argonne National Laboratory, 1991 . Google Scholar
J. E. Horwedel, Automatic Differentiation of Algorithms: Theory, Implementation, and Application, GRESS: A preprocessor for sensitivity studies on Fortran programs, eds. A. Griewank and G. F. Corliss (SIAM, Philadelphia, 1991) pp. 243–250. Google Scholar
Ed. Oktay Baysal (ed.) , CFD for Design Optimization, FED Volume 232 , Proceedings of the 1995 ASME Int. Mech. Engr. Congress & Exposition . Google Scholar
Tellus 45a(5), (1993). Google Scholar
P. Roache , Fundamentals of Computational Fluid Dynamics ( Hermosa Publishers , Albuquerque , 1998 ) . Google Scholar
N. Rostaing, S. Dalmas and A. Galligo, Tellus 45a(5), 558 (1993). Google Scholar
J. C. Tannehill , D. A. Anderson and R. H. Pletcher , Computational Fluid Dynamics and Heat Transfer , 2nd edn. ( Taylor & Francis , Washington, D.C. , 1997 ) . Google Scholar
Z. Wang, Variational data assimilation with 2-D shallow water equations and 3-D FSU global spectral models, Technical Report FSU-SCRI-93T-149, Florida State University, Department of Mathematics, December 1993 . Google Scholar
Z. Wanget al., Comput. Opt. Appl. 4, 241 (1995). Crossref, Google Scholar