FG Numerische Lineare Algebra

21 Items

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

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

Structured pseudospectra and the condition of a nonderogatory eigenvalue

Karow, Michael (2010-11-30)

Let $\lambda$ be a nonderogatory eigenvalue of $A\in\mathbb{C}^{n\times n}$ of algebraic multiplicity m. The sensitivity of $\lambda$ with respect to matrix perturbations of the form $A\leadsto A+\Delta$, $\Delta\in\boldsymbol{\Delta}$, is measured by the structured condition number $\kappa_{\boldsymbol{\Delta}}(A,\lambda)$. Here $\boldsymbol{\Delta}$ denotes the set of admissible perturbations...

Properties of worst-case GMRES

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

In the convergence analysis of the GMRES method for a given matrix $A$, one quantity of interest is the largest possible residual norm that can be attained, at a given iteration step $k$, over all unit norm initial vectors. This quantity is called the worst-case GMRES residual norm for $A$ and $k$. We show that the worst-case behavior of GMRES for the matrices $A$ and $A^T$ is the same, and we ...

A framework for deflated and augmented Krylov subspace methods

Gaul, André ; Gutknecht, Martin H. ; Liesen, Jörg ; Nabben, Reinhard (2013-05-14)

We consider deflation and augmentation techniques for accelerating the convergence of Krylov subspace methods for the solution of nonsingular linear algebraic systems. Despite some formal similarity, the two techniques are conceptually different from preconditioning. Deflation (in the sense the term is used here) “removes” certain parts from the operator making it singular, while augmentation a...