Inst. Mathematik

267 Items

Recent Submissions
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. ...

Structured eigenvalue backward errors of matrix pencils and polynomials with palindromic structures

Bora, Shreemayee ; Karow, Michael ; Mehl, Christian ; Sharma, Punit (2015)

We derive formulas for the backward error of an approximate eigenvalue of a *-palindromic matrix polynomial with respect to *-palindromic perturbations. Such formulas are also obtained for complex T-palindromic pencils and quadratic polynomials. When the T-palindromic polynomial is real, then we derive the backward error of a real number considered as an approximate eigenvalue of the matrix pol...

Structured eigenvalue backward errors of matrix pencils and polynomials with Hermitian and related structures

Bora, Shreemayee ; Karow, Michael ; Mehl, Christian ; Sharma, Punit (2014-04-17)

We derive a formula for the backward error of a complex number λ when considered as an approximate eigenvalue of a Hermitian matrix pencil or polynomial with respect to Hermitian perturbations. The same are also obtained for approximate eigenvalues of matrix pencils and polynomials with related structures like skew-Hermitian, *-even, and *-odd. Numerical experiments suggest that in many cases t...

On a perturbation bound for invariant subspaces of matrices

Karow, Michael ; Kressner, Daniel (2014-05-13)

Given a nonsymmetric matrix A, we investigate the effect of perturbations on an invariant subspace of A. The result derived in this paper differs from Stewart's classical result and sometimes yields tighter bounds. Moreover, we provide norm estimates for the remainder terms in well-known perturbation expansions for invariant subspaces, eigenvectors, and eigenvalues.

Perturbation theory for Hamiltonian matrices and the distance to bounded-realness

Alam, Rafikul ; Bora, Shreemayee ; Karow, Michael ; Mehrmann, Volker ; Moro, Julio (2011-06-27)

Motivated by the analysis of passive control systems, we undertake a detailed perturbation analysis of Hamiltonian matrices that have eigenvalues on the imaginary axis. We construct minimal Hamiltonian perturbations that move and coalesce eigenvalues of opposite sign characteristic to form multiple eigenvalues with mixed sign characteristics, which are then moved from the imaginary axis to spec...

μ-values and spectral value sets for linear perturbation classes defined by a scalar product

Karow, Michael (2011-09-06)

We study the variation of the spectrum of matrices under perturbations which are self- or skew-adjoint with respect to a scalar product. Computable formulas are given for the associated μ-values. The results can be used to calculate spectral value sets for the perturbation classes under consideration. We discuss the special case of complex Hamiltonian perturbations of a Hamiltonian matrix in de...

Structured pseudospectra for small perturbations

Karow, Michael (2011-12-08)

In this paper we study the shape and growth of structured pseudospectra for small matrix perturbations of the form $A \leadsto A_\Delta=A+B\Delta C$, $\Delta \in \boldsymbol{\Delta}$, $\|\Delta\|\leq \delta$. It is shown that the properly scaled pseudospectra components converge to nontrivial limit sets as $\delta$ tends to 0. We discuss the relationship of these limit sets with $\mu$-values an...