The block grade of a block Krylov space

The aim of the paper is to compile and compare basic theoretical facts on Krylov subspaces and block Krylov subspaces. Many Krylov (sub)space methods for solving a linear system Ax=b have the property that in exact computer arithmetic the true solution is found after ν iterations, where ν is the dimension of the largest Krylov subspace generated by A from r₀, the residual of the initial approximation x₀. This dimension is called the grade of r₀ with respect to A. Though the structure of block Krylov subspaces is more complicated than that of ordinary Krylov subspaces, we introduce here a block grade for which an analogous statement holds when block Krylov space methods are applied to linear systems with multiple, say s, right-hand sides. In this case, the s initial residuals are bundled into a matrix R₀ with s columns. The possibility of linear dependence among columns of the block Krylov matrix , which in practical algorithms calls for the deletion (or, deflation) of some columns, requires extra care. Relations between grade and block grade are also established, as well as relations to the corresponding notions of a minimal polynomial and its companion matrix.     

Recursion relations for the extended Krylov subspace method

The evaluation of matrix functions of the form f(A)v, where A is a large sparse or structured symmetric matrix, f is a nonlinear function, and v is a vector, is frequently subdivided into two steps: first an orthonormal basis of an extended Krylov subspace of fairly small dimension is determined, and then a projection onto this subspace is evaluated by a method designed for small problems. This paper derives short recursion relations for orthonormal bases of extended Krylov subspaces of the type K^m,mi+1(A)=span{A^-m+1v,…,A^-1v,v,Av,…,A^miv}, m=1,2,3,…, with i a positive integer, and describes applications to the evaluation of matrix functions and the computation of rational Gauss quadrature rules.     

On monotonicity of the Lanczos approximation to the matrix exponential

We prove strictly monotonic error decrease in the Euclidian norm of the Krylov subspace approximation of exp(A)φ, where φ and A are respectively a vector and a symmetric matrix. In addition, we show that the norm of the approximate solution grows strictly monotonically with the subspace dimension.     

Computing the nearest stable matrix pairs

In this paper, we study the nearest stable matrix pair problem: given a square matrix pair (E,A), minimize the Frobenius norm of (Δ_E,Δ_A) such that (E+Δ_E,A+Δ_A) is a stable matrix pair. We propose a reformulation of the problem with a simpler feasible set by introducing dissipative Hamiltonian matrix pairs: A matrix pair (E,A) is dissipative Hamiltonian if A=(J−R)Q with skew‐symmetric J, positive semidefinite R, and an invertible Q such that Q^TE is positive semidefinite. This reformulation has a convex feasible domain onto which it is easy to project. This allows us to employ a fast gradient method to obtain a nearby stable approximation of a given matrix pair.     

New perturbation bounds for the W-weighted Drazin inverse

The constructive perturbation bounds for the W-weighted Drazin inverse are derived by two approaches in this paper. One uses the matrixG = [(A+E)W]^l?(AW)^l, whereA, E ∈ C ^mxn ,W ∈ C ^nxm ,l = max Ind(AW), Ind[(A + E)W]. The other uses a technique proposed by G. Stewart and based on perturbation theory for invariant subspaces of a matrix. The new approaches to develop perturbation bounds for W-weighted Drazin inverse of a matrix extend the previous results in [19, 29, 31, 36, 42, 44]. Several examples which indicate the sharpness of the new perturbation bounds are presented.     

Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

Intersection problems and integral equivalence

Let A and B be matrices over a principal ideal domain, Π. Necessary conditions, involving the invariant factors of A and B, are given for B to be a submatrix of A or a principal submatrix of A.If a given nonnegative integral matrix, B, is the intersection matrix of a pair of families of subsets of an n-set, and n is the smallest integer for which this is true, we say that the content of B is n. In that event, B is a submatrix of K(n), the intersection matrix of all subsets of an n-set. More refined results are obtained in certain cases by considering S(n, k, l), the intersection matrix of the k-subsets of an n-set versus its l-subsets. The invariant factors of K(n) and S(n, k, l) are calculated and it is shown how this information may be used to get lower bounds for the content of B. In the more widely studied symmetric version of the content problem, B must be a principal submatrix of K(n) or, possibly, S(n, k) = S(n, k, k). In this case, the invariant factors of K(n) ? xI or S(n, k) ? xI also provide relevant information.     

Frames and bases in tensor products of Hilbert spaces and Hilbert <Emphasis Type="Italic">C</Emphasis>*-modules

In this article, we study tensor product of Hilbert C*-modules and Hilbert spaces. We show that if E is a Hilbert A-module and F is a Hilbert B-module, then tensor product of frames (orthonormal bases) for E and F produce frames (orthonormal bases) for Hilbert A ⊗ B-module E ⊗ F, and we get more results. For Hilbert spaces H and K, we study tensor product of frames of subspaces for H and K, tensor product of resolutions of the identities of H and K, and tensor product of frame representations for H and K.     

Closed operator ideals and interpolation

We consider closed operator ideals, which mean operator ideals A whose components A(E, F) are closed subspaces of the space L(E, F). Using interpolation techniques, we obtain general results on products of closed ideals. Furthermore, we investigate which closed ideals A possess the factorization property, i.e., each operator of A factors through a space with the related property “A”. Applications of these results yield the answer to some open questions in ideal theory.     

Maximal exponents of polyhedral cones (I)

Let K be a proper (i.e., closed, pointed, full convex) cone in Rn. An n×n matrix A is said to be K-primitive if there exists a positive integer k such that ; the least such k is referred to as the exponent of A and is denoted by γ(A). For a polyhedral cone K, the maximum value of γ(A), taken over all K-primitive matrices A, is called the exponent of K and is denoted by γ(K). It is proved that if K is an n-dimensional polyhedral cone with m extreme rays then for any K-primitive matrix A, γ(A)?(mA−1)(m−1)+1, where mA denotes the degree of the minimal polynomial of A, and the equality holds only if the digraph (E,P(A,K)) associated with A (as a cone-preserving map) is equal to the unique (up to isomorphism) usual digraph associated with an m×m primitive matrix whose exponent attains Wielandt's classical sharp bound. As a consequence, for any n-dimensional polyhedral cone K with m extreme rays, γ(K)?(n−1)(m−1)+1. Our work answers in the affirmative a conjecture posed by Steve Kirkland about an upper bound of γ(K) for a polyhedral cone K with a given number of extreme rays.     

Functions of a matrix and Krylov matrices

For a given nonderogatory matrix A, formulas are given for functions of A in terms of Krylov matrices of A. Relations between the coefficients of a polynomial of A and the generating vector of a Krylov matrix of A are provided. With the formulas, linear transformations between Krylov matrices and functions of A are introduced, and associated algebraic properties are derived. Hessenberg reduction forms are revisited equipped with appropriate inner products and related properties and matrix factorizations are given.     

Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components

Let A be a matrix with distinct eigenvalues and let w(A) be the distance from A to the set of defective matrices (using either the 2-norm or the Frobenius norm). Define Λ_?, the ?-pseudospectrum of A, to be the set of points in the complex plane which are eigenvalues of matrices A+E with ‖E‖<?, and let c(A) be the supremum of all ? with the property that Λ_? has n distinct components. Demmel and Wilkinson independently observed in the 1980s that w(A)?c(A), and equality was established for the 2-norm by Alam and Bora (2005). We give new results on the geometry of the pseudospectrum near points where first coalescence of the components occurs, characterizing such points as the lowest generalized saddle point of the smallest singular value of A-zI over z∈C. One consequence is that w(A)=c(A) for the Frobenius norm too, and another is the perhaps surprising result that the minimal distance is attained by a defective matrix in all cases. Our results suggest a new computational approach to approximating the nearest defective matrix by a variant of Newton’s method that is applicable to both generic and nongeneric cases. Construction of the nearest defective matrix involves some subtle numerical issues which we explain, and we present a simple backward error analysis showing that a certain singular vector residual measures how close the computed matrix is to a truly defective matrix. Finally, we present a result giving lower bounds on the angles of wedges contained in the pseudospectrum and emanating from generic coalescence points. Several conjectures and questions remain open.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Perturbation of invariant subspaces

We investigate by how much the invariant subspaces of a bounded linear operator on a Banach space change when the operator is slightly perturbed. If E and F are the spectral projector frames associated with A and A + H respectively, we answer the natural question about how far the two frames are in terms of the perturbation H and the separation of parts of the spectrum of the operator A. These results depend on how to measure the difference between the two frames and how to measure the separation between parts of the spectrum. These two measures are introduced and analysed.     

A numerical comparison of two minimal residual methods for linear polynomials in unitary matrices

Two minimal residual methods for solving linear systems of the form (αU + βI)x = b, where U is a unitary matrix, are compared numerically. The first method uses conventional Krylov subspaces, while the second involves generalized Krylov subspaces. Experiments favor the second method if |α| > |β|. Moreover, the greater the ratio |α|/|β|, the higher the superiority of the second method.     

Arbitrary perturbations of hermitian matrices

Kahan's results on the perturbation of the eigenvalues of a hermitian matrix A affected by an arbitrary perturbation A+X are improved in two ways. Better constants are given, and it is shown that the estimates do not depend on the size of A, but only on the size of the clusters of eigenvalues of A, relative to the euclidean norm of X.     

Intersection theory of algebraic obstructions

Let A be a noetherian commutative ring of dimension d and L be a rank one projectiveA-module. For 1≤r≤d, we define obstruction groups E^r(A,L). This extends the original definition due to Nori, in the case r=d. These groups would be called Euler class groups. In analogy to intersection theory in algebraic geometry, we define a product (intersection) E^r(A,A)×E^s(A,A)→E^r+s(A,A). For a projective A-module Q of rank n≤d, with an orientation , we define a Chern class like homomorphism

w(Q,χ):E^d−n(A,L^′)→E^d(A,LL^′),     

All spectral dominant norms are stable

A vector norm |·|on the space of n×n complex valued matrices is called stable if for some constant K&>0, not depending upon A or m, we have |A^m|?K|A|^m We show that such a norm is stable if and only if it dominates the spectralradius.     

On separable Lindenstrauss spaces

Isometric embeddings from l_∞ⁿin l_∞^{n + 1} can be described by a_i,n, i ? n, with $\text{∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{¦ a}{}_{\mathrm{i,n}}\text{¦ ? 1}$, such that e_i,n = e_{i,n + 1} + a_i,ne_{n + 1,n + 1}; i = 1,…, n; holds, where e_i,nand e_{i,n + 1} are the elements of the canonical unit vector bases of l_∞ⁿand l_∞^{n + 1}, respectively (negative signs may occur). We study the connections between a triangular substochastic matrix A, whose nth column consists of the elements a_i,n, i = 1,…, n, and the Banach space a_i,n, E_n ? E_{n + 1}, E_n ? l_∞ⁿ, where A determines the embeddings of the E_n. The class of these Banach spaces is the class of all separable Lindenstrauss spaces. Sufficient and necessary conditions are stated for a matrix A to represent c₀and c. Furthermore, we characterize the class of all extreme triangular substochastic matrices which represents C(K), where K is the Cantor set. We investigate how the special biface structure of the dual unit ball of X is reflected in the elements of a matrix A representing the separable Lindenstrauss space X. This is applicable to Gurarij spaces; we give a new proof for the maximality property of Gurarij spaces and show that they are isomorphic to A(S) where S is a Choquet simplex with dense extreme points.