ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (1754)
- Doctoral Thesis (10)
- Habilitation (10)
- Article (5)
- In Proceedings (1)
Keywords
- integer programming (33)
- mixed integer programming (32)
- optimal control (29)
- KOBV (28)
- Kooperativer Bibliotheksverbund Berlin-Brandenburg (24)
- Bibliotheksverbund (20)
- Mixed Integer Programming (20)
- Integer Programming (17)
- line planning (14)
- mixed-integer programming (14)
Institute
- ZIB Allgemein (909)
- Mathematical Optimization (429)
- Numerical Mathematics (196)
- Visual and Data-centric Computing (92)
- Visual Data Analysis (88)
- Mathematical Optimization Methods (71)
- Mathematics of Transportation and Logistics (66)
- Computational Medicine (62)
- Digital Data and Information for Society, Science, and Culture (55)
- Applied Algorithmic Intelligence Methods (47)
SC-91-16
We consider the discretization of obstacle problems for the Laplacian by piecewise linear finite elements. Assuming that the discrete problems are reduced to a sequence of linear problems by suitable active set strategies, the linear problems are solved iteratively by preconditioned c-g iterations. The proposed preconditioners are treated theoretically as abstract additive Schwarz methods and are implemented as truncated hierarchical basis preconditioners. To allow for local mesh refinement we derive semi-local and local a posteriori error estimates, providing lower and upper estimates for the discretization error. The theoretical results are illustrated by numerical computations.
SC-91-15
We prove combinatorial formulas for the homotopy type of the union of the subspaces in an (affine, compactified affine, spherical or projective) subspace arrangement. From these formulas we derive results of Goresky & MacPherson on the homology of the arrangement and the cohomology of its complement. The union of an arrangement can be interpreted as the direct limit of a diagram of spaces over the intersection poset. A closely related space is obtained by taking the homotopy direct limit of this diagram. Our method consists in constructing a combinatorial model diagram over the same poset, whose homotopy limit can be compared to the original one by usual homotopy comparison results for diagrams of spaces.
SC-91-14
If $B$ is an arrangement of linear complex Hyperplanes in $C^d$, then the following can be constructed from knowledge of its intersection lattice: (a) the cohomology groups of the complement [Br], (b) the cohomology algebra of the complement [OS], (c) the fundamental group of the complement, if $d\le2$, (d) the singularity link up to homeomorphism, if $d\le3$, (e) the singularity link up to homotopy type [ZZ]. If $B'$ is, more generally, a 2-arrangement in $ R^{2d}$ (an arrangement of real subspaces of codimension 2 with even-dimensional intersections), then the intersection lattice still determines (a) the cohomology groups of the complement [GM] and (e) the homotopy type of the singularity link [ZZ]. We show, however, that for 2-arrangements the data (b), (c) and (d) are not determined by the intersection lattice. They require the knowledge of extra information on sign patterns, which can be computed as determinants of linear relations, or (equivalently) as linking coefficients in the sense of knot theory.
SC-91-13
The numerical solution of optimal control problems by indirect methods (such as multiple shooting or collocation) requires a considerable amount of analytic calculation to establish a numerically tractable system. These analytic calculations, though being rather tedious in realistic examples, are nowadays mostly still done by hand-and thus prone to calculation errors. The paper aims at automating this analytic processing to a reasonable extent by means of a modern symbolic manipulation language (here: REDUCE). In its present stage of development the package OCCAL (mnemotechnically for \underline{O}ptimal \underline{C}ontrol \underline{CAL}culator) permits an interactive use, covering tasks like automatic determination of control and, in case of a singular control, of its order. In simpler problems, the present version of OCCAL automatically produces the full subroutine input for a MULtiple shooting code (MULCON) with adaptive numerical CONtinuation. In more complicate problems where singular sub-arcs may occur or where the sequence of sub-arcs of the optimal trajectory is unclear OCCAL is a significant help in reducing analytic pre-processing. Numerical examples illustrate the performance of OCCAL/MULCON.
SC-91-12
An adaptive approach to the numerical solution of the wave propagation in integrated optics devices with 1D cross sections is described. First, Fresnel's approximation of the exact wave equation resulting from Maxwell's equations is considered. A criterion to estimate the validity of this approximation is derived. Fresnel's wave equation being formally equivalent to Schroedinger's equation uniquely defines an initial-boundary-value problem, which is solved numerically by a stepwise calculation of the propagating field. Discretization in longitudinal direction first with stepsize control leads to a stationary subproblem for the transversal field distribution, which is then handled by an adaptive finite element method. Thus full adaptivity of the algorithm is realized. The numerical examples are concentrated on taper structures playing an essential role in integrated optics devices for telecommunication systems.
SC-91-11
We study the space of all extensions of a real hyperplane arrangement by a new pseudo- hyperplane, and, more generally, of an oriented matroid by a new element. The question whether this space has the homotopy type of a sphere is a special case of the "Generalized Baues Problem" of Billera, Kapranov & Sturmfels, via the Bohne-Dress Theorem on zonotopal tilings. We prove that the extension space is spherical for the class of strongly euclidean oriented matroids. This class includes the alternating matroids and all oriented matroids of rank at most 3 or of corank at most 2. In general it is not even known whether the extension space is connected. We show that the subspace of realizable extensions is always connected but not necessarily spherical.
SC-91-10
We study the higher Bruhat orders $B(n,k)$ of Manin & Schechtman [MaS] and - characterize them in terms of inversion sets, - identify them with the posets $U(C^{n+1,r},n+1)$ of uniform extensions of the alternating oriented matroids $C^{n,r}$ for $r:=n-k$ (that is, with the extensions of a cyclic hyperplane arrangement by a new oriented pseudoplane), - show that $B(n,k)$ is a lattice for $k =1$ and for $r\le 3$, but not in general, - show that $B(n,k)$ is ordered by inclusion of inversion sets for $k=1$ and for $r\le 4$. However, $B(8,3)$ is not ordered by inclusion. This implies that the partial order $B_\subseteq (n,k)$ defined by inclusion of inversion sets differs from $B(n,k)$ in general. We show that the proper part of $B_\subseteq (n,k)$ is homotopy equivalent to $S^{r-2}$. Consequently, - $B(n,k)\simeq S^{r-2}$ for $k=1$ and for $r\le 4$. In contrast to this, we find that the uniform extension poset of an affine hyperplane arrangement is in general not graded and not a lattice even for $r=3$, and that the proper part is not always homotopy equivalent to $S^{r(M)-2}$.
SC-91-09
In this paper it is shown that for highly nonuniformly refined triangulations the condition number of the BPX preconditioner for elliptic finite element problems grows at most linearly in the depth of refinement. This is achieved by viewing the computational available version of the BPX preconditioner as an abstract additive Schwarz method with exact solvers. {\bf AMS CLASSIFICATION:} 65F10, 65F35, 65N20, 65N30.
SC-91-08
The deformation of a hexagonal lattice dome under an external load is an example of a parameter dependent system which is equivariant under the symmetry group of a regular hexagon. In this paper the mixed symbolic-numerical algorithm SYMCON is applied to analyze its steady state solutions automatically showing their different symmetry and stability properties.
SC-91-07
In this paper we introduce a discontinuous finite element method. In our approach, it is possible to combine the advantages of finite element and finite difference methods. The main ingredients are numerical flux approximation and local orthogonal basis functions. The scheme is defined on arbitrary triangulations and can be easily extended to nonlinear problems. Two different error indicators are derived. Especially the second one is closely connected to our approach and able to handle arbitrary variing flow directions. Numerical results are given for boundary value problems in two dimensions. They demonstrate the performance of the scheme, combined with the two error indicators. {\bf Key words:} neutron transport equation, discontinuous finite element, adaptive grid refinement. {\bf Subject classifications:} AMS(MOS) 65N30, 65M15.