TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Tue, 30 May 2023 09:02:42 GMT2023-05-30T09:02:42Z50291- Computational error bounds for multiple or nearly multiple eigenvalueshttp://hdl.handle.net/11420/8828Title: Computational error bounds for multiple or nearly multiple eigenvalues
Authors: Rump, Siegfried M.
Abstract: In this paper bounds for clusters of eigenvalues of non-selfadjoint matrices are investigated. We describe a method for the computation of rigorous error bounds for multiple or nearly multiple eigenvalues, and for a basis of the corresponding invariant subspaces. The input matrix may be real or complex, dense or sparse. The method is based on a quadratically convergent Newton-like method; it includes the case of defective eigenvalues, uncertain input matrices and the generalized eigenvalue problem. Computational results show that verified bounds are still computed even if other eigenvalues or clusters are nearby the eigenvalues under consideration.
Thu, 15 Feb 2001 00:00:00 GMThttp://hdl.handle.net/11420/88282001-02-15T00:00:00Z
- On P-matriceshttp://hdl.handle.net/11420/8726Title: On P-matrices
Authors: Rump, Siegfried M.
Abstract: We present some necessary and sufficient conditions for a real matrix to be a P-matrix. They are based on the sign-real spectral radius and regularity of a certain interval matrix. We show that no minor can be left out when checking for P-property. Furthermore, a not necessarily exponential method for checking the P-property is given.
Thu, 10 Jan 2002 00:00:00 GMThttp://hdl.handle.net/11420/87262002-01-10T00:00:00Z
- Addendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107]http://hdl.handle.net/11420/5276Title: Addendum to “Estimates of the determinant of a perturbed identity matrix” [Linear Algebra Appl. 558 (2018) 101–107]
Authors: Rump, Siegfried M.; Batra, Prashant
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/52762019-01-01T00:00:00Z
- Perron-Frobenius theory for complex matriceshttp://hdl.handle.net/11420/8728Title: Perron-Frobenius theory for complex matrices
Authors: Rump, Siegfried M.
Abstract: The purpose of this paper is to present a unified Perron-Frobenius Theory for nonnegative, for real not necessarily nonnegative and for general complex matrices. The sign-real spectral radius was introduced for general real matrices. This quantity was shown to share certain properties with the Perron root of nonnegative matrices. In this paper we introduce the sign-complex spectral radius. Again, this quantity extends many properties of the Perron root of nonnegative matrices to general complex matrices. Various characterizations will be given, and many open problems remain.
Wed, 04 Dec 2002 00:00:00 GMThttp://hdl.handle.net/11420/87282002-12-04T00:00:00Z
- A matrix-decomposition theorem for GLn (K)http://hdl.handle.net/11420/8775Title: A matrix-decomposition theorem for GLn (K)
Authors: Bünger, Florian; Nielsen, Klaus
Abstract: Given an arbitrary commutative field K, n ∈ ℕ≥3 and two monic polynomials q and r over K of degree n - 1 and n such that q(0) ≠ 0 ≠ r(0). We prove that any non-scalar invertible n x n matrix M can be written as a product of two matrices A and B, where the minimum polynomial of A is divisible by q and B is cyclic with minimum polynomial r. This result yields that the Thompson conjecture is true for PSLn(F3), n ∈ ℕ≥3, and PSL2n+1(F2), n ∈ ℕ. If G is such a group, then G has a conjugacy class Ω such that G = Ω2. In particular each element of G is a commutator.
Wed, 01 Sep 1999 00:00:00 GMThttp://hdl.handle.net/11420/87751999-09-01T00:00:00Z
- Products of symmetries in unitary groupshttp://hdl.handle.net/11420/8776Title: Products of symmetries in unitary groups
Authors: Bünger, Florian; Knüppel, Frieder; Nielsen, Klaus
Abstract: Given a regular --hermitian form on a finite-dimensional vector space V over a commutative field K of characteristic ≠ 2 such that the norm on K is surjective onto the fixed field of - (this is true whenever K is finite). Call an element σ of the unitary group a symmetry if σ2 = 1 and the negative space of σ is 1-dimensional. If π is unitary and det π ∈ 1, -1, we prove that π is a product of symmetries (with a few exceptions when K = GF 9 and dim V = 2) and we find the minimal number of factors in such a product.
Tue, 15 Jul 1997 00:00:00 GMThttp://hdl.handle.net/11420/87761997-07-15T00:00:00Z
- Short biography of Shmuel Friedland for his special LAA volumehttp://hdl.handle.net/11420/7890Title: Short biography of Shmuel Friedland for his special LAA volume
Authors: Berman, Abraham; Krattenthaler, Christian; Rump, Siegfried M.; Spitkovsky, Ilya; Zhang, Fuzhen
Wed, 30 Sep 2009 00:00:00 GMThttp://hdl.handle.net/11420/78902009-09-30T00:00:00Z
- Quasiconvex relaxations based on interval arithmetichttp://hdl.handle.net/11420/8760Title: Quasiconvex relaxations based on interval arithmetic
Authors: Jansson, Christian
Abstract: Interval analysis provides a tool for (i) forward error analysis, (ii) estimating and controlling rounding and approximation errors automatically, and (iii) proving existence and uniqueness of solutions. In this context the terms self-validating methods, inclusion methods orverification methods are in use. In this paper, we present a new self-validating method for solving global constrained optimization problems. This method is based on the construction of quasiconvex lower bound and quasiconcave upper bound functions of a given function, the latter defined by an arithmetical expression. No further assumptions about the nonlinearities of the given function are necessary. These lower and upper bound functions are rigorous by using the tools of interval arithmetic. In its easiest form they are constructed by taking appropriate linear and/or quadratical estimators which yield quasiconvex/quasiconcave bound functions. We show how these bound functions can be used to define rigorous quasiconvex relaxations for constrained global optimization problems and nonlinear systems. These relaxations can be incorporated in a branch and bound framework yielding a self-validating method.
Thu, 15 Feb 2001 00:00:00 GMThttp://hdl.handle.net/11420/87602001-02-15T00:00:00Z
- On norms of principal submatriceshttp://hdl.handle.net/11420/9809Title: On norms of principal submatrices
Authors: Bünger, Florian; Lange, Marko; Rump, Siegfried M.
Abstract: Let a norm on the set Mn of real or complex n-by-n matrices be given. We investigate the question of finding the largest constants αn and βn such that for each A∈Mn the average of the norms of its (n−1)-by-(n−1) principal submatrices is at least αn times the norm of A, and such that the maximum of the norms of those principal submatrices is at least βn times the norm of A. For a variety of classical norms including induced ℓp-norms, weakly unitarily invariant norms, and entrywise norms we give lower and upper bounds for αn and βn. In several cases αn and βn are explicitly determined.
Thu, 01 Jul 2021 00:00:00 GMThttp://hdl.handle.net/11420/98092021-07-01T00:00:00Z
- Finite sections of band operators with slowly oscillating coefficientshttp://hdl.handle.net/11420/10580Title: Finite sections of band operators with slowly oscillating coefficients
Authors: Lindner, Marko; Rabinovich, Vladimir S.; Roch, Steffen
Abstract: The purpose of this note is to show that the finite section method for a band operator with slowly oscillating coefficients is stable if and only if the operator is invertible. This result generalizes the classical stability criterion for the finite section method for band Toeplitz operators (= the case of constant coefficients). © 2004 Elsevier Inc. All rights reserved.
Fri, 01 Oct 2004 00:00:00 GMThttp://hdl.handle.net/11420/105802004-10-01T00:00:00Z
- Block computation and representation of a sparse nullspace basis of a rectangular matrixhttp://hdl.handle.net/11420/10617Title: Block computation and representation of a sparse nullspace basis of a rectangular matrix
Authors: Le Borne, Sabine
Abstract: In this paper, we propose a new method to efficiently compute a representation of an orthogonal basis of the nullspace of a sparse matrix operator BT with B ∈ Rn × m, n > m. We assume that B has full rank, i.e., rank(B) = m. It is well-known that the last n - m columns of the orthogonal matrix Q in a QR factorization B = QR form such a desired null basis. The orthogonal matrix Q can be represented either explicitly as a matrix, or implicitly as a matrix H of Householder vectors. Typically, the matrix H represents the orthogonal factor much more compactly than Q. We will employ this observation to design an efficient block algorithm that computes a sparse representation of the nullspace basis in almost optimal complexity. This new algorithm may, e.g., be used to construct a null space basis of the discrete divergence operator in the finite element context, and we will provide numerical results for this particular application. © 2007 Elsevier Inc. All rights reserved.
Fri, 25 Jan 2008 00:00:00 GMThttp://hdl.handle.net/11420/106172008-01-25T00:00:00Z
- Estimates of the determinant of a perturbed identity matrixhttp://hdl.handle.net/11420/2643Title: Estimates of the determinant of a perturbed identity matrix
Authors: Rump, Siegfried M.
Abstract: Recently Brent et al. presented new estimates for the determinant of a real perturbation I+E of the identity matrix. They give a lower and an upper bound depending on the maximum absolute value of the diagonal and the off-diagonal elements of E, and show that either bound is sharp. Their bounds will always include 1, and the difference of the bounds is at least tr(E). In this note we present a lower and an upper bound depending on the trace and Frobenius norm ϵ:=‖E‖Fof the (real or complex) perturbation E, where the difference of the bounds is not larger than ϵ2+O(ϵ3) provided that ϵ<1. Moreover, we prove a bound on the relative error between det(I+E) and exp(tr(E)) of order ϵ2.
Sat, 01 Dec 2018 00:00:00 GMThttp://hdl.handle.net/11420/26432018-12-01T00:00:00Z
- A short note on the ratio between sign-real and sign-complex spectral radius of a real square matrixhttp://hdl.handle.net/11420/3852Title: A short note on the ratio between sign-real and sign-complex spectral radius of a real square matrix
Authors: Bünger, Florian
Abstract: For a real (n×n)-matrix A the sign-real and the sign-complex spectral radius – invented by Rump – are respectively defined as ρR(A):=max|λ|||Ax|=|λx|,λ∈R,x∈Rn{0,ρC(A):=max|λ|||Ax|=|λx|,λ∈C,x∈Cn{0. For n≥2 we prove ρR(A)≥ζn ρC(A) where the constant ζn:=[formula omitted] is best possible.
Fri, 15 Sep 2017 00:00:00 GMThttp://hdl.handle.net/11420/38522017-09-15T00:00:00Z
- Residual bounds for some or all singular valueshttp://hdl.handle.net/11420/3480Title: Residual bounds for some or all singular values
Authors: Lange, Marko
Abstract: For a given real or complex matrix we derive perturbation bounds for some or all singular values. The bounds are of the same quality as corresponding residual bounds for the Hermitian eigenvalue problem. They are suitable for numerical computation.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11420/34802015-01-01T00:00:00Z
- Multi-level substructuring combined with model order reduction methodshttp://hdl.handle.net/11420/3362Title: Multi-level substructuring combined with model order reduction methods
Authors: Blömeling, Frank
Abstract: In many fields of engineering problems linear time-invariant dynamical systems (LTI systems) play an outstanding role. They result for instance from discretizations of the unsteady heat equation and they are also used in optimal control problems. Often the order of LTI systems is a limiting factor, since it becomes easily very large. As a consequence these systems cannot be treated efficiently without model reduction algorithms. In this paper a new approach for the combination of model order reduction methods and recent multi-level substructuring (MLS) techniques is presented. Similar multi-level substructuring methods have already been applied successfully to huge eigenvalue problems up to several millions of degrees of freedom. However, the presented approach does not make use of a modal analysis like former algorithms. Instead the original system is decomposed in smaller LTI systems which are treated with recent model reduction methods. Furthermore, the error which is induced by this substructuring approach is analysed and numerical examples based on the Oberwolfach benchmark collection are given in this paper.
Fri, 16 Sep 2011 00:00:00 GMThttp://hdl.handle.net/11420/33622011-09-16T00:00:00Z
- Large-scale Tikhonov regularization via reduction by orthogonal projectionhttp://hdl.handle.net/11420/3378Title: Large-scale Tikhonov regularization via reduction by orthogonal projection
Authors: Lampe, Jörg; Reichel, Lothar; Voß, Heinrich
Abstract: This paper presents a new approach to computing an approximate solution of Tikhonov-regularized large-scale ill-posed least-squares problems with a general regularization matrix. The iterative method applies a sequence of projections onto generalized Krylov subspaces. A suitable value of the regularization parameter is determined by the discrepancy principle.
Fri, 23 Sep 2011 00:00:00 GMThttp://hdl.handle.net/11420/33782011-09-23T00:00:00Z
- Yet more elementary proofs that the determinant of a symplectic matrix is 1http://hdl.handle.net/11420/3836Title: Yet more elementary proofs that the determinant of a symplectic matrix is 1
Authors: Bünger, Florian; Rump, Siegfried M.
Abstract: It seems to be of recurring interest in the literature to give alternative proofs for the fact that the determinant of a symplectic matrix is one. We state four short and elementary proofs for symplectic matrices over general fields. Two of them seem to be new.
Tue, 15 Nov 2016 00:00:00 GMThttp://hdl.handle.net/11420/38362016-11-15T00:00:00Z
- Detecting hyperbolic and definite matrix polynomialshttp://hdl.handle.net/11420/3904Title: Detecting hyperbolic and definite matrix polynomials
Authors: Niendorf, Vasco; Voß, Heinrich
Abstract: Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach. © 2009 Elsevier Inc. All rights reserved.
Tue, 17 Nov 2009 00:00:00 GMThttp://hdl.handle.net/11420/39042009-11-17T00:00:00Z
- Entrywise lower and upper bounds for the Perron vectorhttp://hdl.handle.net/11420/13570Title: Entrywise lower and upper bounds for the Perron vector
Authors: Rump, Siegfried M.
Abstract: Let an irreducible nonnegative matrix A and a positive vector x be given. Assume αx≤Ax≤βx for some 0<α≤β∈R. Then, by Perron-Frobenius theory, α and β are lower and upper bounds for the Perron root of A. As for the Perron vector x⁎, only bounds for the ratio γ:=maxi,jxi⁎/xj⁎ are known, but no error bounds against some given vector x. In this note we close this gap. For a given positive vector x and provided that α and β as above are not too far apart, we prove entrywise lower and upper bounds of the relative error of x to the Perron vector of A.
Tue, 15 Nov 2022 00:00:00 GMThttp://hdl.handle.net/11420/135702022-11-15T00:00:00Z
- Bounds for the determinant by Gershgorin circleshttp://hdl.handle.net/11420/2326Title: Bounds for the determinant by Gershgorin circles
Authors: Rump, Siegfried M.
Abstract: Each connected component of the Gershgorin circles of a matrix contains exactly as many eigenvalues as circles are involved. Thus the power set product of all circles is an inclusion of the determinant if all circles are disjoint. We prove that statement to be true for real matrices, even if their circles overlap. © 2018 Elsevier Inc.
Fri, 15 Feb 2019 00:00:00 GMThttp://hdl.handle.net/11420/23262019-02-15T00:00:00Z
- Inverses, determinants, eigenvalues, and eigenvectors of real symmetric Toeplitz matrices with linearly increasing entrieshttp://hdl.handle.net/11420/7882Title: Inverses, determinants, eigenvalues, and eigenvectors of real symmetric Toeplitz matrices with linearly increasing entries
Authors: Bünger, Florian
Abstract: We explicitly determine the skew-symmetric eigenvectors and corresponding eigenvalues of the real symmetric Toeplitz matricesT=T(a,b,n):=( a+b|j-k|)1≤j,k≤n of order n≥3 where a, b ∈ ℝ, b ≠0. The matrix T is singular if and only if c := a/b = -n-1/2. In this case we also explicitly determine the symmetric eigenvectors and corresponding eigenvalues of T. If T is regular, we explicitly compute the inverse T- 1, the determinant det T, and the symmetric eigenvectors and corresponding eigenvalues of T are described in terms of the roots of the real self-inversive polynomial pn(δ;z):=(zn+1- δzn-δz+1)/(z+1) if n is even, and pn(δ; z):=zn+1-δzn-δz+1 if n is odd, δ:=1+2/(2c+n-1). © 2014 Elsevier Inc.
Thu, 07 Aug 2014 00:00:00 GMThttp://hdl.handle.net/11420/78822014-08-07T00:00:00Z
- The product of two quadratic matriceshttp://hdl.handle.net/11420/8761Title: The product of two quadratic matrices
Authors: Bünger, Florian; Knüppel, Frieder; Nielsen, Klaus
Abstract: Let p=(x-β)(x-β-1)∈K[x] where β2≠β-2 and let V be a finite-dimensional vector space over the field K. A linear mapping M:V→V is called quadratic if p(M)=0. We characterize products of two quadratic linear mappings. © 2001 Elsevier Science Inc.
Thu, 24 May 2001 00:00:00 GMThttp://hdl.handle.net/11420/87612001-05-24T00:00:00Z
- Self-validating methodshttp://hdl.handle.net/11420/9347Title: Self-validating methods
Authors: Rump, Siegfried M.
Abstract: We present some ideas on self-validating (SV) methods. This note is especially intended to give some background for the articles in this special volume of LAA. It is not intended to be a survey of the big variety of all possible aspects of SV methods but rather a summary of some basic concepts. Especially, some common misconceptions are mentioned and explored. © 2001 Elsevier Science Inc.
Thu, 15 Feb 2001 00:00:00 GMThttp://hdl.handle.net/11420/93472001-02-15T00:00:00Z
- Structured perturbations and symmetric matriceshttp://hdl.handle.net/11420/9440Title: Structured perturbations and symmetric matrices
Authors: Rump, Siegfried M.
Abstract: For a given n × n matrix the ratio between the componentwise distance to the nearest singular matrix and the inverse of the optimal Bauer-Skeel condition number cannot be larger than (3 + 2√2)n. In this note a symmetric matrix is presented where the described ratio is equal to n for the choice of most interest in numerical computation, for relative perturbations of the individual matrix components. It is shown that a symmetric linear system can be arbitrarily ill-conditioned, while any symmetric and entrywise relative perturbation of the matrix of less than 100% does not produce a singular matrix. That means that the inverse of the condition number and the distance to the nearest ill-posed problem can be arbitrarily far apart. Finally we prove that restricting structured perturbations to symmetric (entrywise) perturbations cannot change the condition number by more than a factor (3 + 2\√2)n. © 1998 Elsevier Science Inc. All rights reserved.
Tue, 20 Jun 2000 00:00:00 GMThttp://hdl.handle.net/11420/94402000-06-20T00:00:00Z
- Calculation of exact bounds for the solution set of linear interval systemshttp://hdl.handle.net/11420/9378Title: Calculation of exact bounds for the solution set of linear interval systems
Authors: Jansson, Christian
Abstract: This paper presents some topological and graph theoretical properties of the solution set of linear algebraic systems with interval coefficients. Based on these properties, we describe a method which, in a finite number of steps, either calculates exact bounds for each component of the solution set, or finds a singular matrix within the interval coefficients. The calculation of exact bounds of the solution set is known to be NP-hard. Our method needs p calls of a polynomial-time algorithm, where p is the number of nonempty intersections of the solution set with the orthants. Frequently, due to physical or economical requirements, many variables do not change the sign. In those cases p is small, and our method works efficiently. © Elsevier Science Inc., 1997.
Wed, 15 Jan 1997 00:00:00 GMThttp://hdl.handle.net/11420/93781997-01-15T00:00:00Z
- Theorems of Perron-Frobenius type for matrices without sign restrictionshttp://hdl.handle.net/11420/9392Title: Theorems of Perron-Frobenius type for matrices without sign restrictions
Authors: Rump, Siegfried M.
Abstract: The paper attempts to solve a problem which was called a "challenge for the future" in Linear Algebra Appl. We define and investigate a new quantity for real matrices, the sign-real spectral radius, and derive various characterizations, bounds, and properties of it. In certain aspects our quantity shows similar behavior to the Perron root of a nonnegative matrix. It is shown that our quantity also has intimate connections to the componentwise distance to the nearest singular matrix. Relations to the Perron root of the (entrywise) absolute value of the matrix and to the μ-number are given as well. © 1997 Elsevier Science Inc.
Sat, 15 Nov 1997 00:00:00 GMThttp://hdl.handle.net/11420/93921997-11-15T00:00:00Z
- The sign-real spectral radius and cycle productshttp://hdl.handle.net/11420/9441Title: The sign-real spectral radius and cycle products
Authors: Rump, Siegfried M.
Abstract: The extension of the Perron-Frobenius theory to real matrices without sign restriction uses the sign-real spectral radius as the generalization of the Perron root. The theory was used to extend and solve the conjecture in the affirmative that an ill-conditioned matrix is nearby a singular matrix also in the componentwise sense. The proof estimates the ratio between the sign-real spectral radius and the maximum geometric mean of a cycle product. In this note we discuss bounds for this ratio including a counterexample to a conjecture about this ratio. © 1998 Elsevier Science Inc. All rights reserved.
Mon, 02 Nov 1998 00:00:00 GMThttp://hdl.handle.net/11420/94411998-11-02T00:00:00Z
- Eigenvalues, pseudospectrum and structured perturbationshttp://hdl.handle.net/11420/8878Title: Eigenvalues, pseudospectrum and structured perturbations
Authors: Rump, Siegfried M.
Abstract: We investigate the behavior of eigenvalues under structured perturbations. We show that for many common structures such as (complex) symmetric, Toeplitz, symmetric Toeplitz, circulant and others the structured condition number is equal to the unstructured condition number for normwise perturbations, and prove similar results for real perturbations. An exception are complex skewsymmetric matrices. We also investigate componentwise complex and real perturbations. Here Hermitian and skew-Hermitian matrices are exceptional for real perturbations. Furthermore we characterize the structured (complex and real) pseudospectrum for a number of structures and show that often there is little or no significant difference to the usual, unstructured pseudospectrum. © 2004 Elsevier Inc. All rights reserved.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11420/88782006-01-01T00:00:00Z
- The main diagonal of a permutation matrixhttp://hdl.handle.net/11420/3166Title: The main diagonal of a permutation matrix
Authors: Lindner, Marko; Strang, Gilbert
Abstract: By counting 1's in the "right half" of 2w consecutive rows, we locate the main diagonal of any doubly infinite permutation matrix with bandwidth w. Then the matrix can be correctly centered and factored into block-diagonal permutation matrices. Part II of the paper discusses the same questions for the much larger class of band-dominated matrices. The main diagonal is determined by the Fredholm index of a singly infinite submatrix. Thus the main diagonal is determined "at infinity" in general, but from only 2w rows for banded permutations.
Thu, 03 May 2012 00:00:00 GMThttp://hdl.handle.net/11420/31662012-05-03T00:00:00Z