tr-announce

Download

tr-announce@lists.rwth-aachen.de

October 2011

1 participants
2 discussions

2011-10: Adjoint Subgradient Calculation for McCormick Relaxations
by Carsten Fuhs 12 Oct '11

12 Oct '11

The following technical report is available from http://aib.informatik.rwth-aachen.de: Adjoint Subgradient Calculation for McCormick Relaxations Markus Beckers, Viktor Mosenkis, Michael Maier, Uwe Naumann AIB 2011-10 In [Corbett 2010] the library modMC was presented which allows the propagation of McCormick relaxations and their corresponding subgradients based on the forward mode of Algorithmic Differentiation (AD). Subgradients are natural extensions of usual derivatives which allow the application of derivative based methods on possibly nondifferentiable convex and concave functions. These subgradients can be computed by AD, a method which allows the computation of derivatives with machine accuracy even for highly complex functions implemented by a computer program. In this article we present the advancement of modMC by reverse mode AD. Reverse mode AD is an adjoint method for the propagation of derivatives which is preferable when scalar functions are considered. We describe the theory behind the application of reverse mode in subgradient propagation as well as the improved library amodMC in detail. The calculated subgradients are used in an deterministic global optimization algorithm which is based on a branch-and-bound method. The improvements gained using Reverse instead of Forward mode AD are illustrated by several examples.

1 0

2011-09: Fifth SIAM Workshop on Combinatorial Scientific Computing
by Carsten Fuhs 12 Oct '11

12 Oct '11

The following technical report is available from http://aib.informatik.rwth-aachen.de: Fifth SIAM Workshop on Combinatorial Scientific Computing Markus Beckers, Johannes Lotz, Viktor Mosenkis, Uwe Naumann (Editors) AIB 2011-09 The human desire for meaningful numerical simulation of physical, chemical, and biological phenomena in science and engineering has been increasing with the growing performance of the continuously improving computer systems. As a result of this development, we are (and will always be) faced with a large (and growing) number of highly complex numerical simulation codes that run at the limit of the available high-performance computing resources. These codes often result from the discretization of systems of differential equations. The runtime correlates with the resolution that often needs to be very high in order to capture the real behavior of the underlying system. There is no doubt that the available hardware will always be used to the extreme. Improvements in the runtime of the simulations need to be sought through research in numerical algorithms and their efficient implementation on parallel architectures. Many of the resulting problems are combinatorial in nature. Most of those are known to be computationally hard in the sense that efficient (polynomial in the required time and memory space) algorithms for their exact solution are unlikely to exist. For example, we have to deal with partitioning, elimination ordering, coloring, and matching problems for graphs and hypergraphs in various contexts. A good approximation of the solution to these abstract problems may lead to a significant decrease in the runtime of numerical programs that implement solvers for partial differential equations, nonlinear optimization algorithms, or solvers for generalized Eigenvalue problems. Problem sizes are typically now in the millions of unknowns; and with emerging large-scale computing systems, this size is expected to increase by a factor of thousand over the next five years. Moreover, simulations are increasingly used in design optimization and parameter identification which is even more complex and requires the highest possible computational performance and fundamental enabling algorithmic technology. What binds together the community of combinatorial scientific computing is the focus on practical use of graph algorithms and combinatorial algorithms to address a variety of different problems that all arise in scientific computing. This shared common denominator allows us to interact productively and to advance the state of the art in several different problem areas. The Fifth SIAM Workshop on Combinatorial Scientific Computing represents another important milestone. Three CSC experts have been invited to present plenary talks on various important aspects of CSC: Thomas F. Coleman (University of Waterloo, Canada): Efficient Automatic Differentiation for Nonlinear Systems and Continuous Optimization (by using graphs) Burkhard Monien (Paderborn University, Germany): Recent Trends in Graph Partitioning for Scientific Computing Trond Steihaug (Bergen University, Norway): Sparse Matrix Structures and Higher Derivatives This collection of extended abstracts covers all accepted contributed oral and poster presentations. It is meant to give both participants of CSC11 and other interested readers an overview of recent results and ongoing research and development projects in the area of Combinatorial Scientific Computing.

1 0