检索结果-内蒙古大学图书馆

Matrix-Free Jacobian Chaining

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Naumann, Uwe Software and Tools for Computational Engineering RWTH Aachen University Germany

The efficient computation of Jacobians represents a fundamental challenge in computational science and engineering. Large-scale modular numerical simulation programs can be regarded as sequences of evaluations of in our case differentiable subprograms with corresponding elemental Jacobians. The latter are typically not available. Tangent and adjoint versions of the individual subprograms are assumed to be given as results of algorithmic differentiation instead. The classical (Jacobian) Matrix Chain Product problem is reformulated in terms of matrix-free Jacobian-matrix (tangents) and matrix-Jacobian products (adjoints), subject to limited memory for storing information required by latter. All numerical results can be reproduced using an open-source reference implementation. Copyright © 2024, The Authors. All rights reserved.

关键词： Jacobian matrices

DIFFERENTIAL INVERSION OF THE IMPLICIT EULER METHOD: SYMBOLIC ANALYSIS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Naumann, Uwe Software and Tools for Computational Engineering RWTH Aachen University Aachen52056 Germany

The implicit Euler method integrates systems of ordinary differential equations dx dt = G(t, x(t)) with differentiable right-hand side G : R × Rn → Rn from an initial state x = x(0) ∈ Rn to a target time t ∈ R as x(t) = E(t, m, x) using an equidistant discretization of the time interval [0, t] yielding m > 0 time steps. We present a method for efficiently computing the product of its inverse Jacobian (E′)−1 ≡ （ dEdx）−1 ∈ Rn×n with a given vector v ∈ Rn. We show that the differential inverse (E′)−1 ·v can be evaluated for given v ∈ Rn with a computational cost of O(m·n2) as opposed to the standard O(m·n3) or, naively, even O(m · n4). The theoretical results are supported by actual run times. A reference implementation is *** Codes 65F05 © 2024, CC BY.

关键词： Ordinary differential equations

Season’s Greetings by AD

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Naumann, Uwe Software and Tools for Computational Engineering RWTH Aachen University Germany

MSC Codes 00-02We use Algorithmic Differentiation (AD) [1] to implement type-generic tangent and adjoint versions of (formula presented) in C++. We run an instantiation for char-arithmetic and we print the gradient at (101 77 114 114 32 121 109 88 115 97)T to std:: cout, yielding the output "Merry Xmas". Similar instantiations of type-generic second-order tangent and second-order adjoint versions of (formula presented) yield "Happy 2024" at (72 97 112 112 121 32 50 48 50 52)T . Prepend a sufficiently large number of zeros to the input vector to explore the varying run times of the different derivative codes. The entire source code can be found on https://***/un110076/SeasonsGreetings . © 2023, CC BY.

关键词：

Differentiable Programming: Efficient Smoothing of Control-Flow-Induced Discontinuities

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Christodoulou, Sebastian Naumann, Uwe Software Tools for Computational Engineering RWTH Aachen University Germany

We want to obtain derivatives in discontinuous program code, where default Algorithmic Differentiation may not perform well. Specifically, we consider discontinuities induced by control flow statements, where meaningful derivatives should ideally be capable of representing the resulting'jumps' in the trajectory. To achieve this, one can interpolate the trajectory at the control flow statements before taking the derivative. We formulate a method to efficiently interpolate between all boundaries induced by control flow in program code. Theoretically, code can be viewed as a series of piecewise continuous functions applied in succession. These functions are nested inside one another and result in a function composition with several cases. We interpret this function composition as a tree and devise a heuristic to identify paths that are relevant to the interpolation. This allows us to conceive a language that smoothly interpolates control-flow statements automatically and efficiently, making it fully differentiable. © 2023, CC BY-NC-ND.

关键词： Combinatorial mathematics

A MATRIX-FREE NEWTON METHOD

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Naumann, Uwe Software and Tools for Computational Engineering RWTH Aachen University Aachen Germany

A modification of Newton’s method for solving systems of n nonlinear equations is presented. The new matrix-free method relies on a given decomposition of the invertible Jacobian of the residual into invertible sparse local Jacobians according to the chain rule of differentiation. It is motivated in the context of local Jacobians with bandwidth 2m + 1 for m mn ) can be observed. Supporting run time measurements are presented for the tridiagonal case showing a reduction of the computational cost by O(n). Generalization yields the combinatorial Matrix-Free Newton Step problem. We prove NP-completeness and we present algorithmic components for building methods for the approximate solution. Inspired by adjoint Algorithmic Differentiation, the new method shares several challenges for the latter including the DAG Reversal problem. Further challenges are due to combinatorial problems in sparse linear algebra such as Bandwidth or Directed Elimination *** Codes 49M15, 47A05, 68N99 © 2023, CC BY-NC-ND.

关键词： Bandwidth

Elimination Techniques for Algorithmic Differentiation Revisited

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Naumann, Uwe Schneidereit, Erik Märtens, Simon Towara, Markus Software and Tools for Computational Engineering RWTH Aachen University Aachen52056 Germany

All known elimination techniques for (first-order) algorithmic differentiation (AD) rely on Jacobians to be given for a set of relevant elemental functions. Realistically, elemental tangents and adjoints are given instead. They can be obtained by applying software tools for AD to the parts of a given modular numerical simulation. The novel generalized face elimination rule proposed in this article facilitates the rigorous exploitation of associativity of the chain rule of differentiation at arbitrary levels of granularity ranging from elemental scalar (state of the art) to multivariate vector functions with given elemental tangents and adjoints. The implied combinatorial Generalized Face Elimination problem asks for a face elimination sequence of minimal computational cost. Simple branch and bound and greedy heuristic methods are employed as a baseline for further research into more powerful algorithms motivated by promising first test results. The latter can be reproduced with the help of an open-source reference *** Codes 68R05 © 2023, CC BY.

关键词： Heuristic methods

Numerical simulation of differential-algebraic equations with embedded global optimization criteria

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Deussen, Jens Hüser, Jonathan Naumann, Uwe Informatik 12 Software and Tools for Computational Engineering RWTH Aachen University Germany

We are considering differential-algebraic equations with embedded optimization criteria (DAEOs) in which the embedded optimization problem is solved by global optimization. This actually leads to differential inclusions for cases in which there are multiple global optimizer at the same time. Jump events from one global optimum to another result in nonsmooth DAEs and thus reduction of the convergence order of the numerical integrator to first-order. Implementation of event detection and location as introduced in this work preserves the higher-order convergence behavior of the integrator. This allows to compute discrete tangents and adjoint sensitivities for optimal control *** Codes 90C26, 49L20, 34A36 Copyright © 2023, The Authors. All rights reserved.

关键词： Global optimization

REDUCTION OF THE RANDOM ACCESS MEMORY SIZE IN ADJOINT ALGORITHMIC DIFFERENTIATION BY OVERLOADING

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Naumann, Uwe Informatik 12: Software and Tools for Computational Engineering RWTH Aachen University Germany

Adjoint algorithmic differentiation by operator and function overloading is based on the interpretation of directed acyclic graphs resulting from evaluations of numerical simulation programs. The size of the computer system memory required to store the graph grows proportional to the number of floating-point operations executed by the underlying program. It quickly exceeds the available memory resources. Naive adjoint algorithmic differentiation often becomes infeasible except for relatively simple numerical simulations. Access to the data associated with the graph can be classified as sequential and random. The latter refers to memory access patterns defined by the adjacency relationship between vertices within the graph. Sequentially accessed data can be decomposed into blocks. The blocks can be streamed across the system memory hierarchy thus extending the amount of available memory, for example, to hard discs. Asynchronous i/o can help to mitigate the increased cost due to accesses to slower memory. Much larger problem instances can thus be solved without resorting to technically challenging user intervention such as checkpointing. Randomly accessed data should not have to be decomposed. Its block-wise streaming is likely to yield a substantial overhead in computational cost due to data accesses across blocks. Consequently, the size of the randomly accessed memory required by an adjoint should be kept minimal in order to eliminate the need for decomposition. We propose a combination of dedicated memory for adjoint L-values with the exploitation of remainder bandwidth as a possible solution. Test results indicate significant savings in random access memory size while preserving overall computational efficiency. Copyright © 2022, The Authors. All rights reserved.

关键词： Bandwidth

Discrete Interval Adjoints in Unconstrained Global Optimization 6th

学校读者我要写书评

暂无评论

Discrete Interval Adjoints in Unconstrained Global Optimizat...

6th World Congress on Global Optimization, WCGO 2019

作者： Deussen, Jens Naumann, Uwe Software and Tools for Computational Engineering RWTH Aachen University Aachen Germany

ISBN: (纸本)9783030218027

We describe how to deploy interval derivatives up to second order in the context of unconstrained global optimization with a branch and bound method. For computing these derivatives we combine the Boost interval library and the algorithmic differentiation tool dco/c++. The differentiation tool also computes the required floating-point derivatives for a local search algorithm that is embedded in our branch and bound implementation. First results are promising in terms of utility of interval adjoints in global optimization. © 2020, Springer Nature Switzerland AG.

关键词： Global optimization