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 is concerned with transparent boundary conditions
(TBCs) for the time-dependent Schrödinger equation in one and two
dimensions. Discrete TBCs are introduced in the numerical simulations
of whole space problems in order to reduce the computational
domain to a finite region. Since the discrete TBC for the Schrödinger
equation includes a convolution w.r.t. time with a weakly decaying
kernel, its numerical evaluation becomes very costly for large-time
simulations.
As a remedy we construct approximate TBCs with a kernel having
the form of a finite sum-of-exponentials, which can be evaluated
in a very efficient recursion. We prove stability of the resulting initialboundary
value scheme, give error estimates for the considered approximation
of the boundary condition, and illustrate the efficiency of
the proposed method on several examples.
In this paper we introduce the notion of smoothed competitive analysis of online
algorithms. Smoothed analysis has been proposed by Spielman and Teng [22] to explain
the behaviour of algorithms that work well in practice while performing very poorly
from a worst case analysis point of view. We apply this notion to analyze the Multi-
Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of
jobs released over time when the processing time of a job is only known at time of
completion.
The initial processing times are integers in the range [1, 2K ]. We use a partial bit
randomization model, where the initial processing times are smoothened by changing
the k least significant bits under a quite general class of probability distributions. We
show that MLF admits a smoothed competitive ratio of O(max((2k /σ)3 , (2k /σ)2 2K−k )),
where σ denotes the standard deviation of the distribution. In particular, we obtain a
competitive ratio of O(2K−k ) if σ = Θ(2k ). We also prove an Ω(2K−k ) lower bound for
any deterministic algorithm that is run on processing times smoothened according to
the partial bit randomization model. For various other smoothening models, including
the additive symmetric smoothening model used by Spielman and Teng [22], we give a
higher lower bound of Ω(2K ).
A direct consequence of our result is also the first average case analysis of MLF. We
show a constant expected ratio of the total flow time of MLF to the optimum under
several distributions including the uniform distribution.
The paper presents a new affine invariant theory on asymptotic mesh
independence of Newton’s method for discretized nonlinear operator equations.
Compared to earlier attempts, the new approach is both much simpler
and more intuitive from the algorithmic point of view. The theory
is exemplified at collocation methods for ODE boundary value problems
and at finite element methods for elliptic PDE problems.
In this article, we use numerical simulation to investigate transient temperature
phenomena during sublimation growth of SiC single crytals via physical
vapor transport (also called the modified Lely method). We consider the evolution
of temperatures at the SiC source and at the SiC seed crystal, which
are highly relevant to the quality of the grown crystals, but inaccessible to
direct measurements. The simulations are based on a transient mathematical
model for the heat transport, including heat conduction, radiation, and radio
frequency (RF) induction heating. Varying the position of the induction coil
as well as the heating power, it is shown that the measurable temperature difference
between the bottom and the top of the growth apparatus can usually
not be used as a simple indicator for the respective temperature difference
between SiC source and seed. Moreover, it is shown that there can be a time
lack of 1.5 hours between the heating of the temperature measuring points
and the heating of the interior of the SiC source.
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly
at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n
be the density of the graph of Pd,n (i.e., the number of one-dimensional
faces of Pd,n divided by n ). Our main result is that, for any function 2
n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √
for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √
converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.
Abstract. Let P be a random 0/1-polytope in Rd with n(d) vertices, and denote by νr (P ) the
quotient of the number of faces of P with exactly r vertices and n(d) (the r-density of P ). For each
r
r ≥ 3, we establish the existence of a sharp threshold for the r-density and determine the values of
the threshold numbers τr such that, for all ε > 0,
E [νr (P )] =
1 − o(1)
o(1)
if n(d) ≤ 2(τr −ε)d for all d
if n(d) ≥ 2(τr +ε)d for all d
holds for the expected value of νr (P ). The threshold for r = 2 has already been determined in [8].
In particular, these results indicate that the high densities often encountered in polyhedral com-
binatorics (e.g., the cut-polytope has both 2- and 3-density equal to one) is due to the geometry of
0/1-polytopes rather than to the special combinatorics of the underlying problems.
We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
How to Whack Moles
(2004)
In the classical whack-a-mole game moles that pop up at
certain locations must be whacked by means of a hammer before they
go under ground again. The goal is to maximize the number of moles
caught. This problem can be formulated as an online optimization problem:
Requests (moles) appear over time at points in a metric space and
must be served (whacked) by a server (hammer) before their deadlines
(i.e., before they disappear). An online algorithm learns each request
only at its release time and must base its decisions on incomplete information.
We study the online whack-a-mole problem (wham) on the real
line and on the uniform metric space. While on the line no deterministic
algorithm can achieve a constant competitive ratio, we provide competitive
algorithms for the uniform metric space. Our online investigations
are complemented by complexity results for the offline problem.
In this paper we analyze decompositions of reversible nearly uncoupled
Markov chains into rapidly mixing subchains. We state upper
bounds on the 2nd eigenvalue for restriction and stochastic complementation
chains of reversible Markov chains, as well as a relation between
them. We illustrate the obtained bounds analytically for bunkbed
graphs, and furthermore apply them to restricted Markov chains that
arise when analyzing conformation dynamics of a small biomolecule.
Fractional multistep methods were introduced by C. Lubich for the quadrature of Abel integral operators and the solution of weakly singular Volterra integral equations of the first kind with exactly given right-hand sides. In the current paper, we consider the regularizing properties of these methods to solve the mentioned integral equations of the first kind for perturbed right-hand sides. Finally, numerical results are presented.
We present an algorithm that constructs parametrizations of boundary
and interface surfaces automatically. Starting with high-resolution triangulated
surfaces describing the computational domains, we iteratively
simplify the surfaces yielding a coarse approximation of the boundaries
with the same topological type. While simplifying we construct a function
that is defined on the coarse surface and whose image is the original
surface. This function allows access to the correct shape and surface normals
of the original surface as well as to any kind of data defined on it.
Such information can be used by geometric multigrid solvers doing adaptive
mesh refinement. Our algorithm runs stable on all types of input
surfaces, including those that describe domains consisting of several materials.
We have used our method with success in different fields and we
discuss examples from structural mechanics and biomechanics.
We use a numerical optimization method to determine the control parameters
frequency, power, and coil position for the radio frequency (RF) induction
heating of the growth apparatus during sublimation growth of SiC single crystals
via physical vapor transport (PVT) (also called the modified Lely method). The
control parameters are determined to minimize a functional, tuning the radial
temperature gradient on the single crystal surface as well as the vertical temperature
gradient between SiC source and seed, both being crucial for high-quality
growth. The optimization is subject to constraints with respect to a required
temperature difference between source and seed, a required temperature range at
the seed, and an upper bound for the temperature in the entire apparatus. The
numerical computations use a stationary mathematical model for the heat transport,
including heat conduction, radiation, and RF heating to solve the forward
problem, and a Nelder-Mead method for optimization. A minimal radial temperature
gradient is found to coincide with a minimal temperature at the single
crystal surface, and a maximal temperature gradient between source and seed is
found to coincide with a low coil position.
The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.
Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable.
Relaying - allowing multiple wireless hops - is a protocol extension
for cellular networks conceived to improve data throughput. Its benefits have only
been quantfied for small example networks. For assessing its general potential,
we define a complex resource allocation/scheduling problem. Several mathematical
models are presented for this problem; while a time-expanded MIP approach turns
out intractable, a sophisticated column generation scheme leads to good computational
results. We thereby show that for selected cases relaying can increase data
throughput by 30% on the average.
The key to molecular conformation dynamics is the direct identification of metastable conformations, which are almost invariant sets of molecular dynamical systems. Once some reversible Markov operator has been discretized, a generalized symmetric stochastic matrix arises. This matrix can be treated by Perron cluster analysis, a rather recent method involving a Perron cluster eigenproblem. The paper presents an improved Perron cluster analysis algorithm, which is more robust than earlier suggestions. Numerical examples are included.