Refine
Year of publication
Language
- English (1103) (remove)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
This paper discusses the stability of quasi-static paths for a continuous elastic-plastic system with hardening in a one-dimensional (bar) domain. Mathematical formulations, as well as existence and uniqueness results for dynamic and quasi-static problems involving elastic-plastic systems with linear kinematic hardening are recalled in the paper. The concept of stability of quasi-static paths used here is essentially a continuity property of the system dynamic solutions relatively to the quasi-static ones, when (as in Lyapunov stability) the size of initial perturbations is decreased and the rate of application of the forces (which plays the role of the small parameter in singular perturbation problems) is also decreased to zero. The stability of the quasi-static paths of these elastic-plastic systems is the main result proved in the paper.
Mathematical results on existence for viscoelastodynamic problems with unilateral constraints
(2011)
We study a damped wave equation and the evolution of a Kelvin-Voigt material, both problems have unilateral boundary conditions. Under appropriate regularity assumptions on the initial data, both problems possess a weak solution which is obtained as the limit of a sequence of penalized problems; the functional properties of all the traces are precisely identified through Fourier analysis, and this enables us to infer the existence of a strong solution.
Energetic solutions to rate-independent processes are usually constructed via time-incremental minimization problems. In this work we show that all energetic solutions can be approximated by incremental problems if we allow approximate minimizers, where the error in minimization has to be of the order of the time step. Moreover, we study sequences of problems where the energy functionals have a Gamma limit.
A model for the evolution of damage that allows for complete disintegration is addressed. Small strains and a linear response function are assumed. The ``flow rule'' for the damage parameter is rate-independent. The stored energy involves the gradient of the damage variable, which determines an internal length-scale. Quasi-static fully rate-independent evolution is considered as well as rate-dependent evolution including viscous/inertial effects. Illustrative 2-dimensional computer simulations are presented, too.
Quasistatic small-strain plasticity in the limit of small hardening and its numerical approximation
(2011)
The quasistatic rate-independent evolution of the Prager-Ziegler-type model of linearized plasticity with hardening is shown to converge to the rate-independent evolution of the Prandtl-Reuss elastic/perfectly plastic model. Based on the concept of energetic solutions we study the convergence of the solutions in the limit for hardening coefficients converging to 0 by using the abstract method of Gamma-convergence for rate-independent systems. An unconditionally convergent numerical scheme is devised and 2D and 3D numerical experiments are presented. A two-sided energy inequality is a posteriori verified to document experimental convergence rates.
Deflated and augmented Krylov subspace methods: Basic Facts and a Breakdown-free deflated MINRES
(2011)
In this paper we consider deflation and augmentation techniques for accelerating
the convergence of Krylov subspace methods for the solution of nonsingular linear
algebraic systems. The two techniques are conceptually different from
preconditioning. Deflation "removes" certain parts from the operator, while
augmentation adds a subspace to the Krylov subspace. Both approaches have been
used in a variety of methods and settings. For Krylov subspace methods that
satisfy a (Petrov-) Galerkin condition we show that augmentation can in general
be achieved implicitly by projecting the residuals appropriately and correcting
the approximate solutions in a final step. In this context, we analyze known
methods to deflate CG, GMRes and MinRes. Our analysis reveals that the recently
proposed RMinRes method can break down. We show how such breakdowns can be
avoided by choosing a special initial guess, and we derive a breakdown-free
deflated MinRes method. In numerical experiments we study the properties of
different variants of MinRes analyzed in this paper.
We introduce a~numerical method for the numerical solution of the Lur'e matrix equations that arise, for instance, in linear-quadratic infinite time horizon optimal control. The method is based on the characterization of the solutions in terms of deflating subspaces of a suitable even matrix pencil. Via a Cayley transformation, the problem is transformed to the discrete-time case. This leaves us with a symplectic problem with several Jordan blocks of eigenvalue 1 and even size, which arise from the remaining eigenvalues at infinity of the original problem. For the solution of this modified problem, we use the {\em structure-preserving doubling algorithm} (SDA), an iterative scheme for the solution of dense continuous- and discrete-time algebraic Riccati equations. Unlike other iterative schemes, this algorithm converges also when the pencil has eigenvalues on the unit circle, as is the case in our problem. Implementation issues such as the choice of the parameter $\gamma$ in the Cayley transform are discussed. The numerical examples presented confirm the effectiveness of this method.
This paper presents concepts and implementation of the finite element toolbox Kaskade 7, a flexible C++ code for solving elliptic and parabolic PDE systems. Issues such as problem formulation, assembly and adaptivity are discussed at the example of optimal control problems. Trajectory compression for parabolic optimization problems is considered as a case study.
We propose a generalization of the Structured Doubling Algorithm (SDA) to compute invariant subspaces
of structured matrix pencils
that arise in the context of solving linear quadratic optimal control problems.
The new algorithm is
designed to attain better accuracy when the classical Riccati equation approach for the solution of the optimal control problem is not well suited because
the stable and unstable invariant subspaces are not well separated (due to eigenvalues near or on the imaginary
axis) or in the case when the Riccati solution does not exist at all. We analyze the convergence
of the method and compare the new method with the classical SDA algorithm as well as some recent structured QR-methods.
Recently, the format of TT tensors
\cite{hackbuschHT,osele1,tyrtosele2,tyrtosele3} has turned out to be
a promising new format for the approximation of solutions of high
dimensional problems. In this paper, we prove some new results for
the TT representation of a tensor $U \in \R^{n_1\times \ldots\times
n_d}$ and for the manifold of tensors of TT-rank $\underline{r}$.\As a first result, we prove that the TT (or compression) ranks $r_i$
of a tensor $U$ are unique and equal to the respective separation
ranks of $U$ if the components of the TT decomposition are required to
fulfil a certain maximal rank condition. We then show that the set
$\mathcal{T}$ of TT tensors of fixed rank $\underline{r}$ forms an embedded
manifold in $\R^{n^d}$, therefore preserving the essential theoretical
properties of the Tucker format, but often showing an improved scaling
behaviour. Extending a similar approach for matrices \cite{conte_lub},
we introduce certain gauge conditions to obtain a unique
representation of the tangent space $\cT_U\mathcal{T}$ of $\mathcal{T}$
and deduce a
local parametrization of the TT manifold. The parametrisation of
$\cT_{U}\mathcal{T}$ is often crucial for an algorithmic treatment of
high-dimensional time-dependent PDEs and minimisation problems
\cite{lubuch_blau}. We conclude with remarks on those applications and
present some numerical examples.
We investigate the regularity of the weak solution to elliptic transmission problems that involve two layered anisotropic materials separated by a boundary intersecting interface. Under a compatibility condition for the angle of contact of the two surfaces and the boundary data, we prove the existence of square-integrable second derivatives, and the global Lipschitz continuity of the solution. We show that the second weak derivatives remain integrable to a certain power less than two if the compatibility condition is violated.
While it is well-known that the standard integral operator K of (stationary) diffuse-gray radiation, as it occurs in the radiosity equation, is compact if the domain of radiative interaction is sufficiently regular, we show noncompactness of the operator if the domain is polyhedral. We also show that a stationary operator is never compact when reinterpreted in a transient setting. Moreover, we provide new proofs, which do not use the compactness of K, for 1 being a simple eigenvalue of K for connected enclosures, and for I-(1-e)K being invertible, provided the emissivity e does not vanish identically.
In this paper we will consider elliptic boundary value problems with
oscillatory diffusion coefficient, say A. We will derive regularity
estimates in Sobolev norms which are weighted by certain derivatives of A.
The constants in the regularity estimates then turn out to be independent of
the variations in A.
These regularity results will be employed for the derivation of error
estimates for hp-finite element discretizations which are explicit with
respect to the local variations of the diffusion coefficient.
We consider the numerical solution of projected Lyapunov equations using Krylov subspace iterative methods. Such equations
play a fundamental role in balanced truncation model reduction of descriptor systems. We present generalizations of
the extended block and global Arnoldi methods to projected Lyapunov equations and compare these methods with the alternating direction implicit method with respect to performance on different examples.
A deflation strategy is also proposed to overcome possible breakdown in the
recurrence.
The PSurface Library
(2010)
We describe psurface, a C++ library that allows to store and access piecewise linear mappings between simplicial surfaces in $\R^2$ and $\R^3$. These mappings are stored in a graph data structure and can be constructed explicitly, by projection, or by surface simplification. Piecewise linear maps can be used, e.g., to construct boundary
approximations for finite element grids, and grid intersections for domain decomposition methods. In computer graphics the mappings allow to build level-of-detail representations as well as texture- and bump maps. We document the data structures and algorithms used and show how \psurface is used in the numerical analysis framework Dune
and the visualization software Amira.
We describe the appearance and stability of spatio-temporal periodic
patterns (rotating waves) in unidirectional rings of coupled oscillators
with delayed couplings. We show how delays in the coupling lead
to a splitting of each rotating wave into several new ones. The appearance
of rotating waves is mediated by Hopf bifurcations of the symmetric
equilibrium.
We also conclude that the coupling delays can be effectively
replaced by increasing the number of oscillators in the chain.
The phenomena are shown for Stuart-Landau
oscillators as well as for coupled FitzHugh-Nagumo systems interacting
via excitatory chemical synapses.
Classical surface parameterization algorithms often place singularities
in order to enhance the quality of the resulting parameter map. Unfortunately, singularities of positive integral index (as the north pole of a sphere) were not handled since they cannot be described with piecewise linear parameter functions on a triangle mesh. Preprocessing is needed to adapt the mesh connectivity. We present an extension to the QuadCover parameterization algorithm [KNP07], which allows to handle those singularities. A singularity of positive integral index can be resolved using bilinear parameter functions on quadrilateral elements. This generalization
of piecewise linear functions for quadrilaterals enriches the space of parameterizations. The resulting parameter map can be visualized by textures using a rendering system which supports quadrilateral elements, or it can be used for remeshing into a pure quad mesh.
We study the class of linear differential-algebraic m-input m-output systems
which have a transfer function with proper inverse.
A sufficient condition for the transfer function to have proper inverse
it that the system has 'strict and non-positive relative degree'.
We present two main results:
First, a so called 'zero dynamics form' is derived: this form is - within the class of system equivalence - a simple "almost normal" form of the DAE; it is a counterpart to the well-known Byrnes-Isidori form for
ODE systems with strictly proper transfer function.
The 'zero dynamics form' is exploited to characterize structural properties such as
asymptotically stable zero dynamics,
minimum phase, and high-gain stabilizability.
The zero dynamics are characterized by (A,E,B)-invariant subspaces.
Secondly, it is shown that the 'funnel controller' (that is a static nonlinear output error feedback) achieves, for all DAE systems with asymptotically stable zero dynamics and transfer function with proper inverse, tracking of a reference signal by the output signal within a pre-specified funnel. This funnel determines the transient behaviour.
We study discrete curvatures computed from nets of curvature lines on a given smooth surface and prove their uniform convergence to smooth principal curvatures. We provide explicit error bounds, with constants depending only on properties of the smooth limit surface and the shape regularity of the discrete net.
We present a novel algorithm for automatic parameterization of tube-like surfaces of arbitrary genus such as the surfaces of knots, trees, blood vessels, neurons, or any tubular graph with a globally consistent stripe texture. We use the principal curvature frame field of the underlying tube-like surface to guide the creation of a global, topologically consistent stripe parameterization of the surface. Our algorithm extends the QuadCover algorithm and is based, first, on the use of so-called projective vector fields instead of frame fields, and second, on different types of branch points. That does not only simplify the mathematical theory, but also reduces computation time by the decomposition of the underlying stiffness matrices.
Riemann surfaces naturally appear in the analysis of complex functions that are branched over the complex plane. However, they usually possess a complicated topology and are thus hard to understand. We present an algorithm for constructing Riemann surfaces as meshes in R3 from explicitly given branch points with corresponding branch indices. The constructed surfaces cover the complex plane by the canonical
projection onto R2 and can therefore be considered as multivalued graphs
over the plane – hence they provide a comprehensible visualization of the
topological structure. Complex functions are elegantly visualized using domain coloring on
a subset of C. By applying domain coloring to the automatically constructed Riemann surface models, we generalize this approach to deal with functions which cannot be entirely visualized in the complex plane.
Diffusion weighted imaging is a magnetic resonance based method to investigate
tissue micro-structure especially in the human brain via water diffusion.
Since the standard diffusion tensor model for the acquired data failes in
large portion of the brain voxel more sophisticated models have bee developed.
Here, we report on the package dti and how some of these models
can be used with the package.
The package fmri is provided for analysis of single run functional
Magnetic Resonance Imaging data. It implements structural adaptive smoothing
methods with signal detection for adaptive noise reduction which avoids blurring
of edges of activation areas. fmri provides fmri analysis from time series
modeling to signal detection and publication-ready images.
Modeling the orientation distribution function by mixtures of angular central Gaussian distributions
(2010)
In this paper we develop a tensor mixture model for diffusion weighted imaging
data using an automatic model selection criterion for the order of tensor
components in a voxel. We show that the weighted orientation distribution
function for this model can be expanded into a mixture of angular central
Gaussian distributions. We show properties of this model in extensive
simulations and in a high angular resolution experimental data set. The results
suggest that the model may improve imaging of cerebral fiber tracts. We
demonstrate how inference on canonical model parameters may give rise to new
clinical applications.
In this work, we study the spectra and eigenmodes of the Hessian of various discrete surface energies and discuss applications to shape analysis. In particular, we consider a physical model that describes the vibration modes and frequencies of a surface through the eigenfunctions and eigenvalues of the Hessian of a deformation energy, and we
derive a closed form representation for the Hessian (at the rest state of the energy) for a general class of deformation energies. Furthermore, we design a quadratic energy, such that the eigenmodes of the Hessian of
this energy are sensitive to the extrinsic curvature of the surface. Based on these spectra and eigenmodes, we derive two shape signatures. One that measures the similarity of points on a surface, and another that
can be used to identify features of the surface. In addition, we discuss a
spectral quadrangulation scheme for surfaces.
We discuss the perturbation analysis for
eigenvalues and eigenvectors of structured homogeneous matrix polynomials with
Hermitian, skew-Hermitian, H-even and H-odd structure.
We construct minimal structured perturbations (structured backward errors) such that an
approximate eigenpair is an exact eigenpair of an appropriate perturbed structured matrix
polynomial. We present various comparisons with unstructured backward
errors and previous error bounds derived for the non-homogeneous case
and show that our bounds present a significant improvement.
Many applications give rise to matrix polynomials whose coefficients have
a kind of reversal symmetry, a structure we call palindromic.
Several properties of scalar palindromic polynomials are derived,
and together with properties of compound matrices, used to
establish the Smith form of regular and singular T-palindromic matrix polynomials,
over arbitrary fields.
The invariant polynomials are shown to
inherit palindromicity,
and their structure is described in detail.
Jordan structures of palindromic matrix polynomials are characterized,
and necessary conditions for the
existence of structured linearizations established.
In the odd degree case, a constructive procedure for building
palindromic linearizations shows that the necessary conditions are sufficient as well.
The Smith form for *-palindromic polynomials is also analyzed. Finally, results for palindromic matrix polynomials over fields of
characteristic two are presented.
We define a risk averse nonanticipative feasible policy for multistage stochastic programs and propose a methodology to implement it. The approach is based on dynamic programming equations written for a risk averse formulation of the problem.
This formulation relies on a new class of multiperiod risk functionals called extended polyhedral risk measures. Dual representations of such risk functionals are given and used to derive conditions of coherence. In the one-period case, conditions for convexity and consistency with second order stochastic dominance are also provided. The risk averse dynamic programming equations are specialized considering convex combinations of one-period extended polyhedral risk measures such as spectral risk measures.
To implement the proposed policy, the approximation of the risk averse recourse functions for stochastic linear programs is discussed. In this context, we detail a stochastic dual dynamic programming algorithm which converges to the optimal value of the risk averse problem.
We derive a Crooks-Jarzynski-type identity for computing free energy differences between metastable states that is based on nonequilibrium diffusion processes. Furthermore we outline a brief derivation of an infinite-dimensional stochastic partial differential equation that can be used to efficiently generate the ensemble of trajectories connecting the metastable states.
To address the plurality of interpretations of the subjective notion of risk, we describe it by means of a risk order and concentrate on the context invariant features of diversification and monotonicity. Our main results are uniquely characterized robust representations of lower semicontinuous risk orders on vector spaces and convex sets. This representation covers most instruments related to risk and allow for a differentiated interpretation depending on the underlying context which is illustrated in different settings: For random variables, risk perception can be interpreted as model risk, and we compute among others the robust representation of the economic index of riskiness. For lotteries, risk perception can be viewed as distributional risk and we study the "Value at Risk". For consumption patterns, which excerpt an intertemporality dimension in risk perception, we provide an interpretation in terms of discounting risk and discuss some examples.
We study the risk assessment of uncertain cash flows in terms of dynamic convex risk measures for processes as introduced in Cheridito, Delbaen, and Kupper (2006). These risk measures take into account not only the amounts but also the timing of a cash flow. We discuss their robust representation in terms of suitably penalized probability measures on the optional $\sigma$-field. This yields an explicit analysis both of model and discounting ambiguity. We focus on supermartingale criteria for time consistency. In particular we show how ``bubbles'' may appear in the dynamic penalization, and how they cause a breakdown of asymptotic safety of the risk assessment procedure.
Dynamic risk measures
(2010)
This paper gives an overview of the theory of dynamic convex risk measures for random variables in discrete time setting. We summarize robust representation results of conditional convex risk measures, and we characterize various time consistency properties of dynamic risk measures in terms of acceptance sets, penalty functions, and by supermartingale properties of risk processes and penalty functions.
The classical valuation of an uncertain cash flow in discrete time consists in taking the expectation of the sum of the discounted future payoffs under a fixed probability measure, which is assumed to be known. Here we discuss the valuation problem in the context of Knightian uncertainty. Using results from the theory of convex risk measures, but without assuming the existence of a global reference measure, we derive a robust representation of concave valuations with an infinite time horizon, which specifies the interplay between model uncertainty and uncertainty about the time value of money.
Recently, there is a growing trend to offer guarantee products where the investor is allowed to shift her account/investment value between multiple funds. The switching right is granted a finite number per year, i.e. it is American style with multiple exercise possibilities. In consequence, the pricing and the risk management is based on the switching strategy which maximizes the value of the guarantee put option. We analyze the optimal stopping problem in the case of one switching right within different model classes and compare the exact price with the lower price bound implied by the optimal deterministic switching time. We show that, within the class of log-price processes with independent increments, the stopping problem is solved by a deterministic stopping time if (and only if) the price process is in addition continuous. Thus, in a sense, the Black & Scholes model is the only (meaningful) pricing model where the lower price bound gives the exact price. It turns out that even moderate deviations from the Black & Scholes model assumptions give a lower price bound which is really below the exact price. This is illustrated by means of a stylized stochastic volatility model setup.
In this paper we consider the optimal stopping problem for general dynamic monetary utility functionals. Sufficient conditions for the Bellman principle and the existence of optimal stopping times are provided. Particular attention is payed to representations which allow for a numerical treatment in real situations. To this aim, generalizations of standard evaluation methods like policy iteration, dual and consumption based approaches are developed in the context of general dynamic monetary utility functionals. As a result, it turns out that the possibility of a particular generalization depends on specific properties of the utility functional under consideration.
Boolean modeling frameworks have long since proved their worth for capturing and analyzing essential characteristics of complex systems.
Hybrid approaches aim at exploiting the advantages of Boolean formalisms while refining expressiveness. In this paper, we present a formalism that augments Boolean models with stochastic aspects. More specifically, biological reactions effecting a system in a given state are associated
with probabilities, resulting in dynamical behavior represented as a Markov chain. Using this approach, we model and analyze the cytokinin
response network of Arabidopsis thaliana with a focus on clarifying the character of an important feedback mechanism.
Bovine fertility is the subject of extensive research in animal sciences,
especially because fertility of dairy cows has declined during the last
decades. The regulation of estrus is controlled by the complex interplay
of various organs and hormones. Mathematical modeling of the bovine
estrous cycle could help in understanding the dynamics of this complex
biological system. In this paper we present a mechanistic mathematical
model of the bovine estrous cycle that includes the processes of follicle
and corpus luteum development and the key hormones that interact to
control these processes. The model generates successive estrous cycles of
21 days, with three waves of follicle growth per cycle. The model contains
12 differential equations and 54 parameters. Focus in this paper is on
development of the model, but also some simulation results are presented,
showing that a set of equations and parameters is obtained that describes
the system consistent with empirical knowledge. Even though the majority
of the mechanisms that are included in the model are based on relations
that in literature have only been described qualitatively (i.e. stimulation
and inhibition), the output of the model is surprisingly well in line with
empirical data. This model of the bovine estrous cycle could be used
as a basis for more elaborate models with the ability to study effects of
external manipulations and genetic differences.
We consider simple models of financial markets with less and better
informed investors described by a smaller and a larger filtration on a
general stochastic basis that describes the market dynamics, including
continuous and jump components. We study the relation between different forms of non existance of arbitrage and the characteristics of the stochastic basis under the different filtrations. This is achieved through the analysis of the properties of the numéraire portfolio. Furthermore, we focus on the problem of calculating the additional logarithmic utility of the better informed investor in terms of the Shannon antropy of is additional information. The information drift, i.e. the drift to eliminate in order to preserved the martingale property in the larger filtration terms out to be the crucial quantity needed to tackle these problems. We show that the expected
ed logarithmic utility increment due to better information equals its Shannon
entropy also in case of a pure jump basis with jumps that are quadratically
hedgeable, and so extend a similar result known for bases consisting of
continuous semimartingales. An example illustrates that the equality may
not persist if both continuous and jump components are present in the
underlying.
Motivated by the analysis of passive control systems, we undertake a detailed perturbation analysis of Hamiltonian matrices that have eigenvalues on the imaginary axis. We construct minimal Hamiltonian perturbations that move and coalesce eigenvalues of opposite sign characteristic to form multiple eigenvalues with mixed sign characteristics, which are then moved from the imaginary axis to specific locations in the complex plane by small Hamiltonian perturbations. We also present a numerical method to compute upper bounds for the minimal perturbations that move all eigenvalues of a given Hamiltonian matrix outside a vertical strip along the imaginary axis.
In this work we propose a general framework for the structured perturbation
analysis of several classes of structured matrix polynomials in homogeneous
form, including complex symmetric, skew-symmetric, even and odd matrix polynomials. We introduce structured backward errors for approximate eigenvalues and eigenvectors and we construct minimal structured perturbations such that an approximate eigenpair is an exact eigenpair of an appropriately perturbed matrix polynomial. This work extends previous work for the non-homogeneous case (we include infinite eigenvalues) and we show that the structured backward errors improve the known unstructured backward errors.
Mathematical programs in which the constraint set is partially defined by the solutions of an elliptic variational inequality, so-called ``elliptic MPECs'', are formulated in reflexive Banach spaces. With the goal of deriving explicit first order optimality conditions amenable to the development of numerical procedures, variational analytic concepts are both applied and further developed. The paper is split into two main parts. The first part concerns the derivation of conditions in which the state constraints are assumed to be polyhedric sets. This part is then completed by two examples, the latter of which involves pointwise bilateral bounds on the gradient of the state. The second part begins with the derivation of a formula for the second order (Mosco) epiderivative of the indicator function of a general convex set. This result is then used to derive analogous conditions to those which are presented in the first part. Finally, an elliptic MPEC is considered important to the study of elasto-plasticity in which the pointwise Euclidean norm of the gradient of the state is bounded. Explicit strong stationarity conditions are provided for this problem.
This paper is devoted to the numerical approximation of Lyapunov and Sacker-Sell spectral intervals for linear differential-algebraic equations (DAEs). The spectral analysis for DAEs is improved and the concepts of leading directions and solution subspaces associated with spectral intervals are extended to DAEs. Numerical methods
based on smooth singular value decompositions are introduced for computing all or only some spectral intervals and their associated leading directions. The numerical algorithms as well as implementation issues are discussed in detail and numerical examples are presented to illustrate the theoretical results.
This paper proposes a new mathematical model for the open pit mine planning problem,
based on continuous functional analysis. The traditional models for this problem have been
constructed by using discrete 0-1 decision variables, giving rise to large-scale combinatorial
and Mixed Integer Programming (MIP) problems. Instead, we use a continuous approach
which allows for a refined imposition of slope constraints associated with geotechnical stability.
The model introduced here is posed in a suitable functional space, essentially the
real-valued functions that are Lipschitz continuous on a given two dimensional bounded region.
We derive existence results and investigate some qualitative properties of the solutions
Cross–derivatives are mixed partial derivatives that are obtained by differentiating at most
once in every coordinate direction. They are a computational tool in combinatorics and high–
dimensional integration. Here we present two methods of computing exact values of all cross–
derivatives at a given point both following the general philosophy of automatic differentiation.
Implementation details are discussed and numerical results given.
We consider the behavior of a modulated wave solution to
an $\mathbb{S}^1$-equivariant autonomous system of differential equations under an external
forcing of modulated wave type. The modulation frequency of the forcing is assumed to be close to the
modulation frequency of the modulated wave solution, while the wave frequency of the forcing is supposed to be far
from that of the modulated wave solution. We describe the domain in the three-dimensional
control parameter space (of frequencies and amplitude of the forcing)
where stable locking of the modulation frequencies of the forcing and the modulated wave solution
occurs.
Our system is a simplest case scenario for the behavior of self-pulsating lasers under the influence of external
periodically modulated
optical signals.
We show that the coupled balance equations for a large class of dissipative materials
can be cast in the form of GENERIC (General Equations for Non-Equilibrium
Reversible Irreversible Coupling). In dissipative solids, also called generalized standard
materials, the state of a material point is described by dissipative internal variables in addition to the elastic deformation and the temperature. The framework GENERIC allows
for an efficient derivation of thermodynamically consistent coupled field equations,
while revealing additional underlying physical structures, like the role of the free energy
as the driving potential for reversible effects and the role of the free entropy (Massieu potential) as the driving potential for dissipative effects.
Applications to large and small-strain thermoplasticity is given. Moreover, for the
quasistatic case, where the deformation can be statically eliminated, we derive a generalized
gradient structure for the internal variable and the temperature with a reduced
entropy as driving functional.
In this paper we consider the first exit problem of an overdamped
Lévy driven particle in a confining potential. We survey results
obtained in recent years from our work on the Kramers' times for
dynamical systems of this type with Lévy perturbations containing
heavy, and exponentially light jumps, and compare them to the well
known case of dynamical systems with Gaussian perturbations. It
turns out that exits induced by Lévy processes with jumps are
always essentially faster than Gaussian exits.
In this paper we study BSDEs arising from a special class of backward stochastic partial differential equations (BSPDEs) that is intimately related to utility maximization problems with respect to arbitrary utility functions. After providing existence and uniqueness we discuss the numerical realizability. Then we study utility maximization problems on incomplete financial markets whose dynamics are governed by continuous semimartingales. Adapting standard methods that solve the utility maximization problem using BSDEs, we give solutions for the portfolio optimization problem which involve the delivery of a liability at maturity. We illustrate our study by numerical simulations for selected examples. As a byproduct we prove existence of a solution to a very particular quadratic growth BSDE with unbounded terminal condition. This complements results on this topic obtained in [6,7,8].
We prove central and non-central limit theorems for the
Hermite variations of the anisotropic fractional Brownian sheet
$W^{\alpha, \beta}$
with Hurst parameter $(\alpha, \beta) \in (0,1)2$. When $0<\alpha \leq
1-\frac{1}{2q}$ or $0<\beta \leq 1-\frac{1}{2q}$ a central limit theorem
holds for the renormalized Hermite variations of order $q\geq 2$, while
for $1-\frac{1}{2q}<\alpha, \beta < 1$ we prove that these variations
satisfy a non-central limit theorem. In fact, they converge to a random
variable which is the value of a two-parameter Hermite process at time
$(1,1)$.
The weak Stratonovich integral with respect to fractional Brownian motion with Hurst parameter 1/6
(2010)
Let $B$ be a fractional Brownian motion with Hurst parameter
$H=1/6$. It is known that the symmetric Stratonovich-style Riemann sums
for $\int g(B(s))\,dB(s)$ do not, in general, converge in probability.
We show, however, that they do converge in law in the Skorohod space of
c\`adl\`ag functions. Moreover, we show that the resulting stochastic
integral satisfies a change of variable formula with a correction term
that is an ordinary It\^o integral with respect to a Brownian motion
that is independent of $B$.
In this Note we consider a Lipschitz backward stochastic
differential equation (BSDE) driven by a continuous martingale $M$. We
prove (in Theorem \ref{theorem:main}) that if $M$ is a strong Markov
process and if the BSDE has regular data then the unique solution
$(Y,Z,N)$ of the BSDE is reduced to $(Y,Z)$, \textit{i.e.} the
orthogonal martingale $N$ is equal to zero, showing that in a Markovian
setting the "usual" solution $(Y,Z)$ (of a BSDE with regular data) has
not to be completed by a strongly orthogonal component even if $M$ does
not enjoy the martingale representation property.
We extend some recent works by Delong and Imkeller concerning Backward
stochastic differential equations with time delayed generators (delay
BSDE). We provide sharper a priori estimates and show that the solution
of a delay BSDE is in $L^p$. We introduce decoupled systems of SDE and
delay BSDE (which we term delay FBSDE) and give sufficient conditions
for the variational differentiability of their solutions. We connect
these derivatives to the Malliavin derivatives of such delay FBSDE via
the usual representation formulas which in turn give access to several
path regularity results. In particular we prove an extension of the
$L2$-path regularity result for delay FBSDE.
Model Reduction for a Class of Nonlinear Electrical Circuits by Reduction of Linear Subcircuits
(2010)
We analyze a model reduction approach for a class of electrical circuits containing nonlinear resistance.
In our approach
the linear subcircuits are extracted and replaced with linear passive reduced-order models. The resulting nonlinear
reduced-order model preserves admissibility and passivity. Moreover, we derive a-priori bounds for the error between
the input-output map of the original circuit equations and that of our reduced-order model. These bounds
are valid for all inputs. Since only linear subcircuits are reduced, our approach is effective when the number of nonlinear resistances is relatively small. The performance of our approach is illustrated numerically.
This paper concerns $n\times n$ linear one-dimensional hyperbolic systems of the type
$$
\om\partial_tu_j + a_j(x)\partial_xu_j + \sum\limits_{k=1}^nb_{jk}(x)u_k = f_j(x,t),\; j=1,\ldots,n,
$$
with periodicity conditions in time and reflection boundary conditions in space.
We state sufficient conditions on the data $\om, a_j$ and $b_{jk}$
such that the system has a Fredholm like solvability behavior.
Moreover, we state sufficient conditions on the data such that for any right hand side there exists exactly
one solution, that the solution survives under small perturbations of the data, and that the corresponding
data-to-solution-map
is smooth with respect to appropriate function space norms. In particular, those sufficient conditions
imply that no small denominator effects occur. Moreover, we show that perturbations of the coefficients $\om$ and $a_j$ lead to
essentially different results than perturbations of the coefficients $b_{jk}$, in general.
In this article we compare two different calmness conditions which are
widely used in the literature on bilevel programming and on mathematical
programs with equilibrium constraints. In order to do so, we consider convex
bilevel programming as a kind of intersection between both research areas.
The so-called partial calmness concept is based on the function value
approach for describing the lower level solution set. Alternatively,
calmness in the sense of multifunctions may be considered for perturbations
of the generalized equation representing the same lower level solution set.
Both concepts allow to derive first order necessary optimality conditions
via tools of generalized differentiation introduced by Mordukhovich. They
are very different, however, concerning their range of applicability and the
form of optimality conditions obtained. The results of this paper seem to
suggest that partial calmness is considerably more restrictive than calmness
of the perturbed generalized equation. This fact is also illustrated by
means of a dicretized obstacle control problem.
Based on a thermodynamically consistent model for precipitation in gallium arsenide crystals including surface tension and bulk stresses by Dreyer and Duderstadt, we propose different mathematical models to describe the size evolution of liquid droplets in a crystalline solid. The first class of models treats the diffusion-controlled regime of interface motion, while the second class is concerned with the interface-controlled regime of interface motion. Our models take care of conservation of mass and substance. We consider homogenised models, where different length scales of the experimental situation have been exploited in order to simplify the equations. These homogenised models generalise the well-known Lifshitz-Slyozov-Wagner model for Ostwald ripening. Mean field models capture the main properties of our system and are well adapted for numerics and further analysis. Numerical evidence suggests in which case which one of the two regimes might be appropriate to the experimental situation.
We introduce an electronic model for solar cells including energy resolved defect
densities. The resulting drift-diffusion model corresponds to a generalized
van Roosbroeck system with additional source terms coupled with ODEs containing space and
energy as parameters for all defect densities. The system has to be considered in
heterostructures and with mixed boundary conditions from device simulation.
We give a weak formulation of the problem. If the boundary data and the sources
are compatible with thermodynamic equilibrium the free energy along solutions
decays monotonously. In other cases it may be increasing, but we estimate its growth.
We establish boundedness and uniqueness results and prove the existence of a
weak solution. This is done by considering a regularized problem, showing its
solvability and the boundedness of its solutions independent of the regularization level.
We prove global convergence of an inexact polyhedral Gau\ss--Seidel method for the minimization of strictly convex functionals that are continuously differentiable on each polyhedron of a polyhedral decomposition of
their domains of definition. While being known to be very slow by themselves, such methods are a cornerstone for fast, globally convergent multigrid methods. Our result generalizes the proof of Kornhuber and Krause [2006] for differentiable functionals on the Gibbs simplex. Example applications are given that require the generality of our approach.
Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests
(2010)
Convexity is an important property in nonlinear optimization since it allows to apply efficient local methods for finding global solutions. We propose to apply symbolic methods to prove or disprove convexity of rational functions over a polyhedral domain. Our algorithms reduce convexity questions to real quantifier elimination problems. Our methods are implemented and publicly available in the open source computer algebra system REDUCE. Our long term goal is to integrate REDUCE as a ``workhorse'' for symbolic computations into a numerical solver.
The aim of this paper is to devise an adaptive timestep control in the contact--stabilized Newmark method (CONTACX) for dynamical contact problems between two viscoelastic bodies in the framework of Signorini's condition. In order to construct a comparative scheme of higher order accuracy, we extend extrapolation techniques. This approach demands a subtle theoretical investigation of an asymptotic error expansion of the contact--stabilized Newmark scheme. On the basis of theoretical insight and numerical observations, we suggest an error estimator and a timestep selection which also cover the presence of contact. Finally, we give a numerical example.
We propose a robust and efficient numerical discretization scheme for the infinitesimal generator of a diffusion process based on a finite volume approximation. The resulting discrete-space operator can be interpreted as a jump process on the mesh whose invariant measure is precisely the cell approximation of the Boltzmann distribution of the original process. Moreover the resulting jump process preserves the detailed balance property of the original stochastic process.
We revisit the problem of the linear response of a constrained mechanical system. In doing so we show that the standard expressions of Green and Kubo carry over to the constrained case without any alteration. The argument is based on the appropriate definition of constrained expectations by means of which Liouville’s theorem and the Green-Kubo relations naturally follow.
We propose a nonequilibrium sampling method for computing free energy profiles along a given reaction coordinate. The method consists of two parts: a controlled Langevin sampler that generates nonequilibrium bridge paths conditioned by the reaction coordinate, and Jarzynski’s formula for reweighting the paths. Our derivation of the equa- tions of motion of the sampler is based on stochastic perturbation of a controlled dissipative Hamiltonian system, for which we prove Jarzynski’s identity as a special case of the Feynman-Kac formula. We illustrate our method by means of a suitable numerical example and briefly discuss issues of optimally choosing the control protocol for the reaction coordinate.
We study balanced model reduction of partially-observed linear stochastic differential equa- tions of Langevin type. Balancing the equations of motion gives rise to a singularly perturbed system of equations with slow and fast degrees of freedom, and we prove that in the limit of the fast variables becoming infinitely fast, the solutions converge to the solution of a reduced-order Langevin equation. We illustrate the method with several numerical examples and discuss the relation to model reduction of deterministic control systems that have an underlying Hamiltonian structure.
We study balanced model reduction for stable bilinear systems in the limit of partly vanishing Hankel singular values. We show that the dynamics admit a splitting into fast and slow subspaces and prove an averaging principle for the slow dynamics. We illustrate our method with an example from stochastic control (density evolution of a dragged Brownian particle) and discuss issues of structure preservation and positivity.
This paper presents three different adaptive algorithms for eigenvalue problems
associated with non-selfadjoint partial differential
operators. The basis for the developed algorithms is a homotopy method.
The homotopy method starts from a well-understood selfadjoint problem,
for which well-established adaptive methods are available.
Apart from the adaptive grid refinement, the progress of the homotopy as
well as the solution of the iterative method are adapted to balance the contributions
of the different error sources.
The first algorithm balances the homotopy, discretization and approximation errors with respect
to a fixed step-size $\tau$ in the homotopy.
The second algorithm combines the adaptive step-size control for the homotopy
with an adaptation in space that ensures an error below a fixed tolerance $\varepsilon$.
The third algorithm allows the complete adaptivity in space,
homotopy step-size as well as the iterative algebraic eigenvalue solver.
All three algorithms are compared in numerical examples.
Given a system of closed convex domains (inclusions) in n-dimensional Euclidean space, new computational meshes are introduced which partition the convex hull of the inclusion set into simple geometric objects. These partitions generalize the concept of Delaunay triangulations by interpreting the inclusions as generalized vertices while the remaining elements of the partition serve as connections between generalized vertices and therefore assume the classical role of edges, faces, etc. The proposed partitions are derived in two different ways: by exploiting duality with respect to certain generalized Voronoi partitions and by generalizing the well known Delaunay (empty circumcircle) criterion.
Generalized Delaunay partitions are of practical importance for the modeling of particle- and fiber-reinforced composite materials
since they enable an efficient conforming resolution of the highly complicated component geometries. The number of elements in the partitions is proportional to the number of inclusions which is minimal.
Functional Magnetic Resonance Imaging inherently involves noisy measurements and a severe multiple test
problem. Smoothing is usually used to reduce the effective number of multiple
comparisons and to locally integrate the signal and hence increase the
signal-to-noise ratio. Here, we provide a new structural adaptive segmentation
algorithm (AS)
that naturally combines the signal detection with noise reduction in one procedure.
Moreover, the new method
is closely related to a recently proposed structural adaptive smoothing
algorithm and preserves shape and spatial extent of activation areas without
blurring the borders.
MINLP Solver Software
(2010)
Motivated by an obstacle problem for a membrane
subject to cohesion forces, constrained minimization problems involving
a non-convex and non-differentiable objective functional
representing the total potential energy are considered. The associated
first order optimality system leads to a hemi-variational inequality,
which can also be interpreted as a special complementarity
problem in function space. Besides an analytical investigation
of first-order optimality, a primal-dual active set solver is introduced.
It is associated to a limit case of a semi-smooth Newton
method for a regularized version of the underlying problem class.
For the numerical algorithms studied in this paper, global as well as
local convergence properties are derived and verified numerically.
A duality based semismooth Newton framework for solving variational inequalities of the second kind
(2010)
In an appropriate function space setting, semismooth Newton methods are proposed
for iteratively computing the solution of a rather general class of variational inequalities (VIs) of the
second kind. The Newton scheme is based on the Fenchel dual of the original VI problem which
is regularized if necessary. In the latter case, consistency of the regularization with respect to the
original problem is studied. The application of the general framework to specific model problems
including Bingham flows, simplified friction, or total variation regularization in mathematical imaging
is described in detail. Finally, numerical experiments are presented in order to verify the theoretical
results.
In this paper a general form of the infinite-horizon linear quadratic control problem is considered. We will discuss quadratic cost functionals which involve not only the state and input-variables but also derivatives of the state and input-variables of arbitrary order under constraints given by linear systems of higher order. We will examine two results that relate the linear quadratic control problem to an optimality system, which is given through a para-Hermitian matrix polynomial. The results can be applied to general rectangular descriptor systems (see Subsection 6.1) to obtain results which so far were only known for quadratic descriptor systems. Also we will see that the notion of dissipativity (when introduced in the proper way) is equivalent to the solvability of the linear quadratic control problem.
The behavior approach and the problem of dissipativity have both been introduced and studied extensively by Willems et al. However, a computationally feasible method to check dissipativity is missing. Current methods will mostly rely on symbolic representations of rational functions. We will discuss a new characterization for linear systems in behavior form that allows to check dissipativity via the solution of a para-Hermitian, polynomial eigenvalue problem. Thus, we can employ standard methods of cubic complexity.
Under market frictions like illiquidity or transaction costs, contingent claims
can incorporate some inevitable intrinsic risk that cannot be completely hedged
away but remains with the holder. In general, they cannot be synthesized by
dynamical trading in liquid assets and hence not be priced by no-arbitrage arguments alone. Still, an agent can determine a valuation with respect to her
preferences towards risk. The utility indifference value for a variation in the
quantity of illiquid assets held by the agent is defined as the compensating variation
of wealth, under which her maximal expected utility remains unchanged.
Arrow Debreu Prices
(2010)
Arrow Debreu prices are the prices of ‘atomic’ time and state contingent
claims which deliver one unit of a specific consumption good if a specific uncertain
state realizes at a specific future date. For instance, claims on the good
‘ice cream tomorrow’ are split into different commodities depending whether the
weather will be good or bad, so that good-weather and bad-weather ice cream
tomorrow can be traded separately. Such claims were introduced by K.J. Arrow
and G. Debreu in their work on general equilibrium theory under uncertainty,
to allow agents to exchange state and time contingent claims on goods. Thereby
the general equilibrium problem with uncertainly can be reduced to a conventional
one without uncertainty. In finite state financial models, Arrow-Debreu
securities delivering one unit of the numeraire good can be viewed as natural
atomic building blocks for all other state-time contingent financial claims; their
prices determine a unique arbitrage-free price system.
We present and compare two different approaches to conditional
risk measures. One approach draws from vector space based convex analysis
and presents risk measures as functions on L^p spaces while the other approach
utilizes module based convex analysis where conditional risk measures are defined on L^p type modules. Both approaches utilize general duality theory for
vector valued convex functions in contrast to the current literature in which
we fi nd ad hoc dual representations. By presenting several applications such
as monotone and sub(cash) invariant hulls with corresponding examples we
illustrate that module based convex analysis is well suited to the concept of
conditional risk measures.
In this paper, we propose and investigate numerical methods based on QR factorization for computing all or some Lyapunov or Sacker-Sell spectral intervals for
linear differential-algebraic equations.
Furthermore, a perturbation and error analysis for these methods is presented. We
investigate how errors in the data and in the numerical integration affect the
accuracy of the approximate spectral intervals. Although we need to integrate
numerically some differential-algebraic systems on usually very long
time-intervals, under certain assumptions, it is shown that the error of the
computed spectral intervals can be controlled by the local error of numerical
integration and the error in solving the algebraic constraint.
Some numerical examples are presented to illustrate the theoretical results.
We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL,
DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on realistic network topologies and node architectures as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial
benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A
sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks.
A new implicitly-restarted Krylov subspace method
for real symmetric/skew-symmetric generalized eigenvalue problems
is presented. The new method improves and generalizes the SHIRA method
to the case where the skew symmetric matrix is singular.
It computes a few eigenvalues and eigenvectors of the matrix pencil
close to a given target point. Several applications from control theory are
presented and the properties of the new method are illustrated by benchmark
examples.
In this paper, we investigate the interconversion processes of the major flame retardant - 1,2,5,6,9,10-hexabromocyclododecane (HBCD) - by the means of statistical thermodynamics based on classical force-fields. Three ideas will be presented. First, the application of classical hybrid Monte-Carlo simulations for quantum mechanical processes will be justified. Second, the problem of insufficient convergence properties of hybrid Monte-Carlo methods for the generation of low temperature canonical ensembles will be solved by an interpolation approach. Furthermore, it will be shown how free energy differences can be used for a rate matrix computation. The results of our numerical simulations will be compared to experimental results.
Keywords: Markov process, molecular dynamics, rate matrix
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We
identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems
by a factor of two on average.
We study the perturbation theory of structured matrices under
structured rank one perturbations, and then focus on several classes of complex
matrices. Generic Jordan structures of perturbed matrices are identified.
It is shown that the perturbation
behavior of the Jordan structures
is substantially different from the corresponding theory for unstructured generic
rank one perturbations.
An one-dimensional Kohn-Sham system for spin particles is considered which effectively describes semiconductor nanostructures and which is investigated at zero temperature. We prove the existence of solutions and derive a priori estimates. For this purpose we find estimates for eigenvalues of the Schrödinger operator with effective Kohn-Sham potential and obtain $W^1,2$-bounds of the associated particle density operator. Afterwards, compactness and continuity results allow to apply Schauder's fixed point theorem. In case of vanishing exchange-correlation potential uniqueness is shown by monotonicity arguments. Finally, we investigate the behavior of the system if the temperature approaches zero.
We regard drift-diffusion equations for semiconductor devices in Lebesgue spaces. To that end we reformulate the (generalized) van Roosbroeck system as an evolution equation for the potentials to the driving forces of the currents of electrons and holes. This evolution equation falls into a class of quasi-linear parabolic systems which allow unique, local in time solution in certain Lebesgue spaces. In particular, it turns out that the divergence of the electron and hole current is an integrable function. Hence, Gauss' theorem applies, and gives the foundation for space discretization of the equations by means of finite volume schemes. Moreover, the strong differentiability of the electron and hole density in time is constitutive for the implicit time discretization scheme. Finite volume discretization of space, and implicit time discretization are accepted custom in engineering and scientific computing. ---This investigation puts special emphasis on non-smooth spatial domains, mixed boundary conditions, and heterogeneous material compositions, as required in electronic device simulation.
The goal of this paper is to show how the heat treatment of steel can be modelled in terms of a mathematical optimal
control problem. The approach is applied to laser surface hardening and the cooling of a steel slab including
mechanical effects. Finally, it is shown how the results can be utilized in industrial practice by a coupling with
machine-based control.
In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.
Stability-based methods for scenario generation in stochastic programming are reviewed. In particular, we briefly discuss Monte Carlo sampling, Quasi-Monte Carlo methods, quadrature rules based on sparse grids and optimal quantization. In addition, we provide some convergence results based on recent developments in multivariate integration. The method of optimal scenario reduction and techniques for scenario trees generation are also reviewed.
An adaptive finite element semi-smooth Newton solver for
the Cahn-Hilliard model with double obstacle free energy is proposed. For this purpose, the governing system is discretised in time using a semi-implicit scheme, and the resulting time-discrete system is formulated as an optimal control problem with pointwise constraints on the control. For the numerical solution of the optimal control problem, we propose a function space based algorithm which combines a Moreau-Yosida regularization technique for handling the control constraints with a semi-smooth-Newton method for solving the optimality systems of the resulting sub-problems. Further, for the discretization in space and in connection with the proposed algorithm, an adaptive finite element method is considered. The performance of the overall algorithm is illustrated by numerical experiments.
We study the dynamics of a ring of unidirectionally coupled autonomous
Duffing oscillators. Starting from a situation where the individual
oscillator without coupling has only trivial equilibrium dynamics,
the coupling induces complicated transitions to periodic, quasiperiodic,
chaotic, and hyperchaotic behavior. We study these transitions in
detail for small and large numbers of oscillators. Particular attention
is paid to the role of unstable periodic solutions for the appearance
of chaotic rotating waves, spatiotemporal structures and the Eckhaus
effect for a large number of oscillators. Our analytical and numerical
results are confirmed by a simple experiment based on the electronic
implementation of coupled Duffing oscillators.
Abstract—We present a novel coder for lossless compression
of adaptive multiresolution meshes that exploits their special
hierarchical structure. The heart of our method is a new
progressive connectivity coder that can be combined with
leading geometry encoding techniques. The compressor uses
the parent/child relationships inherent to the hierarchical mesh.
We use the rules that accord to the refinement scheme and
store bits only where it leaves freedom of choice, leading to
compact codes that are free of redundancy. To illustrate our
scheme we chose the widespread red-green refinement, but
the underlying concepts can be directly transferred to other
adaptive refinement schemes as well. The compression ratio of
our method exceeds that of state-of-the-art coders by a factor
of 2 to 3 on most of our benchmark models.
{We suggest hierarchical a posteriori error estimators for time-discretized
Allen-Cahn and Cahn-Hilliard equations with logarithmic potential and investigate
their robustness numerically.
We observe that the associated effectivity ratios seem to saturate for decreasing mesh size
and are almost independent of the temperature.
For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in
the sense of algebraic geometry. Special attention is paid to the perturbation
behavior of the sign characteristic. Typically, under such a perturbation,
for every given eigenvalue, the largest Jordan block of the eigenvalue is
destroyed and (in case the eigenvalue is real) all other Jordan blocks
keep their sign characteristic. The new eigenvalues, i.e., those eigenvalues of
the perturbed matrix that are not eigenvalues of the original matrix,
are typically simple, and in some cases information is provided about their sign
characteristic (if the new eigenvalue is real). The main results are proved by using
the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky
canonical form and on general results concerning rank one perturbations.
We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors.
For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction.
With the close relation between contiguous scheduling and strip packing, our FPTAS
is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.
This paper is intended to be a first step towards the continuous dependence of dynamical contact problems on the initial data as well as the uniqueness of a solution. Moreover, it provides the basis for a proof of the convergence of popular time integration schemes as the Newmark method.
We study a frictionless dynamical contact problem between both linearly elastic and viscoelastic bodies which is formulated via the Signorini contact conditions. For viscoelastic materials fulfilling the Kelvin-Voigt constitutive law, we find a characterization of the class of problems which satisfy a perturbation result in a non-trivial mix of norms in function space. This characterization is given in the form of a stability condition on the contact stresses at the contact boundaries.
Furthermore, we present perturbation results for two well-established approximations of the classical Signorini condition: The Signorini condition formulated in velocities and the model of normal compliance, both satisfying even a sharper version of our stability condition.