March 2008 - tr-announce - lists.rwth-aachen.de

2007-19: Adjoints for Time-Dependent Optimal Control
by Peter Schneider-Kamp 07 Mar '08

07 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Adjoints for Time-Dependent Optimal Control Jan Riehme, Andrea Walther, Jörg Stiller, Uwe Naumann AIB 2007-19 The use of discrete adjoints in the context of a hard time-dependent optimal control problem is considered. Gradients required for the steepest descent method are computed by code that is generated automatically by the differentiation-enabled NAGWare Fortran compiler. Single time steps are taped using an overloading approach. The entire evolution is reversed based on an efficient checkpointing schedule that is computed by revolve. The feasibility of nonlinear optimization based on discrete adjoints is supported by our numerical results.

1 0

2007-18: Call Tree Reversal is NP-Complete
by Peter Schneider-Kamp 07 Mar '08

07 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Call Tree Reversal is NP-Complete Uwe Naumann AIB 2007-18 The data-flow of a numerical program is reversed in its adjoint. We discuss the combinatorial optimization problem that aims to find optimal checkpointing schemes at the level of call trees. For a given amount of persistent memory the objective is to store selected arguments and/or results of subroutine calls such that the overall computational effort (the total number of floating-point operations performed by potentially repeated forward evaluations of the program) of the data-flow reversal is minimized. Call Tree Reversal is shown to be NP-complete.

1 0

2008-04: Sensitivity Analysis in Sisyphe with the AD-Enabled NAGWare Fortran Compiler
by Peter Schneider-Kamp 05 Mar '08

05 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Sensitivity Analysis in Sisyphe with the AD-Enabled NAGWare Fortran Compiler Uwe Naumann, Jan Riehme AIB 2008-04 We present the final report for a collaborative research project with the Federal Waterways Engineering and Research Institute, Karsruhle. A numerical model of a dune implemented in Sisyphe is considered. Sensitivity analysis is performed using a tangent-linear model that is generated automatically by the differentiation-enabled NAGWare Fortran compiler.

1 0

2008-05: An Automata Theoretic Approach to the Theory of Rational Tree Relations
by Peter Schneider-Kamp 04 Mar '08

04 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: An Automata Theoretic Approach to the Theory of Rational Tree Relations Frank G. Radmacher AIB 2008-05 We investigate rational relations over trees. Our starting point is the definition of rational tree relations via rational expressions by Raoult (Bull.Belg.Math.Soc. 1997). We develop a new class of automata, called asynchronous tree automata, which recognize exactly these relations. The automata theoretic approach is convenient for the solution of algorithmic problems (like the emptiness problem). The second contribution of this paper is a new subclass of the rational tree relations, called separate-rational tree relations, defined via a natural restriction on asynchronous tree automata. These relations are closed under composition, preserve regular tree languages, and generate precisely the regular sets in the unary case (all these properties fail for the general model), and they are still more powerful than, for instance, the automatic tree relations.

1 0

2008-03: Maximal Termination
by Peter Schneider-Kamp 04 Mar '08

04 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Maximal Termination Carsten Fuhs, Jürgen Giesl, Aart Middeldorp, Peter Schneider-Kamp, René Thiemann, Harald Zankl AIB 2008-03 We present a new approach for termination proofs that uses polynomial interpretations (with possibly negative coefficients) together with the "maximum" function. To obtain a powerful automatic method, we solve two main challenges: (1) We show how to adapt the latest developments in the dependency pair framework to our setting. (2) We show how to automate the search for such interpretations by integrating "max" into recent SAT-based methods for polynomial interpretations. Experimental results support our approach.

1 0