The technique of automatic differentiation provides directional derivatives and discrete adjoints with working accuracy. A complete complexity analysis of the basic modes of automatic differentiation is available. Therefore, the research activities are focused now on different aspects of the derivative calculation, as for example the efficient implementation by exploitation of structural information, studies of the theoretical properties of the provided derivatives in the context of optimization problems, and the development and analysis of new mathematical algorithms based on discrete adjoint information. According to this motivation, this habilitation presents an analysis of different checkpointing strategies to reduce the memory requirement of the discrete adjoint computation. Additionally, a new algorithm for computing sparse Hessian matrices is presented including a complexity analysis and a report on practical experiments. Hence, the first two contributions of this thesis are dedicated to an efficient computation of discrete adjoints. The analysis of discrete adjoints with respect to their theoretical properties is another important research topic. The third and fourth contribution of this thesis focus on the relation of discrete adjoint information and continuous adjoint information for optimal control problems. Here, differences resulting from different discretization strategies as well as convergence properties of the discrete adjoints are analyzed comprehensively. In the fifth contribution, checkpointing approaches that are successfully applied for the computation of discrete adjoints, are adapted such that they can be used also for the computation of continuous adjoints. Additionally, the fifth contributions presents a new proof of optimality for the binomial checkpointing that is based on new theoretical results. Discrete adjoint information can be applied for example for the approximation of dense Jacobian matrices. The development and analysis of new mathematical algorithms based on these approximate Jacobians is the topic of the sixth contribution. Is was possible to show global convergence to first-order critical points for a whole class of trust-region methods. Here, the usage of inexact Jacobian matrices allows a considerable reduction of the computational complexity.

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst. / For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

The technique of automatic differentiation provides directional derivatives and discrete adjoints with working accuracy. A complete complexity analysis of the basic modes of automatic differentiation is available. Therefore, the research activities are focused now on different aspects of the derivative calculation, as for example the efficient implementation by exploitation of structural information, studies of the theoretical properties of the provided derivatives in the context of optimization problems, and the development and analysis of new mathematical algorithms based on discrete adjoint information. According to this motivation, this habilitation presents an analysis of different checkpointing strategies to reduce the memory requirement of the discrete adjoint computation. Additionally, a new algorithm for computing sparse Hessian matrices is presented including a complexity analysis and a report on practical experiments. Hence, the first two contributions of this thesis are dedicated to an efficient computation of discrete adjoints. The analysis of discrete adjoints with respect to their theoretical properties is another important research topic. The third and fourth contribution of this thesis focus on the relation of discrete adjoint information and continuous adjoint information for optimal control problems. Here, differences resulting from different discretization strategies as well as convergence properties of the discrete adjoints are analyzed comprehensively. In the fifth contribution, checkpointing approaches that are successfully applied for the computation of discrete adjoints, are adapted such that they can be used also for the computation of continuous adjoints. Additionally, the fifth contributions presents a new proof of optimality for the binomial checkpointing that is based on new theoretical results. Discrete adjoint information can be applied for example for the approximation of dense Jacobian matrices. The development and analysis of new mathematical algorithms based on these approximate Jacobians is the topic of the sixth contribution. Is was possible to show global convergence to first-order critical points for a whole class of trust-region methods. Here, the usage of inexact Jacobian matrices allows a considerable reduction of the computational complexity.

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst. / For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. This thesis extends the theoretical results of the parallel reversal schedules. First a algorithm was constructed which carries out the ``forward'' calculation and distributes checkpoints in a way, such that the reversal calculation can be started at any time. This approach provides adaptive parallel reversal schedules for simulations where the number of time steps is not known a-priori. The number of checkpoints and processors used is optimal at any time. Further, an algorithm was described which makes is possible to restart the initial computer program during the program reversal. Again, this can be done without any additional computation at any time. Hence, optimal parallel reversal schedules for the bidirectional simulation are provided by this thesis. / Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Erstellen einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. In dieser Arbeit wird die Theorie der optimalen parallelen Umkehrschemata erweitert. Zum einen erfolgt die Konstruktion von adaptiven parallelen Umkehrschemata. Dafür wird ein Algorithmus beschrieben, der es durch die Nutzung von mehreren Prozessen ermöglicht, Checkpoints so zu verteilen, daß die Umkehrung des Programmes jederzeit ohne Zeitverlust erfolgen kann. Hierbei bleibt die Zahl der verwendeten Checkpoints und Prozesse innerhalb der bekannten Optimalitätsgrenzen. Zum anderen konnte für die adaptiven parallelen Umkehrschemata ein Algorithmus entwickelt werden, welcher ein Restart der eigentlichen Programmauswertung basierend auf der laufenden Programmumkehr erlaubt. Dieser Restart kann wieder jederzeit ohne Zeitverlust erfolgen und die entstehenden Checkpointverteilung erfüllen wieder sowohl Optimalitäts- als auch die Adaptivitätskriterien. Zusammenfassend wurden damit in dieser Arbeit Schemata konstruiert, die bidirektionale Simulationen ermöglichen.

For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. This thesis extends the theoretical results of the parallel reversal schedules. First a algorithm was constructed which carries out the ``forward'' calculation and distributes checkpoints in a way, such that the reversal calculation can be started at any time. This approach provides adaptive parallel reversal schedules for simulations where the number of time steps is not known a-priori. The number of checkpoints and processors used is optimal at any time. Further, an algorithm was described which makes is possible to restart the initial computer program during the program reversal. Again, this can be done without any additional computation at any time. Hence, optimal parallel reversal schedules for the bidirectional simulation are provided by this thesis. / Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Erstellen einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. In dieser Arbeit wird die Theorie der optimalen parallelen Umkehrschemata erweitert. Zum einen erfolgt die Konstruktion von adaptiven parallelen Umkehrschemata. Dafür wird ein Algorithmus beschrieben, der es durch die Nutzung von mehreren Prozessen ermöglicht, Checkpoints so zu verteilen, daß die Umkehrung des Programmes jederzeit ohne Zeitverlust erfolgen kann. Hierbei bleibt die Zahl der verwendeten Checkpoints und Prozesse innerhalb der bekannten Optimalitätsgrenzen. Zum anderen konnte für die adaptiven parallelen Umkehrschemata ein Algorithmus entwickelt werden, welcher ein Restart der eigentlichen Programmauswertung basierend auf der laufenden Programmumkehr erlaubt. Dieser Restart kann wieder jederzeit ohne Zeitverlust erfolgen und die entstehenden Checkpointverteilung erfüllen wieder sowohl Optimalitäts- als auch die Adaptivitätskriterien. Zusammenfassend wurden damit in dieser Arbeit Schemata konstruiert, die bidirektionale Simulationen ermöglichen.