Refine
Year of publication
Language
- English (1103)
- German (10)
- Multiple languages (1)
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.
Cyclic timetabling for public transportation companies is usually modeled by the periodic
event scheduling problem. To deduce a mixed-integer programming formulation, artificial integer
variables have to be introduced. There are many ways to define these integer variables.
We show that the minimal number of integer variables required to encode an instance is
achieved by introducing an integer variable for each element of some integral cycle basis. An
integral cycle basis consists of |A|-|V|+1 oriented cycles of a directed graph D = (V;A) that
enable any oriented cycle of the directed graph to be expressed as an integer linear combination.
The solution times for the originating application vary extremely with different integral
cycle bases. However, our computational studies show that the width of integral cycle bases
is a good empirical measure for the solution time of the MIP. Clearly, integral cycle bases
permit a much wider choice than the former standard approach, in which integer variables are
associated with the co-tree arcs of some spanning tree. Hence, to formulate better solvable
integer programs, we present algorithms that construct integral cycle bases of small width.
To that end, we investigate classes of directed cycle bases that are closely related to integral
cycle bases, namely (generalized) fundamental and undirected cycle bases. This gives rise to
both, a compact classification of directed cycle bases and notable reductions of running times
for cyclic timetabling.
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
For linear differential-algebraic equations (DAEs) with properly
stated leading terms the property of being numerically qualified
guarantees that qualitative properties of DAE solutions are reflected
by the numerical approximations. In this case BDF and Runge-Kutta
methods integrate the inherent regular ODE.
Here, we extend these results to general linear methods. We show
how general linear methods having stiff accuracy can be applied to
linear DAEs of index 1 and 2. In addition to the order conditions for
ODEs, general linear methods for DAEs have to satisfy additional
conditions.
As general linear methods require a starting procedure to start the
integration we put special emphasis on finding suitable starting
methods for index-2 DAEs.
Balancing a matrix by a simple and accurate similarity transformation can improve
the speed and accuracy of numerical methods for computing eigenvalues. We describe
balancing strategies for a large and sparse Hamiltonian matrix H. It is first shown how
to permute H to irreducible form while retaining its structure. This form can be used to
decompose the Hamiltonian eigenproblem into smaller-sized problems. Next, we discuss
the computation of a symplectic scaling matrix D so that the norm of D 1 HD is reduced.
The considered scaling algorithm is solely based on matrix-vector products and thus particularly
suitable if the elements of H are not explicitly given. The merits of balancing
for eigenvalue computations are illustrated by several practically relevant examples.
The periodic QR algorithm is a strongly backward stable method for computing the
eigenvalues of products of matrices, or equivalently for computing the eigenvalues of
block cyclic matrices. The main purpose of this paper is to show that this algorithm
is numerically equivalent to the standard QR algorithm. It will be demonstrated
how this connection may be used to develop a better understanding of the periodic
QR algorithm.
Two algorithms for the solution of discrete-time periodic Lyapunov
equations are presented. The first one is a variant of the
squared Smith iteration, which is solely based on matrix multiplications
and thus attractive to parallel computing environments.
The second algorithm is based on Krylov subspaces and
employs a recently developed variant of the block Arnoldi algorithm.
It is particularly suited for periodic Lyapunov equations
with large and sparse coefficient matrices. We also demonstrate
how these methods can be applied to balanced truncation model
reduction of periodic discrete-time systems and the solution of
periodic Riccati equations.
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.
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.