Structured mixed and componentwise condition numbers of some structured matrices

Structured matrices, such as Cauchy, Vandermonde, Toeplitz, Hankel, and circulant matrices, are considered in this paper. We apply a Kronecker product-based technique to deduce the structured mixed and componentwise condition numbers for the matrix inversion and for the corresponding linear systems.     

Quasi-integrals of even-dimensional linear differential systems with skew-symmetric coefficient matrices

For a linear nonstationary system with skew-symmetric continuously differentiable coefficient matrix of arbitrary even dimension, we construct its quasi-integrals and obtain effective coefficient estimates for their deviations from the corresponding integrals in the stationary case. For each trajectory of motion described by such a system and lying on the sphere of the corresponding radius, these estimates permit precisely indicating a domain on the sphere containing the trajectory on a nonsmall time interval. The estimates can also be used for expanding the multidimensional motion of a mechanical object into multicomponent elements of lower dimension.     

A method of congruent type for linear systems with conjugate-normal coefficient matrices

Minimal residual methods, such as MINRES and GMRES, are well-known iterative versions of direct procedures for reducing a matrix to special condensed forms. The method of reduction used in these procedures is a sequence of unitary similarity transformations, while the condensed form is a tridiagonal matrix (MINRES) or a Hessenberg matrix (GMRES). The algorithm CSYM proposed in the 1990s for solving systems with complex symmetric matrices was based on the tridiagonal reduction performed via unitary congruences rather than similarities. In this paper, we construct an extension of this algorithm to the entire class of conjugate-normal matrices. (Complex symmetric matrices are a part of this class.) Numerical results are presented. They show that, on many occasions, the proposed algorithm has a superior convergence rate compared to GMRES.     

On componentwise condition numbers for eigenvalue problems with structured matrices

We give explicit expressions for the componentwise condition number for eigenvalue problems with structured matrices. We will consider only linear structures and show a general result from which expressions for the condition numbers follow. We obtain explicit expressions for the following structures: Toeplitz and Hankel. Details for other linear structures should follow in a straightforward manner from our general result. Copyright © 2008 John Wiley & Sons, Ltd.     

Structured condition numbers and statistical condition estimation for the LDU factorization

In this article, we consider the structured condition numbers for LDU, factorization by using the modified matrix-vector approach and the differential calculus, which can be represented by sets of parameters. By setting the specific norms and weight parameters, we present the expressions of the structured normwise, mixed, componentwise condition numbers and the corresponding results for unstructured ones. In addition, we investigate the statistical estimation of condition numbers of LDU factorization using the probabilistic spectral norm estimator and the small-sample statistical condition estimation method, and devise three algorithms. Finally, we compare the structured condition numbers with the corresponding unstructured ones in numerical experiments.     

On nonautonomous linear systems of differential and difference equations with -symmetric coefficient matrices

Let denote the set of continuous n×n matrices on an interval . We say that is a nontrivial k-involution if where ζ=e^-2πi/k, d₀+d₁++d_k-1=n, and with . We say that is R-symmetric if R(t)A(t)R^-1(t)=A(t), , and we show that if A is R-symmetric then solving x^′=A(t)x or x^′=A(t)x+f(t) reduces to solving k independent d_ℓ×d_ℓ systems, 0ℓk-1. We consider the asymptotic behavior of the solutions in the case where . Finally, we sketch analogous results for linear systems of difference equations.     

Solution spaces of homogeneous linear difference systems with coefficient matrices from commutative groups

We analyse the solution spaces of limit periodic homogeneous linear difference systems, where the coefficient matrices of the considered systems are taken from a commutative group which does not need to be bounded. In particular, we study such systems whose fundamental matrices are not asymptotically almost periodic or which have solutions vanishing at infinity. We identify a simple condition on the matrix group which guarantees that the studied systems form a dense subset in the space of all considered systems. The obtained results improve previously known theorems about non-almost periodic and non-asymptotically almost periodic solutions. Note that the elements of the coefficient matrices are taken from an infinite field with an absolute value and that the corresponding almost periodic case is treated as well.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices

For a class of block two-by-two systems of linear equations with certain skew-Hamiltonian coefficient matrices, we construct additive block diagonal preconditioning matrices and discuss the eigen-properties of the corresponding preconditioned matrices. The additive block diagonal preconditioners can be employed to accelerate the convergence rates of Krylov subspace iteration methods such as MINRES and GMRES. Numerical experiments show that MINRES preconditioned by the exact and the inexact additive block diagonal preconditioners are effective, robust and scalable solvers for the block two-by-two linear systems arising from the Galerkin finite-element discretizations of a class of distributed control problems.     

On certain decompositions of complex inverse Toeplitz matrices and related fast algorithms for solving linear systems with Toeplitz coefficient matrices

Formulas for inverting nonsingular Toeplitz matrices with complex entries are derived. These formulas either refine known ones or are new. They make it possible to develop economical algorithms for calculating products of inverse Toeplitz matrices with vectors.     

Bounds for condition numbers of triangular and trapezoid matrices

Lower and upper bounds are determined for the conditioning of triangular and trapezoid matrices of full rank. These bounds can justify column pivoting in Gaussian elimination and in orthogonal elimination, or symmetrical pivoting in Cholesky factorization, or singular value decomposition instead of elimination.     

Once again on solving systems of linear equations whose coefficient matrices are low-rank perturbations of Hermitian matrices

MINRES-N is a minimal residual algorithm, originally developed by the authors for solving systems of linear equations with normal coefficient matrices whose spectra lie on algebraic curves of low degree. In a previous publication, the authors showed that a variant of MINRES-N, called MINRES-N2, is applicable to nonnormal matrices A satisfying the condition

On perturbation bounds of Kronecker product linear systems and their level-2 condition numbers

The classical perturbation theory of linear systems $\mathit{Ax}=b$ is extended to Kronecker product linear systems $(A\otimes B)x=d$. Upper bounds are derived for the normwise and componentwise condition number. The nearness to singularity and the sensitivity of the condition numbers are analyzed.     

Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.