TY - GEN A1 - Streubel, Tom A1 - Tischendorf, Caren A1 - Griewank, Andreas T1 - Piecewise Polynomial Taylor Expansions – The Generalization of Faà di Bruno’s Formula N2 - We present an extension of Taylor’s theorem towards nonsmooth evalua- tion procedures incorporating absolute value operaions. Evaluations procedures are computer programs of mathematical functions in closed form expression and al- low a different treatment of smooth operations and calls to the absolute value value function. The well known classical Theorem of Taylor defines polynomial approx- imation of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential or differential algebraic equations, for the construction of solvers for the continuous nonlinear op- timization of finite dimensional objective functions and for root solving of nonlinear systems of equations. The herein provided proof is construtive and allow efficiently designed algorithms for the execution and computation of generalized piecewise polynomial expansions. As a demonstration we will derive a k-step method on the basis of polynomial interpolation and the proposed generalized expansions. T3 - ZIB-Report - 18-24 KW - generalized Taylor expansion KW - implicit generation of splines KW - nonsmooth integration of differential algebraic equations (DAE and ODE) KW - multistep methods KW - generalized hermite interpolation KW - algorithmic piecewise differentiation (AD and APD) KW - evaluation procedures KW - treating absolute values (abs, max and min) Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68859 SN - 1438-0064 ER - TY - GEN A1 - Radons, Manuel A1 - Lehmann, Lutz A1 - Streubel, Tom A1 - Griewank, Andreas T1 - An Open Newton Method for Piecewise Smooth Systems N2 - Recent research has shown that piecewise smooth (PS) functions can be approximated by piecewise linear functions with second order error in the distance to a given reference point. A semismooth Newton type algorithm based on successive application of these piecewise linearizations was subsequently developed for the solution of PS equation systems. For local bijectivity of the linearization at a root, a radius of quadratic convergence was explicitly calculated in terms of local Lipschitz constants of the underlying PS function. In the present work we relax the criterium of local bijectivity of the linearization to local openness. For this purpose a weak implicit function theorem is proved via local mapping degree theory. It is shown that there exist PS functions f:IR^2 --> IR^2 satisfying the weaker criterium where every neighborhood of the root of f contains a point x such that all elements of the Clarke Jacobian at x are singular. In such neighborhoods the steps of classical semismooth Newton are not defined, which establishes the new method as an independent algorithm. To further clarify the relation between a PS function and its piecewise linearization, several statements about structure correspondences between the two are proved. Moreover, the influence of the specific representation of the local piecewise linear models on the robustness of our method is studied. An example application from cardiovascular mathematics is given. T3 - ZIB-Report - 18-43 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70418 SN - 1438-0064 ER - TY - GEN A1 - Hasenfelder, Richard A1 - Lehmann, Lutz A1 - Radons, Manuel A1 - Streubel, Tom A1 - Strohm, Christian A1 - Griewank, Andreas T1 - Computational aspects of the Generalized Trapezoidal Rule N2 - In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side F:IR^n -> IR^n. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a non-differentiability of F. In such a situation the investigated generalized trapezoidal rule achieves a higher convergence order than the classical method. While the asymptotic behavior of the generalized method was investigated in a previous work, in the present article we develop the algorithmic structure for efficient implementation strategies and estimate the actual computational cost of the latter. Moreover, energy preservation of the generalized trapezoidal rule is proved for Hamiltonian systems with piecewise linear right hand side. T3 - ZIB-Report - 18-23 KW - Algorithmic Differentiation KW - Automatic Differentiation KW - Lipschitz Continuity KW - Piecewise Linearization KW - Nonsmooth KW - Trapezoidal Rule KW - Implementation KW - Computational Cost Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68615 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions N2 - Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains. T3 - ZIB-Report - 20-14 KW - Nonsmooth Taylor polynomial/series KW - forward mode propagation KW - abs-normal form KW - abs-linear form KW - absolute convergence KW - Moore recurrences KW - quadratic complexity Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78448 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Hasenfelder, Richard A1 - Radons, Manuel T1 - Piecewise linear secant approximation via Algorithmic Piecewise Differentiation N2 - It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x − x̌|| ||x − x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton’s method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. T3 - ZIB-Report - 16-54 KW - Automatic differentiation KW - Computational graph KW - Lipschitz continuity KW - Generalized Hermite interpolation KW - ADOL-C Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61642 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Hasenfelder, Richard A1 - Radons, Manuel A1 - Lehmann, Lutz A1 - Streubel, Tom T1 - Integrating Lipschitzian Dynamical Systems using Piecewise Algorithmic Differentiation N2 - In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side \(F:R^n \to R^n\) based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of \(F\). The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third order interpolation polynomial for the numerical trajectory. In the smooth case the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented. T3 - ZIB-Report - 17-44 KW - Automatic Differentiation KW - Lipschitz Continuity KW - Piecewise Linearization KW - Nonsmooth KW - Trapezoidal Rule KW - Energy Preservation KW - Dense Output Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64639 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas T1 - Sequential Evaluation of Adjoints and Higher Derivative Vectors by Overloading and Reverse Accumulation. N2 - Most nonlinear computations require the evaluation of first and higher derivatives of vector functions defined by computer programs. It is shown here how vectors of such partial derivatives can be obtained automatically and efficiently if the computer language allows overloading (as is or will be the case for C++, PASCAL-XSC, FORTRAN90, and other modern languages). Here, overloading facilitates the extension of arithmetic operations and univariate functions from real or complex arguments to truncated Taylor-series (or other user- defined types), and it generates instructions for the subsequent evaluation of adjoints. Similar effects can be achieved by precompilation of FORTRAN77 programs. The proposed differentiation algorithm yields gradients and higher derivatives at a small multiple of the run-time and RAM requirement of the original function evaluation program. {\bf Keywords:} Automatic Differentiation, Chain Rule, Overloading, Taylor Coefficients, Gradients, Hessians, Reverse Accumulation, Adjoint Equations. {\bf Abbreviated title:} Automatic Differentiation by Overloading. T3 - ZIB-Report - SC-91-03 KW - Automatic Differentiation KW - Chain Rule KW - Overloading KW - Taylor Coefficients KW - Gradients KW - Hessians KW - Reverse Accumulation KW - Adjoint Equations Y1 - 1991 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-539 ER -