A combination of Sylvester block sum and block matrix Kronecker map for explicit solutions of Sylvester system of matrix equations

In this paper, we consider an explicit solution of system of Sylvester matrix equations of the form A₁V₁ ? E₁V₁F₁ = B₁W₁ and A₂V₂ ? E₂V₂F₂ = B₂W₂ with F₁ and F₂ being arbitrary matrices, where V₁,W₁,V₂ and W₂ are the matrices to be determined. First, the definitions, of the matrix polynomial of block matrix, Sylvester sum, and Kronecker product of block matrices are defined. Some definitions, lemmas, and theorems that are needed to propose our method are stated and proved. Numerical test problems are solved to illustrate the suggested technique.     

On solutions of matrix equations and

With the help of the Kronecker map, a complete, general and explicit solution to the Yakubovich matrix equation V−AVF=BW, with F in an arbitrary form, is proposed. The solution is neatly expressed by the controllability matrix of the matrix pair (A,B), a symmetric operator matrix and an observability matrix. Some equivalent forms of this solution are also presented. Based on these results, explicit solutions to the so-called Kalman–Yakubovich equation and Stein equation are also established. In addition, based on the proposed solution of the Yakubovich matrix equation, a complete, general and explicit solution to the so-called Yakubovich-conjugate matrix is also established by means of real representation. Several equivalent forms are also provided. One of these solutions is neatly expressed by two controllability matrices, two observability matrices and a symmetric operator matrix.     

On the ADI method for Sylvester equations

This paper is concerned with the numerical solution of large scale Sylvester equations AX−XB=C, Lyapunov equations as a special case in particular included, with C having very small rank. For stable Lyapunov equations, Penzl (2000) [22] and Li and White (2002) [20] demonstrated that the so-called Cholesky factor ADI method with decent shift parameters can be very effective. In this paper we present a generalization of the Cholesky factor ADI method for Sylvester equations. An easily implementable extension of Penz’s shift strategy for the Lyapunov equation is presented for the current case. It is demonstrated that Galerkin projection via ADI subspaces often produces much more accurate solutions than ADI solutions.     

On equivalence and explicit solutions of a class of matrix equations

It is shown in this paper that three types of matrix equations AX−XF=BY,AX−EXF=BY and which have wide applications in control systems theory, are equivalent to the matrix equation with their coefficient matrices satisfying some relations. Based on right coprime factorization to , explicit solutions to the equation are proposed and thus explicit solutions to the former three types of matrix equations can be immediately established. With the special structure of the proposed solutions, necessary conditions to the nonsingularity of matrix X are also obtained. The proposed solutions give an ultimate and unified formula for the explicit solutions to these four types of linear matrix equations.     

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.     

Iterative orthogonal direction methods for Hermitian minimum norm solutions of two consistent matrix equations

The consistent conditions and the general expressions about the Hermitian solutions of the linear matrix equations AXB=C and (AX, XB)=(C, D) are studied in depth, where A, B, C and D are given matrices of suitable sizes. The Hermitian minimum F‐norm solutions are obtained for the matrix equations AXB=C and (AX, XB)=(C, D) by Moore–Penrose generalized inverse, respectively. For both matrix equations, we design iterative methods according to the fundamental idea of the classical conjugate direction method for the standard system of linear equations. Numerical results show that these iterative methods are feasible and effective in actual computations of the solutions of the above‐mentioned two matrix equations. Copyright © 2006 John Wiley & Sons, Ltd.     

矩阵方程A1Z+ZB1=C1的广义自反最佳逼近解的迭代算法

本文研究了Sylvester复矩阵方程A_1Z+ZB_1=c_1的广义自反最佳逼近解.利用复合最速下降法,提出了一种的迭代算法.不论矩阵方程A_1Z+ZB_1=C_1是否相容,对于任给初始广义自反矩阵Z_0,该算法都可以计算出其广义自反的最佳逼近解.最后,通过两个数值例子,验证了该算法的可行性.     

A Convergence Analysis of Gmres and Fom Methods for Sylvester Equations

We discuss convergence properties of the GMRES and FOM methods for solving large Sylvester equations of the form AX–XB=C. In particular we show the importance of the separation between the fields of values of A and B on the convergence behavior of GMRES. We also discuss the stagnation phenomenon in GMRES and its consequence on FOM. We generalize the issue of breakdown in the block-Arnoldi algorithm and explain its consequence on FOM and GMRES methods. Several numerical tests illustrate the theoretical results.     

Alternating Direction Method for a Class of Sylvester Matrix Equations with Linear Matrix Inequality Constraint

This paper introduces an alternating direction method of multipliers (ADMM) for finding solutions to a class of Sylvester matrix equation AXB = E subject to a linear matrix inequality constraint CXD≥G. Preliminary convergence properties of ADMM are presented. Numerical experiments are performed to illustrate the feasibility and effectiveness of ADMM. In addition, some numerical comparisons with a recent algorithm are also given.     

Generating orthogonal matrix polynomials satisfying second order differential equations from a trio of triangular matrices

The method developed in [A.J. Durán, F.A. Grünbaum, Orthogonal matrix polynomials satisfying second order differential equations, Int. Math. Res. Not. 10 (2004) 461–484] led us to consider matrix polynomials that are orthogonal with respect to weight matrices W(t) of the form , , and (1−t)^α(1+t)^βT(t)T^*(t), with T satisfying T^′=(2Bt+A)T, T(0)=I, T^′=(A+B/t)T, T(1)=I, and T^′(t)=(−A/(1−t)+B/(1+t))T, T(0)=I, respectively. Here A and B are in general two non-commuting matrices. We are interested in sequences of orthogonal polynomials (P_n)_n which also satisfy a second order differential equation with differential coefficients that are matrix polynomials F₂, F₁ and F₀ (independent of n) of degrees not bigger than 2, 1 and 0 respectively. To proceed further and find situations where these second order differential equations hold, we only dealt with the case when one of the matrices A or B vanishes.The purpose of this paper is to show a method which allows us to deal with the case when A, B and F₀ are simultaneously triangularizable (but without making any commutativity assumption).     

The quaternion matrix equation ΣA i XB i =E

LetH _F be the generalized quaternion division algebra over a fieldF with charF#2. In this paper, the adjoint matrix of anyn×n matrix overH _F [γ] is defined and its properties is discussed. By using the adjoint matrix and the method of representation matrix, this paper obtains several necessary and sufficient conditions for the existence of a solution or a unique solution to the matrix equation Σ _i=0 ^k A ⁱ XB _i =E overH _F , and gives some explicit formulas of solutions. Supported by the National Natural Science Foundation of China and Human     

LSQR iterative method for generalized coupled Sylvester matrix equations

An iterative method is proposed to solve generalized coupled Sylvester matrix equations, based on a matrix form of the least-squares QR-factorization (LSQR) algorithm. By this iterative method on the selection of special initial matrices, we can obtain the minimum Frobenius norm solutions or the minimum Frobenius norm least-squares solutions over some constrained matrices, such as symmetric, generalized bisymmetric and (R, S)-symmetric matrices. Meanwhile, the optimal approximate solutions to the given matrices can be derived by solving the corresponding new generalized coupled Sylvester matrix equations. Finally, numerical examples are given to illustrate the effectiveness of the present method.     

On matrix equations and

With the help of the concept of Kronecker map, an explicit solution for the matrix equation X−AXF=C is established. This solution is neatly expressed by a symmetric operator matrix, a controllability matrix and an observability matrix. In addition, the matrix equation is also studied. An explicit solution for this matrix equation is also proposed by means of the real representation of a complex matrix. This solution is neatly expressed by a symmetric operator matrix, two controllability matrices and two observability matrices.     

矩阵方程AXB+CX~TD=E自反最佳逼近解的迭代算法

本文研究了Sylvester矩阵方程AXB+CXTD=E自反(或反自反)最佳逼近解.利用所提出的共轭方向法的迭代算法,获得了一个结果:不论矩阵方程AXB+CXTD=E是否相容,对于任给初始自反(或反自反)矩阵X1,在有限迭代步内,该算法都能够计算出该矩阵方程的自反(或反自反)最佳逼近解.最后,三个数值例子验证了该算法是有效性的.     

Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum

We investigate simultaneous solutions of the matrix Sylvester equations A_iX-XB_i=C_i,i=1,2,…,k, where {A₁,…,A_k} and {B₁,…,B_k} are k-tuples of commuting matrices of order m×m and p×p, respectively. We show that the matrix Sylvester equations have a unique solution X for every compatible k-tuple of m×p matrices {C₁,…,C_k} if and only if the joint spectra σ(A₁,…,A_k) and σ(B₁,…,B_k) are disjoint. We discuss the connection between the simultaneous solutions of Sylvester equations and related questions about idempotent matrices separating disjoint subsets of the joint spectrum, spectral mapping for the differences of commuting k-tuples, and a characterization of the joint spectrum via simultaneous solutions of systems of linear equations.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

Function of a square matrix with repeated eigenvalues

An analytical function f(A) of an arbitrary n×n constant matrix A is determined and expressed by the “fundamental formula”, the linear combination of constituent matrices. The constituent matrices Z_kh, which depend on A but not on the function f(s), are computed from the given matrix A, that may have repeated eigenvalues. The associated companion matrix C and Jordan matrix J are then expressed when all the eigenvalues with multiplicities are known. Several other related matrices, such as Vandermonde matrix V, modal matrix W, Krylov matrix K and their inverses, are also derived and depicted as in a 2-D or 3-D mapping diagram. The constituent matrices Z_kh of A are thus obtained by these matrices through similarity matrix transformations. Alternatively, efficient and direct approaches for Z_kh can be found by the linear combination of matrices, that may be further simplified by writing them in “super column matrix” forms. Finally, a typical example is provided to show the merit of several approaches for the constituent matrices of a given matrix A.     

Maps on spaces of symmetric matrices preserving idempotence

Suppose F is an arbitrary field. Let |F| be the number of the elements of F. Let M_n(F) be the space of all n×n matrices over F, and let S_n(F) be the subset of M_n(F) consisting of all symmetric matrices. Let V{S_n(F),M_n(F)}, a map Φ:V→V is said to preserve idempotence if A-λB is idempotent if and only if Φ(A)-λΦ(B) is idempotent for any A,BV and λF. It is shown that: when the characteristic of F is not 2, |F|>3 and n4, Φ:S_n(F)→S_n(F) is a map preserving idempotence if and only if there exists an invertible matrix PM_n(F) such that Φ(A)=PAP^-1 for every AS_n(F) and P^tP=aI_n for some nonzero scalar a in F.