@phdthesis{Martin1992, author = {Martin, Alexander}, title = {Packen von Steinerb{\"a}umen: Polyedrische Studien und Anwendung.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4894}, number = {TR-92-04}, year = {1992}, abstract = {Gegeben sei ein Graph \$G=(V,E)\$ mit positiven Kantenkapazit{\"a}ten \$c_e\$ und Knotenmengen \$T_1,\ldots,T_N\$. Das Steinerbaumpackungs-Problem besteht darin, Kantenmengen \$S_1,\ldots,S_N\$ zu finden, so da\ss\ jedes \$S_k\$ die Knoten aus \$T_k\$ verbindet und jede Kante \$e\$ in h{\"o}chstens \$c_e\$ Kantenmengen aus \$S_1,\ldots,S_N\$ vorkommt. Eine zul{\"a}ssige L{\"o}sung dieses Problems nennen wir eine Steinerbaumpackung. Ist zus{\"a}tzlich eine Gewichtung der Kanten gegeben und nach einer bez{\"u}glich dieser Gewichtung minimalen Steinerbaumpackung gesucht, so sprechen wir vom gewichteten Steinerbaumpackungs-Problem. Die Motivation zum Studium dieses Problems kommt aus dem Entwurf elektronischer Schaltungen. Ein dort auftretendes Teilproblem ist das sogenannte Verdrahtungsproblem, das im wesentlichen darin besteht, gegebene Punktmengen unter bestimmten Nebenbedingungen und Optimalit{\"a}tskriterien auf einer Grundfl{\"a}che zu verbinden. Wir studieren das Steinerbaumpackungs-Problem aus polyedrischer Sicht und definieren ein Polyeder, dessen Ecken genau den Steinerbaumpackungen entsprechen. Anschlie\ss end versuchen wir, dieses Polyeder durch gute'' beziehungsweise facetten-definierenden Ungleichungen zu beschreiben. Basierend auf diesen Ungleichungen entwickeln wir ein Schnittebenenverfahren. Die L{\"o}sung des Schnittebenenverfahrens liefert eine untere Schranke f{\"u}r die Optimall{\"o}sung und dient als Grundlage f{\"u}r die Entwicklung guter Primalheuristiken. Wir haben das von uns implementierte Schnittebenenverfahren an einem Spezialfall des Verdrahtungsproblems, dem sogenannten Switchbox-Verdrahtungsproblem, getestet und vielversprechende Ergebnisse erzielt.}, language = {de} } @misc{LeimkuhlerReich1992, author = {Leimkuhler, Benedict and Reich, Sebastian}, title = {The Numerical Solution of Constrained Hamiltonian Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-868}, number = {SC-92-16}, year = {1992}, abstract = {A Hamiltonian system subject to smooth constraints can typically be viewed as a Hamiltonian system on a manifold. Numerical computations, however, must be performed in \$ R^n\$. In this paper, canonical transformations from ``Hamiltonian differential--algebraic equations'' to ODEs in Euclidean space are considered. In \S2, canonical parameterizations or local charts are developed and it is shown how these can be computed in a practical framework. In \S3 we consider the construction of unconstrained Hamiltonian ODE systems in the space in which the constraint manifold is embedded which preserve the constraint manifold as an integral invariant and whose flow reduces to the flow of the constrained system along the manifold. It is shown that certain of these unconstrained Hamiltonian systems force Lyapunov stability of the constraint--invariants, while others lead to an unstable invariant. In \S4, we compare various projection techniques which might be incorporated to better insure preservation of the constraint--invariants in the context of numerical discretization. Numerical experiments illustrate the degree to which the constraint and symplectic invariants are maintained under discretization of various formulations. {\bf Keywords:} differential--algebraic equations, Hamiltonian systems, canonical discretization schemes. {\bf AMS(MOS):} subject classification 65L05.}, language = {en} } @misc{Moeller1992, author = {M{\"o}ller, H. Michael}, title = {On decomposing systems of polynomial equations with finitely many solutions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-851}, number = {SC-92-15}, year = {1992}, abstract = {This paper deals with systems of \$m\$ polynomial equations in \$n\$ unknown, which have only finitely many solutions. A method is presented which decomposes the solution set into finitely many subsets, each of them given by a system of type \begin{displaymath} f_1(x_1)=0, f_2(x_1,x_2)=0,...,f_n(x_1,...,x_n)=0. \end{displaymath} The main tools for the decomposition are from ideal theory and use symbolical manipulations. For the ideal generated by the polynomials which describe the solution set, a lexicographical Gr{\"o}bner basis is required. A particular element of this basis allows the decomposition of the solution set. A recursive application of these decomposition techniques gives finally the triangular subsystems. The algorithm gives even for non-finite solution sets often also usable decompositions. {\bf Keywords:} Algebraic variety decomposition, Gr{\"o}bner bases, systems of nonlinear equations.}, language = {en} } @misc{BornemannErdmannKornhuber1992, author = {Bornemann, Folkmar A. and Erdmann, Bodo and Kornhuber, Ralf}, title = {Adaptive Multilevel-Methods in 3-Space Dimensions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-843}, number = {SC-92-14}, year = {1992}, abstract = {We consider the approximate solution of selfadjoint elliptic problems in three space dimensions by piecewise linear finite elements with respect to a highly non-uniform tetrahedral mesh which is generated adaptively. The arising linear systems are solved iteratively by the conjugate gradient method provided with a multilevel preconditioner. Here, the accuracy of the iterative solution is coupled with the discretization error. as the performance of hierarchical bases preconditioners deteriorate in three space dimensions, the BPX preconditioner is used, taking special care of an efficient implementation. Reliable a-posteriori estimates for the discretization error are derived from a local comparison with the approximation resulting from piecewise quadratic elements. To illustrate the theoretical results, we consider a familiar model problem involving reentrant corners and a real-life problem arising from hyperthermia, a recent clinical method for cancer therapy.}, language = {en} } @misc{Gatermann1992, author = {Gatermann, Karin}, title = {Computation of Bifurcation Graphs.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-837}, number = {SC-92-13}, year = {1992}, abstract = {The numerical treatment of Equivariant parameter-dependent onlinear equation systems, and even more its automation requires the intensive use of group theory. This paper illustrates the group theoretic computations which are done in the preparation of the numerical computations. The bifurcation graph which gives the bifurcation subgroups is determined from the interrelationship of the irreducible representations of a group and its subgroups. The Jacobian is transformed to block diagonal structure using a modification of the transformation which transforms to block diagonal structure with respect to a supergroup. The principle of conjugacy is used everywhere to make symbolic and numerical computations even more efficient. Finally, when the symmetry reduced problems and blocks of Jacobian matrices are evaluated numerically, the fact that the given representation is a quasi-permutation representation is exploited automatically.}, language = {en} } @misc{OPUS4-982, title = {Jahresbericht 1991}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9825}, number = {1991}, year = {1992}, language = {de} } @misc{LubichNowakPoehleetal.1992, author = {Lubich, Christian and Nowak, Ulrich and P{\"o}hle, Uwe and Engstler, Ch.}, title = {MEXX - Numerical Software for the Integration of Constrained Mechanical Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-823}, number = {SC-92-12}, year = {1992}, abstract = {MEXX (short for MEXanical systems eXtrapolation integrator) is a Fortran code for time integration of constrained mechanical systems. MEXX is suited for direct integration of the equations of motion in descriptor form. It is based on extrapolation of a time stepping method that is explicit in the differential equations and linearly implicit in the nonlinear constraints. It only requires the solution of well--structured systems of linear equations which can be solved with a computational work growing linearly with the number of bodies, in the case of multibody systems with few closed kinematic loops. Position and velocity constraints are enforced throughout the integration interval, whereas acceleration constraints need not be formulated. MEXX has options for time--continuous solution representation (useful for graphics) and for the location of events such as impacts. The present article describes MEXX and its underlying concepts.}, language = {en} } @misc{Bixby1992, author = {Bixby, Robert E.}, title = {Das Implementieren des Simplex- Verfahrens: Die Startbasis.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-816}, number = {SC-92-11}, year = {1992}, abstract = {Dieses Paper enth{\"a}lt die ersten beiden Teile einer geplanten Serie von Aufs{\"a}tzen {\"u}ber die \$CPLEX^2\$-Implementierung des Simplex- Verfahrens. Der erste Teil ist eine Einf{\"u}hrung: er liefert eine kurze Beschreibung des Verfahrens f{\"u}r Probleme mit beschr{\"a}nkten Variablen, zusammen mit einer relativ ausf{\"u}hrlichen Diskussion der numerischen Eigenschaften der Netlib-Probleme. Diese Probleme bilden auch das Fundament der rechnerischen Untersuchungen in den folgenden Teilen. Der zweite Teil enth{\"a}lt die Hauptergebnisse dieses Papers, eine Beschreibung der Methode, die von CPLEX verwendet wird, um eine Startbasis zu konstruieren.}, language = {de} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Polyhedral Investigations.}, doi = {10.1007/BF02592085}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-786}, number = {SC-92-08}, year = {1992}, abstract = {Let \$G=(V,E)\$ be a graph and \$T\subseteq V\$ be a node set. We call an edge set \$S\$ a Steiner tree with respect to \$T\$ if \$S\$ connects all pairs of nodes in \$T\$. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph \$G=(V,E)\$ with edge weights \$w_e\$, edge capacities \$c_e, e \in E,\$ and node sets \$T_1,\ldots,T_N\$, find edge sets \$S_1,\ldots,S_N\$ such that each \$S_k\$ is a Steiner tree with respect to \$T_k\$, at most \$c_e\$ of these edge sets use edge \$e\$ for each \$e\in E\$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing Problem from a polyhedral point of view and define an appropriate polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch \& cut algorithm. This algorithm is described in our companion paper SC 92-09.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-792}, number = {SC-92-09}, year = {1992}, abstract = {In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems.}, language = {en} }