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 deals with the numerical solution of the time{dependent Schroedinger-
Poisson system in the spherically symmetric case. Since the problem is posed on an
unbounded domain one has to introduce artificial boundary conditions to confine
the computational domain. The main topic of this work is the construction of a
so-called discrete transparent boundary condition (TBC) for a Crank-Nicolsontype
predictor-corrector scheme for solving the Schroedinger-Poisson system. This
scheme has the property of mass and energy conservation exactly on the discrete
level. We propose different strategies for the discrete TBC and present an efficient
implementation. Finally, a numerical example illustrate the findings and shows the
comparison results between the different approaches.
A 1D coupled drift-diffusion dissipative Schroedinger model (hybrid model), which
is capable to describe the transport of electrons and holes in semi-conductor devices
in a non-equilibrium situation, is mathematically analyzed. The device domain is
split into a part where the transport is well-described by the drift-diffusion equations
(classical zone) and a part where a quantum description via a dissipative Schroedinger
system (quantum zone) is used. Both system are coupled such that the continuity
of the current densities is guaranteed. The electrostatic potential is self-consistently
determined by Poisson's equation on the whole device. We show that the hybrid
model is well-posed, prove existence of solutions and show their uniform boundedness
provided the distribution function satisfy a so-called balance condition. The current
densities are different from zero in the non-equilibrium case and uniformly bounded.
We revisit here the situation of a thin liquid film driven up an
inclined substrate by a thermally induced Marangoni shear stress against
the counter-acting parallel component of gravity. In contrast to previous
studies, we focus here on the meniscus region, in the case where the substrate
is nearly horizontal, so there is a significant contribution from the
normal component of gravity. Our numerical simulations show that the
time-dependent lubrication model for the film profile can reach a steady
state in the meniscus region that is unlike the monotonic solutions found
in [MÄunch, SIAM J. Appl. Math., 62(6):2045-2063, 2002]. A systematic
investigation of the steady states of the lubrication model is carried out by
studying the phase space of the corresponding third order ODE system. We
find a rich structure of the phase space including multiple non-monotonic
solutions with the same far-field film thickness.
Transient analysis in industrial chip design leads to very large systems
of differential-algebraic equations (DAEs). The numerical solution of these
DAEs strongly depends on the so called index of the DAE. In general,
the higher the index of the DAE is, the more sensitive the numerical
solution will be to errors in the computation. So, it is advisable to use
mathematical models with small index or to reduce the index.
This paper presents an index reduction method that uses information
based on the topology of the circuit. In addition, we show that the
presented method retains structural properties of the DAE.
This work studies the stability and the stochastic properties of neural activity evoked by external
stimulation. The underlying model describes the spatiotemporal dynamics of neural populations
involving both synaptic delay and axonal transmission delay. We show, that the linear model
recasts to a set of affne delay differential equations in spatial Fourier space. Besides a stability
study for general kernels and general external stimulation, the power spectrum of evoked activity
is derived analytically in case of external Gaussian noise. Further applications to specific kernels
reveal critical
uctuations at Hopf- and Turing bifurcations and allow the numerical detection of
1/f fluctuations near the stability threshold.
During the last 15 years, there have been proposed many solution methods
for the important task of constructing periodic timetables for public transportation
companies. We first point out the importance of an objective function, where we
observe that in particular a linear objective function turns out to be a good compromise
between essential practical requirements and computational tractability. Then,
we enter into a detailed empirical analysis of various Mixed Integer Programming
procedures { such using nodes variables and such using arcs variables { genetic algorithms,
simulated annealing and constraint programming. To our knowledge, this
is the first comparison of five conceptually different solution approaches.
On rather small instances, an arc-based MIP formulation behaves best, when
refined by additional valid inequalities. On bigger instances, the solutions obtained
by a genetic algorithm are competitive to the solutions CPLEX was investigating
until it reached a time or memory limit. For Deutsche Bahn AG, the genetic algorithm
was most convincing on their various data sets, and it will become the first
automated timetable optimization software in use.
In the planning process of railway companies, we propose to integrate important
decisions of network planning, line planning, and vehicle scheduling into the task of periodic
timetabling. From such an integration, we expect to achieve an additional potential for
optimization.
Models for periodic timetabling are commonly based on the Periodic Event Scheduling
Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended
by only two features, namely a linear objective function and a symmetry requirement.
These extensions of the PESP do not really impose new types of constraints, because practitioners
have already required them even when only planning timetables autonomously without
interaction with other planning steps.
We derive a link between the short rate and a new index constructed in a multiasset
economy. This uses two structural assumptions: The volatility structure
of the assets is rigidly spherical , and the short rate function is homogeneous of
degree 0. We give clear motivations for the assumptions, and our main result is
economically intuitive and testable from observed data. A preliminary empirical
study illustrates how one can test such results.
In the case of the equidistant discretization of the Airy differential equation (\discrete
Airy equation") the exact solution can be found explicitly. This fact is used
to derive a discrete transparent boundary condition (TBC) for a Schroedinger
equation with linear varying potential, which can be used in \parabolic equation"
simulations in (underwater) acoustics and for radar propagation in the troposphere.
We propose different strategies for the discrete TBC and show an efficient implementation.
Finally a stability proof for the resulting scheme is given. A numerical
example in the application to underwater acoustics shows the superiority of the new
discrete TBC.
In a database of about 2000 approved drugs, represented by 105 structural conformers,
we have performed 2D comparisons (Tanimoto coefficients) and 3D superpositions. For one class of drugs the correlation
between structural resemblance and similar action was analysed in detail.
In general Tanimoto cofficients and 3D scores give similar results, but we
find that 2D similarity measures neglect important structural/funtional
features. Examples for both over- and underestimation of similarity by
2D metrics are discussed. The required additional effort for 3D superpositions
is assessed by implementation of a fast algorithm with a processing
time below 0:01 seconds and a more sophisticated approach (0:5 seconds
per superposition). According to the improvement of similarity detection
compared to 2D screening and the pleasant rapidity on a desktop PC,
full{atom 3D superposition will be an upcoming method of choice for
library prioritization or similarity screening approaches.
We investigate the numerical solution of large-scale Lyapunov equations
with the sign function method. Replacing the usual matrix inversion,
addition, and multiplication by formatted arithmetic for hierarchical
matrices, we obtain an implementation that has linear-polylogarithmic
complexity and memory requirements. The method is well suited for Lyapunov
operators arising from FEM and BEM approximations to elliptic
differential operators. With the sign function method it is possible to
obtain a low-rank approximation to a full-rank factor of the solution directly.
The task of computing such a factored solution arises, e.g., in
model reduction based on balanced truncation. The basis of our method
is a partitioned Newton iteration for computing the sign function of a
suitable matrix, where one part of the iteration uses formatted arithmetic
while the other part directly yields approximations to the full-rank factor
of the solution. We discuss some variations of our method and its application
to generalized Lyapunov equations. Numerical experiments show
that the method can be applied to problems of order up to O(105) on
desktop computers.
Branching Rules Revisited
(2004)
Mixed integer programs are commonly solved with linear programming
based branch-and-bound algorithms. The success of the algorithm
strongly depends on the strategy used to select the variable to
branch on.
We present a new generalization called reliability branching of today's
state-of-the-art strong branching and pseudocost branching branching
strategies for linear programming based branch-and-bound algorithms.
After reviewing commonly used branching strategies and performing
extensive computational studies we compare different parameter
settings and show the superiority of our proposed new strategy.
Effects of nonlocal feedback on traveling fronts in neural fields subject to transmission delay
(2004)
The work introduces a model for reciprocal connections in neural fields by a nonlocal feedback
mechanism, while the neural field exhibits nonlocal interactions and intra-areal transmission delays.
We study the speed of traveling fronts with respect to the transmission delay, the spatial feedback
range and the feedback delay for general axonal and feedback connectivity kernels. In addition, we
find a novel shape of traveling fronts due to the applied feedback and criteria for its occurence are
derived.
We develop a behavioural approach to linear, time-varying, differential algebraic systems.
The analysis is \almost everywhere" in the sense that the statements hold on R T, where
T is a discrete set. Controllability, observability and autonomy is introduced and related to
the behaviour of the system. Classical results on the behaviour of time-invariant systems are
studied in the context of time-varying systems.
Under high load, the automated dispatching of service vehicles for
the German Automobile Association (ADAC) must reoptimize a dispatch for
100{150 vehicles and 400 requests in about ten seconds to near optimality. In
the presence of service contractors, this can be achieved by the column generation
algorithm ZIBDIP. In metropolitan areas, however, service contractors
cannot be dispatched automatically because they may decline. The problem:
a model without contractors yields larger optimality gaps within ten seconds.
One way out are simplified reoptimization models. These compute a shortterm
dispatch containing only some of the requests: unknown future requests
will in
uence future service anyway. The simpler the models the better the
gaps, but also the larger the model error. What is more significant: reoptimization
gap or reoptimization model error? We answer this question in
simulations on real-world ADAC data: only the new models ShadowPrice and
ZIBDIPdummy can keep up with ZIBDIP.
We introduce a behavioural approach to linear, time-varying, differential algebraic
(descriptor) systems. The analysis is \almost global" in the sense that the analysis is
not restricted to an interval I R but is allowed for the \time axis" RnT, where T is
a discrete set of critical points, at which the solution may exhibit a finite escape time.
Controllable, observable, autonomous, and adjoint behaviour for linear time-varying
descriptor systems is introduced and characterized.
O&D revenue management (RM)
– either leg-based or PNR-based – has become
a standard in the airline industry. In this paper,
we present a new approach to O&D RM which
does not make any assumptions on demand distributions
or on the correlations of the booking
process. Protection levels are determined for all
origin destination itineraries, fare classes, points
of sale and data collection points (DCPs). This
approach to the seat inventory problem is modelled
as a multistage stochastic program, where
its stages correspond to the DCPs of the booking
horizon. The stochastic passenger demand
process is approximated by a scenario tree generated
from historical data by a recursive scenario
reduction procedure. The stochastic program
represents a specially structured large scale
LP that may be solved by standard LP software
(e.g. CPLEX). Preliminary numerical experience
is reported.
UMTS radio network evaluation and design are currently important issues for telecommunication operators.
We present a novel view on network evaluation. The recent dimension reduction approach is
generalized to an analytical approximation of the network's general performance based on average traffic.
The pivot is an average coupling matrix that captures the essential coverage and cell coupling properties of
the radio network. Based on this new evaluation method, we present new optimization methods, namely
a new optimization model based on designing the generalized average coupling matrix and an efficient
1-opt local search. We give preliminary computational results that show the potential of our methods on
realistic data.
This article describes Fortran 77 subroutines for computing eigenvalues and invariant subspaces
of Hamiltonian and skew-Hamiltonian matrices. The implemented algorithms are based on orthogonal
symplectic decompositions, implying numerical backward stability as well as symmetry
preservation for the computed eigenvalues. These algorithms are supplemented with balancing and
block algorithms, which can lead to considerable accuracy and performance improvements. As a
by-product, an efficient implementation for computing symplectic QR decompositions is provided.
We demonstrate the usefulness of the subroutines for several, practically relevant examples.
Stewart's recently introduced Krylov-Schur algorithm
is a modification of the implicitly restarted Arnoldi algorithm which
employs reordered Schur decompositions to perform restarts and de-
ations in a numerically reliable manner. This paper describes a variant
of the Krylov-Schur algorithm suitable for addressing eigenvalue
problems associated with products of large and sparse matrices. It
performs restarts and de
ations via reordered periodic Schur decompositions
and, by taking the product structure into account, it is
capable to achieve qualitatively better approximations to the eigenvalues
of small magnitude.
We discuss solvers for Sylvester, Lyapunov, and Stein equations that are available in the SLICOT
Library (Subroutine Library In COntrol Theory). These solvers offer improved efficiency, reliability,
and functionality compared to corresponding solvers in other computer-aided control system
design packages. The performance of the SLICOT solvers is compared with the corresponding
Matlab solvers. This note can also serve as a guide to the SLICOT and SLICOT-based Matlab
solvers for Linear Matrix Equations.
We shortly review the uncoupling-coupling method, a Markov chain
Monte Carlo based approach to compute statistical properties of systems like
medium-sized biomolecules. This technique has recently been proposed for the efficient computation of biomolecular conformations. One crucial step of UC is the
decomposition of reversible nearly uncoupled Markov chains into rapidly mixing
subchains. We show how the underlying scheme of uncoupling-coupling can also be
applied to stochastic differential equations where it can be translated into a domain
decomposition technique for partial differential equations.
This paper discusses some relationships between ILU factorization techniques and factored sparse approximate inverse techniques. While ILU factorizations compute approximate LU factors of the coefficient matrix A, approximate inverse techniques aim at building triangular matrices Z and W such that $W^\top AZ$ is approximately diagonal. The paper shows that certain forms of approximate inverse techniques amount to approximately inverting the triangular factors obtained from some variants of ILU factorization of the original matrix. A few useful applications of these relationships will be discussed.
Quality of Service (QoS) mechanisms in networks
supporting mobile Internet communications give
rise to new threats: these mechanisms could be abused
by malicious entities launching so-called Denial of Service
(DoS) attacks. If the network can not efficiently check the
credibility of a QoS-request during a handover process,
malicious entities could flood the network with bogus QoSrequests;
if the authentication check is performed by means
of an AAA protocol before the access network commits its
resources to the request, the authentication process may
not only introduce a notable latency to the handover process,
but also generate an extensive traffic which degrades
the signaling capacity in the network when there are a considerable
amount of malicious requests. In order to defend
against these kinds of attacks and meet the low-latency
micro-mobility handover requirement, we 1propose to have
a preliminary authentication check with a cookie-based
mechanism before processing the requests and performing
authentication and authorization. The performance evaluation
shows that the cookie-based mechanism is efficient in
dealing with the identified issues.
In this paper we present a new incomplete LU decomposition which is based on
an existing sparse direct solver. In contrast to many incomplete LU decompositions
this ILU incorporates information about the inverse factors L-1 and U-1 which
have direct in
uence on the dropping strategy. We demonstrate in several large scale
examples that this implementation constructs a robust preconditioner.
This article is concerned with the averaging principle and its extensions
for stochastic dynamical systems with fast and slow degrees of
freedom. It is demonstrated how the \conventional" averaging principle
results from asymptotic multiscale analysis, how one can construct
an indicator for its (in-)appropriateness, and how, if inappropriate, it
may be extended into an improved approximation. The conventional
scheme contains averages over the entire accessible state space of the
fast degrees of freedom and may thus fail if these fast degrees of freedom
exhibit long-term (auto-)correlations. In contrast, the improved
scheme combines several conditional averages with a Markov jump process
that is designed to represent the
ipping process between the
conditional averages and thus incorporates the important long-term
correlations. All important steps of the derivation are illustrated by
numerical experiments. Application to problems from molecular dynamics
is discussed.
We study the instability arising at the moving ridge of holes appearing
upon dewetting of thin polymer films on hydrophobized substrates, giving
special attention to the role of slippage at the liquid/solid for the appear-
ance of the instability. We compare here numerical results for a lubrication
model of the dewetting film assuming either a no-slip or a free slip condition
at the liquid/solid interface. Linear stability analysis reveals that in both
cases, perturbations of the ridge are amplied, but by orders of magnitude
more in the free slip case. Furthermore, the perturbations become much
more asymmetrical in the free slip case, while they develop symmetrical
patterns without slip. Additional computations that solve the lubrication
model for the full three-dimensional
ow confirm that these findings carry
over into the nonlinear regime.
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into a
hierarchical network? We propose a solution approach that is based on mixed-integer programming and
Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but
also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved
within 30 minutes to less than 1% off optimality.
This paper introduces arithmetic-like operations on matrix pencils. The pencil-arithmetic
operations extend elementary formulas for sums and products of rational numbers and
include the algebra of linear transformations as a special case. These operation give an
unusual perspective on a variety of pencil related computations. We derive generalizations of
monodromy matrices and the matrix exponential. A new algorithm for computing a pencilarithmetic
generalization of the matrix sign function does not use matrix inverses and gives
an empirically forward numerically stable algorithm for extracting deflating subspaces.
Motivation: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches.
Results: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search.
We consider a one–dimensional coupled stationary Schrödinger drift–diffusion model for quantum
semiconductor device simulations. The device domain is decomposed into a part with large quantum
effects (quantum zone) and a part where quantum effects are negligible (classical zone). We give
boundary conditions at the classic–quantum interface which are current preserving. Collisions within
the quantum zone are introduced via a Pauli master equation. To illustrate the validity we apply the
model to three resonant tunneling diodes
The present work introduces an analysis framework for the de-
tection of metastable signal segments in multivariate time series. It
is shown that in case of linear data these segments represent tran-
sient generalized synchronization, while metastable segments in circu-
lar data reflect transient mutual phase synchronization. We propose
a single segmentation approach for both types of data considering the
space-time structure of the data. Applications to both event-related
potentials and single evoked potentials obtained from an auditory odd-
ball experiment reveal the lack of the component P300 in an experi-
mental condition, indicates attention effects in component N100 and
shows dramatic latency jitters in single trials. A comparison of the
proposed method to a conventional index of mutual phase synchro-
nization demonstrates the superiority of considering space-time data
structures.
The line planning problem is one of the fundamental problems in strategic
planning of public and rail transport. It consists of finding lines
and corresponding frequencies in a public transport network such that
a given travel demand can be satisfied. There are (at least) two objectives.
The transport company wishes to minimize its operating cost;
the passengers request short travel times. We propose two new multicommodity
ow models for line planning. Their main features, in comparison
to existing models, are that the passenger paths can be freely
routed and that the lines are generated dynamically.
The weighted matching problem is to find a matching in a weighted graph
that has maximum weight. The fastest known algorithm for this problem has running time
O(nm +n2 log n). Many real world problems require graphs of such large size that this running
time is too costly. We present a linear time approximation algorithm for the weighted
matching problem with a performance ratio of 2
3 ???? ". This improves the previously best
performance ratio of 1
2 .
Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested [5][17]. Both these algorithms have a performance ratio of 1/2. In this paper we present a set of local improvement operations and prove that it guarantees a performance ratio of 2/3. We show that a maximal set of these local improvements can be found in linear time.
To see how these local improvements behave in practice we conduct an experimental comparison of four different approximation algorithms for calculating maximum weight matchings in weighted graphs. One of these algorithms is the commonly used Greedy algorithm which achieves a performance ratio of 1/2 but has O(m log n) runtime. The other three algorithms all have linear runtime. Two of them are the above mentioned 1/2 approximation algorithms. The third algorithm may have an arbitrarily bad performance ratio but in practice produces reasonably good results. We compare the quality of the algorithms on a test set of weighted graphs and study the improvement achieved by our local improvement operations. We also do a comparison of the runtimes of all algorithms.
We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259–269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.
We investigate the problem of colouring random graphs G ? G(n; p)
in polynomial expected time. For the case p ? 1.01/n, we present an algorithm
that finds an optimal colouring in linear expected time. For
p ?? ln6(n)/n, we give algorithms which approximate the chromatic
number within a factor of O(? np). We also obtain an O(?
np/ ln(np))-
approximation algorithm for the independence number. As an application,
we propose an algorithm for deciding satisfiability of random 2k-
SAT formulas (with sufficiently many clauses) in
polynomial expected time.
We investigate the problem of colouring random graphs G ? G(n, p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n.
We introduce a systematic approach to the problem of maximizing the robust
utility of the terminal wealth of an admissible strategy in a general complete market
model, where the robust utility functional is defined by a set Q of probability measures.
Our main result shows that this problem can be reduced to determining a “least favorable”
measure Q0 2 Q, which is universal in the sense that it does not depend on the
particular utility function. The robust problem is thus equivalent to a standard utility
maximization problem with respect to the “subjective” probability measure Q0. By using
the Huber-Strassen theorem from robust statistics, it is shown that Q0 always exists if Q
is the core of a 2-alternating upper probability. We also discuss the problem of robust
utility maximization with uncertain drift in a Black-Scholes market and the case of “weak
information” as studied by Baudoin (2002).
We discuss an efficient algorithm for optimal Hankel norm approximation of large-scale
systems and an implementation which allows to reduce models of order up to O(104) using
parallel computing techniques. The major computational tasks in this approach are the
computation of a minimal balanced realization, involving the solution of two Lyapunov
equations, and the additive decomposition of a transfer function via block diagonalization.
We will illustrate that these computational tasks can all be performed using iterative
schemes for the matrix sign function. Numerical experiments on a cluster of Linux PCs
show the efficiency of our methods.