Similarity of block diagonal and block triangular matrices

It is shown that if a block triangular matrix is similar to its block diagonal part, then the similarity matrix can be chosen of the block triangular form. An analogous statement is proved for equivalent matrices. For the simplest case of 2×2 block matrices these results were obtained by W.Roth [1]. It is shown that all these results do not admit a generalization for the infinite dimensional case.     

Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations

New methods for computing eigenvectors of symmetric block tridiagonal matrices based on twisted block factorizations are explored. The relation of the block where two twisted factorizations meet to an eigenvector of the block tridiagonal matrix is reviewed. Based on this, several new algorithmic strategies for computing the eigenvector efficiently are motivated and designed. The underlying idea is to determine a good starting vector for an inverse iteration process from the twisted block factorizations such that a good eigenvector approximation can be computed with a single step of inverse iteration.     

Updating the QR decomposition of block tridiagonal and block Hessenberg matrices

We present an efficient block-wise update scheme for the QR decomposition of block tridiagonal and block Hessenberg matrices. For example, such matrices come up in generalizations of the Krylov space solvers MinRes, SymmLQ, GMRes, and QMR to block methods for linear systems of equations with multiple right-hand sides. In the non-block case it is very efficient (and, in fact, standard) to use Givens rotations for these QR decompositions. Normally, the same approach is also used with column-wise updates in the block case. However, we show that, even for small block sizes, block-wise updates using (in general, complex) Householder reflections instead of Givens rotations are far more efficient in this case, in particular if the unitary transformations that incorporate the reflections determined by a whole block are computed explicitly. Naturally, the bigger the block size the bigger the savings. We discuss the somewhat complicated algorithmic details of this block-wise update, and present numerical experiments on accuracy and timing for the various options (Givens vs. Householder, block-wise vs. column-wise update, explicit vs. implicit computation of unitary transformations). Our treatment allows variable block sizes and can be adapted to block Hessenberg matrices that do not have the special structure encountered in the above mentioned block Krylov space solvers.     

A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit

We consider the block orthogonal multi-matching pursuit(BOMMP) algorithm for the recovery of block sparse signals.A sharp condition is obtained for the exact reconstruction of block K-sparse signals via the BOMMP algorithm in the noiseless case,based on the block restricted isometry constant(block-RIC).Moreover,we show that the sharp condition combining with an extra condition on the minimum l_2 norm of nonzero blocks of block K-sparse signals is sufficient to ensure the BOMMP algorithm selects at least one true block index at each iteration until all true block indices are selected in the noisy case.The significance of the results we obtain in this paper lies in the fact that making explicit use of block sparsity of block sparse signals can achieve better recovery performance than ignoring the additional structure in the problem as being in the conventional sense.     

A block bidiangonal form for block companion matrices

The problem of the linear factorization of a polynomial matrix is related with a similarity condition linking the block companion matrix and a block upper bidiagonal matrix constructed from a chain of solvents. This result is the applied to the solution of differential and difference linear matrix equations.     

Optimal block diagonal scaling of block 2-cyclic matrices

We describe a class of optimal block diagonal scalings (preconditionings) of a symmetric positive definite block 2-cyclic matrix, generalizing a result of Forsythe and Strauss [1] for (point) 2-cyclic matrices.     

Simultaneous block triangularization and block diagonalization of sets of matrices

We consider the problem of simultaneously putting a set of square matrices into the same block upper triangular form with a similarity transformation, and obtain a result linking the size of the largest block to polynomial identities. This is used to yield a new proof of a theorem of Watters [20] which gives a necessary and sufficient condition for a set of matrices to be simultaneously, unitarily similar to block diagonal matrices with blocks of sizes one or two.     

Almost block independence

Summary A stationary finite state process is almost block independent, if long blocks are almost independent in the ¯d-sense. We show here that the concept of almost block independence is equivalent to very weak Bernoulli and to finitely determined, hence that the class of almost block independent processes coincides with the class of stationary codings of i.i.d. processes.Research supported in part by NSF grant MP-575-08324     

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.     

Factorization of block matrices

An LU-type factorization theorem due to Elsner and to Gohberg and Goldberg is generalized to block matrices. One form of the general factorization takes the form LMU, where L is block lower-triangular, U is block upper-triangular, and M is a subpermutation matrix each of whose blocks is diagonal. A factorization is also given where the middle term is a block diagonal subpermutation matrix, and the factorization is applied to Wiener-Hopf equations. The nonuniqueness of the middle term in the factorization is analyzed. A special factorization for self-adjoint block matrices is also obtained.     

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.     

Block Eigenvalues of block compound matrices

We obtain some results about the block eigenvalues of block compound matrices and additive block compound matrices. Assuming that a certain block Vandermonde matrix is nonsingular, we generalize known results for (scalar) compound and additive compound matrices.     

On computing of block ILU preconditioner for block tridiagonal systems

We present the recurrence formulas for computing the approximate inverse factors of tridiagonal and pentadiagonal matrices using bordering technique. Resulting algorithms are used to approximate the inverse of pivot blocks needed for constructing block ILU preconditioners for solving the block tridiagonal linear systems, arising from discretization of partial differential equations. Resulting preconditioners are suitable for parallel implementation. Comparison with other methods are also included.     

An adaptive block Lanczos algorithm

A generalization of the block Lanczos algorithm will be given, which allows the block size to be increased during the iteration process. In particular, the algorithm can be implemented with the block size chosen adaptively according to clustering of Ritz values. In this way, multiple and clustered eigenvalues can be found and the difficulty of choosing the block size is eased. Residual bounds for clustered eigenvalues are given. Numerical examples are presented to illustrate the adaptive algorithm.Research supported by a grant from Natural Sciences and Engineering Research Council of Canada.     

Matrices with block Toeplitz inverses

Conditions for a nonsingular matrix to have a block Toeplitz inverse are obtained. A simpler criterion for a block Toeplitz matrix to have a block Toeplitz inverse is also given. The results generalize those of Huang and Cline for Toeplitz matrices with scalar entries, for which alternative statements and proofs are also indicated.     

Loose block independence

A finite state stationary process is defined to be loosely block independent if long blocks are almost independent in the sense. We show that loose block independence is preserved under Kakutani equivalence and limits. We show directly that any loosely block independent process is the limit of Bernoulli processes and is a factor of a process which is Kakutani equivalent to a Bernoulli shift. The existing equivalence theory then yields that the loosely block independent processes are exactly the loosely Bernoulli (or finitely fixed) processes.     

Eigenvalue bounds for block preconditioned matrices

In the symmetric positive definite case, two-sided eigenvalue bounds for block Jacobi scaled matrices and upper eigenvalue bounds for matrices preconditioned with an incomplete block factorization are derived. A quantitative characterization of block matrix partitionings is also suggested, which can be used when analyzing various block preconditioning methods. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 5–41.     

Generalized qd algorithm for block band matrices

The generalized qd algorithm for block band matrices is an extension of the block qd algorithm applied to a block tridiagonal matrix. This algorithm is applied to a positive definite symmetric block band matrix. The result concerning the behavior of the eigenvalues of the first and the last diagonal block of the matrix containing the entries q ^(k) which was obtained in the tridiagonal case is still valid for positive definite symmetric block band matrices. The eigenvalues of the first block constitute strictly increasing sequences and those of the last block constitute strictly decreasing sequences. The theorem of convergence, given in Draux and Sadik (Appl Numer Math 60:1300?C1308, 2010), also remains valid in this more general case.     

More on block intersection polynomials and new applications to graphs and block designs

The concept of intersection numbers of order r for t-designs is generalized to graphs and to block designs which are not necessarily t-designs. These intersection numbers satisfy certain integer linear equations involving binomial coefficients, and information on the non-negative integer solutions to these equations can be obtained using the block intersection polynomials introduced by P.J. Cameron and the present author. The theory of block intersection polynomials is extended, and new applications of these polynomials to the studies of graphs and block designs are obtained. In particular, we obtain a new method of bounding the size of a clique in an edge-regular graph with given parameters, which can improve on the Hoffman bound when applicable, and a new method for studying the possibility of a graph with given vertex-degree sequence being an induced subgraph of a strongly regular graph with given parameters.