## Inst. Mathematik

273 Items

Recent Submissions
Stable marriage and roommates problems with restricted edges: complexity and approximability

Cseh, Ágnes ; Manlove, David F. (2016-04-16)

In the Stable Marriage and Roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the comp...

Tropicalization of del Pezzo surfaces

Ren, Qingchun ; Shaw, Kristin ; Sturmfels, Bernd (2016-03-30)

We determine the tropicalizations of very affine surfaces over a valued field that are obtained from del Pezzo surfaces of degree 5, 4 and 3 by removing their (-1)-curves. On these tropical surfaces, the boundary divisors are represented by trees at infinity. These trees are glued together according to the Petersen, Clebsch and Schläfli graphs, respectively. There are 27 trees on each tropical ...

Presolving techniques and linear relaxations for cumulative scheduling

Heinz, Stefan (2018)

In the mathematical optimization community the term scheduling usually describes the computation of a sequential plan for a set of jobs w.r.t. a set of side conditions such as precedence constraints and resource restrictions. Thereby, a certain objective should be fulfilled which can be for example to minimize the latest completion time of all jobs. The sequential plan can be an ordering of the...

On the dimension of posets with cover graphs of treewidth 2

Joret, Gwenael ; Micek, Piotr ; Trotter, William T. ; Wang, Ruidong ; Wiechert, Veit (2016-06-01)

In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimen...

Matchings with lower quotas: algorithms and complexity

Arulselvan, Ashwin ; Cseh, Ágnes ; Groß, Martin ; Manlove, David F. ; Matuschke, Jannik (2016-11-21)

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G=(A∪˙P,E) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either u...

Algorithm and mechanism design for congested networks

Bjelde, Antje (2018)

We are tackling the problem of reducing high congestion in networks from a mathematical point of view. First, we consider resource allocation problems where a set of commodities jointly uses a set of resources. The feasible allocations for each commodity are a commodity specific set of subsets of resources. The cost of each resource is determined by a polynomial function with maximum degree d...

P1-Nonconforming finite elements on triangulations into triangles and quadrilaterals

Altmann, Robert ; Carstensen, C. (2012)

The P1-nonconforming finite element is introduced for arbitrary triangulations into quadrilaterals and triangles of multiple connected Lipschitz domains. An explicit a priori analysis for the combination of the Park–Sheen and the Crouzeix–Raviart nonconforming finite element methods is given for second-order elliptic PDEs with inhomogeneous Dirichlet boundary conditions.

Matroidal subdivisions, Dressians and tropical Grassmannians

Schröter, Benjamin (2018)

In dieser Arbeit untersuchen wir verschiedene Aspekte von tropischen linearen Räumen und deren Modulräumen, den tropischen Grassmannschen und Dressschen. Tropische lineare Räume sind dual zu Matroidunterteilungen. Motiviert durch das Konzept der Splits, dem einfachsten Fall einer polytopalen Unterteilung, wird eine neue Klasse von Matroiden eingeführt, die mit Techniken der polyedrischen Geomet...

Computable convergence bounds for GMRES

Liesen, Jörg (2006)

The purpose of this paper is to derive new computable convergence bounds for GMRES. The new bounds depend on the initial guess and are thus conceptually different from standard "worst-case" bounds. Most importantly, approximations to the new bounds can be computed from information generated during the run of a certain GMRES implementation. The approximations allow predictions of how the algorit...

Least squares residuals and minimal residual methods

Liesen, Jörg ; Rozlozník, Miroslav ; Strakoš, Zdeněk (2012)

We study Krylov subspace methods for solving unsymmetric linear algebraic systems that minimize the norm of the residual at each step (minimal residual (MR) methods). MR methods are often formulated in terms of a sequence of least squares (LS) problems of increasing dimension. We present several basic identities and bounds for the LS residual. These results are interesting in the general contex...

Convergence of GMRES for tridiagonal Toeplitz matrices

Liesen, Jörg ; Strakoš, Zdeněk (2006)

We analyze the residuals of GMRES [Y. Saad and M. H. Schultz, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856--859], when the method is applied totridiagonal Toeplitz matrices. We first derive formulas for the residuals as well as their norms when GMRES is applied to scaled Jordan blocks. This problem has been studied previously by Ipsen [BIT, 40 (2000), pp. 524--535] and Eiermann and Ernst [P...

Orthogonal Hessenberg reduction and orthogonal Krylov subspace bases

Liesen, Jörg ; Saylor, Paul E. (2006)

We study necessary and sufficient conditions that a nonsingular matrix A can be B-orthogonally reduced to upper Hessenberg form with small bandwidth. By this we mean the existence of a decomposition AV=VH, where H is upper Hessenberg with few nonzero bands, and the columns of V are orthogonal in an inner product generated by a hermitian positive definite matrix B. The classical example for such...

Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems

Sturler, Eric de ; Liesen, Jörg (2006)

We study block-diagonal preconditioners and an efficient variant of constraint preconditioners for general two-by-two block linear systems with zero (2,2)-block. We derive block-diagonal preconditioners from a splitting of the (1,1)-block of the matrix. From the resulting preconditioned system we derive a smaller, so-called related system that yields the solution of the original problem. Solvin...

GMRES convergence analysis for a convection-diffusion model problem

Liesen, Jörg ; Strakoš, Zdenek (2006)

When GMRES [Y. Saad and M. H. Schultz, SIAM J. Sci. Statist. Comput.}, 7 (1986), pp. 856--869] is applied to streamline upwind Petrov--Galerkin (SUPG) discretized convection-diffusion problems, it typically exhibits an initial period of slow convergence followed by a faster decrease of the residual norm. Several approaches were made to understand this behavior. However, the existing analyses ar...

When is the adjoint of a matrix a low degree rational function in the matrix?

Liesen, Jörg (2007)

We show that the adjoint $A^+$ of a matrix A with respect to a given inner product is a rational function in A, if and only if A is normal with respect to the inner product. We consider such matrices and analyze the McMillan degrees of the rational functions r such that $A^+=r(A)$. We introduce the McMillan degree of A as the smallest among these degrees, characterize this degree in terms of th...

The Faber–Manteuffel theorem for linear operators

Faber, Vance ; Liesen, Jörg ; Tichý, Petr (2008)

A short recurrence for orthogonalizing Krylov subspace bases for a matrix A exists if and only if the adjoint of A is a low-degree polynomial in A (i.e., A is normal of low degree). In the area of iterative methods, this result is known as the Faber–Manteuffel theorem [V. Faber and T. Manteuffel, SIAM J. Numer. Anal., 21 (1984), pp. 352–362]. Motivated by the description by J. Liesen and Z. Str...

On optimal short recurrences for generating orthogonal Krylov subspace bases

Liesen, Jörg ; Strakoš, Zdenek (2008-08-05)

We analyze necessary and sufficient conditions on a nonsingular matrix A such that, for any initial vector $r_0$, an orthogonal basis of the Krylov subspaces ${\cal K}_n(A,r_0)$ is generated by a short recurrence. Orthogonality here is meant with respect to some unspecified positive definite inner product. This question is closely related to the question of existence of optimal Krylov subspace ...

On best approximations of polynomials in matrices in the matrix 2-norm

Liesen, Jörg ; Tichý, Petr (2009-07-30)

We show that certain matrix approximation problems in the matrix 2-norm have uniquely defined solutions, despite the lack of strict convexity of the matrix 2-norm. The problems we consider are generalizations of the ideal Arnoldi and ideal GMRES approximation problems introduced by Greenbaum and Trefethen [SIAM J. Sci. Comput., 15 (1994), pp. 359–368]. We also discuss general characterizations ...

Algebraic statistics of Gaussian mixtures

Améndola Cerón, Carlos Enrique (2017)

In this work we study the statistical models known as Gaussian mixtures from an algebraic point of view. First, we illustrate how algebraic techniques can be useful to address funda- mental questions on the shape of Gaussian mixture densities, namely the problem of determining the maximum number of modes a mixture of Gaussians can have, depending on the number of components and the dimensi...

Nonlinear eigenvalue problems with specified eigenvalues

Karow, Michael ; Kressner, Daniel ; Mengi, Emre (2014)

This work considers eigenvalue problems that are nonlinear in the eigenvalue parameter. Given such a nonlinear eigenvalue problem T, we are concerned with finding the minimal backward error such that T has a set of prescribed eigenvalues with prescribed algebraic multiplicities. We consider backward errors that only allow constant perturbations, which do not depend on the eigenvalue parameter. ...