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.
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.
