A New Iterative Scheme for Solving the Semi Sylvester Equation ()
1. Introduction
We want to solve, using Galerkin projection method, the following semi Sylvester equation
(1)
where A, E, B and C are
,
,
and
matrices, respectively, and the unknown matrix
is
. Equation (1) has a unique solution if and only if
and
are regular matrix pairs with disjoint spectra, which will be assumed throughout this paper.
The semi Sylvester equations appear frequently in many areas of applied mathematics. We refer the reader to the elegant survey by Bhatia and Rosenthal [1] and references therein for a history of the equation and many interesting and important theoretical results. The semi Sylvester equations are important in a number of applications such as matrix eigen-decompositions [2,3], control theory [4,5], model reduction [6-8], numerical solution of matrix differential Riccati equations, and many more.
When the sizes of the coefficient matrices A and B are small, the popular and widely used numerical method is the Hessenberg-Schur algorithm [9]. For large and sparse matrices A and B, iterative schemes to solve the semi Sylvester equations such as those based on the matrix sign function or the Newton method are widely used [10-12]. During the last years, several projection methods based on Krylov subspace methods have also been proposed, see, e.g., [13-15] and the references therein. The main idea developed in these methods is to construct suitable bases of the Krylov subspace and projects the large problem into a smaller one. Naturally, a direct method such the one developed in [16] is used to solve the projected problem. The final step in the projection process consists in recovering the solution of the original problem from the solution of the smaller problem.
The semi Sylvesters Equation (1), in the special case, can be reduced to the following multiple linear systeam
(2)
In [17], Ton F. Chan and Michael K. Ng presented the Galerkin projection method for solving linear systems (2). In this paper, we convert the semi Sylvester Equation (1) to the multiple linear system. We present some propositions for applying the Galerkin projection method to solve the reduced semi Sylvester equation. For showing the efficiency of the new scheme, in point of view CPUtime and iteration number, we compare the new scheme with the
-GL-LSQR algorithm [18]. Note that the semi Sylvester Equation (1) is converted to standard Sylvester equation, when E be a identity matrix I.
The remainder of the paper is organized as follows. Section 2 is devoted to a short review of the Galerkin projection method. In Section 3, we show that how to apply the Galerkin projection method for solving the semi Sylvester Equation (1). Some numerical experiments and comparing the new scheme with the
-GLLSQR algorithm, is devoted in Section 4. Finally, we make some concluding remarks in Section 5.
2. The Short Summary of Galerkin Projection Method
In this section, we consider using conjugate gradient (CG) methods for solving multiple linear systems
, for
, where the coefficient matrices
and the right-hand side
are different in general. In particular, we focus on the seed projection method which generates a Krylov subspace from a set of direction vectors obtained by solving one of the systems, called the seed system, by the CG method and then projects the residuals of other systems onto the generated Krylov subspace to get the approximate solutions. The whole process is repeated until all the systems are solved. CG methods can be seen as iterative solution methods to solve a linear system of equations by minimizing an associated quadratic functional. For simplicity, we let
(3)
be the associated quadratic functional of the linear system
. The minimizer of
is the solution of the linear system
. The idea of the projection method is that for each restart, a seed system
is selected from the unsolved ones which are then solved by the CG method. An approximate solution
of the nonseed system
can be obtained by using search direction
generated from the ith iteration of the seed system. More precisely, given the ith iterate
of the nonseed system and the direction vector
, the approximate solution
is found by solving the following minimization problem
(4)
It is easy to check that the minimizer of (4) is attained at
(5)
where
(6)
After the seed system
is solved to the desired accuracy, a new seed system is selected and the whole procedure is repeated. We note from (6) that the matrix-vector multiplication
is required for each projection of the nonseed iteration. In general, the matrix-vector multiplication
cannot be computed cheaply. The cost of the method will be expensive in the general case where the matrices
and
are different.
In order to reduce the extra cost in projection method in the general case, we propose using the modified quadratic function
,

to compute the approximate solution of the nonseed system. Note that we have used
instead of
in the above definition. In this case, we determine the next iterate of the nonseed system by solving the following minimization problem:
(7)
The approximate solution
of the nonseed system
is given by
(8)
where
(9)
Now the projection process does not require the matrix-vector product involving the coefficient matrix
of the nonseed system. Therefore, the method does not increase the dominant cost (matrix-vector multiplies) of each CG iteration. Of course, unless
is close to
in some sense, we do not expect this method to work well because
is then far from the current
. So we have the following algorithm.
Algorithm 1 [17]: Preconditioned version of Projection Method
1. Set for
until all the systems are solved 2. Select the kth system as seed.
3. For
CG iteration,
4. For
unsolved systems 5. If
then perform usual CG steps 6. 
7. 
8. 
9. 
10. 
11. 
12. Else perform Galerkin projection 13. 
14. 
15. 
16. end if 17. end for 18. end for 19. end for
3. Solving the Semi Sylvester Equation
In this section, we focus on numerical solution of the semi Sylvester equations
(10)
where
,
,
,
and
is the solution matrix. The semi Sylvester equation (10) has a unique solution if and only if
and
are regular matrix pairs with disjoint spectra.
Now we want to apply Galerkin projection methods for solving the semi Sylvester Equation (10). Let B be symmetric matrix then semi Sylvester Equation (10) can be reduced to the following multiple linear systeams
(11)
where
,
and
.
By using the Schur decomposition, there is a unitary matrix
such that
(12)
where
is diagonal matrix and it’s digonal components are the eigenvalues of
. By substitution of (12) in (10), we have


By taking
and
, we obtain the following multiple linear systems
(13)
where
,
and
are
, i-th column of the matrix
and
-th column of the matrix
, respectively.
To use the Galerkin projection method for solving the multiple linear systeams (13), it is need the matrix
to be symmetric positive definite. So the following propositons are presented and their proof are clear.
Proposition 1: Let A and B are symmetric matrices and E is symmetric positive definite matrix and

where
be the eigenvalues of matrix
. Then
is symmetric positive difinite.
Proposition 2: Let A, B and E be symmetric positive difinite matrices and symmetric positive semi-difinite matrix, respectively. Then
are symmetric positive definite, where
be the eigenvalues of matrix
.
Note that the semi Sylvester Equation (1) is converted to standard Sylvester equation, when E be a identity matrix I. Now by using the assumptions of the above propositions, we can apply the previous algorithm to solve the semi Sylvester Equation (10).
4. Numerical Experiments
In this section, all the numerical experiments were computed in double precision with some MATLAB codes. For all the examples the initial guess
was taken to be zero matrix. We apply the new scheme for solving the standard Sylvester equation.
For obtaining the numerical solution of the Sylvester equation by using new scheme, we consider two examples. At the first example the dense coefficient matrix is as the form

where
is an
matrix of uniformly distributed random integers and
is an identity matrix. At the second example the coeffient matrix is

where
is
tridiagonal matrix. In both examples the matrix B is symmetric tridiagonal matrix with s size, as follows

Also the right-hand side matrix C in both examples is normalized random matrix. The
-GL-LSQR algorithm and Galerkin projection method are stopped when the residual norms of the first and second examples are less than 10−7 and 10−6, respectively.
In Table 1, we compare two
-GL-LSQR algorithm and Galerkin projection method for the first test example. We show that Galerkin projection method is better than
-GL-LSQR algorithm in point of view CPU-time and iteration number. In this table, (s)m is the sum of iterations when we apply the Galerkin projection method for solving s linear systems (2). In Table 2, we compare the
-GL-LSQR algorithm and Galerkin projection method for the second test example. We find that the
-GL-LSQR algorithm is better in point of veiw the iteration number and the new scheme is better in point of veiw the CPU-time. Finally, Figures 1 and 2 show that the efficientcy of the Galerkin projection method for solving the semi Sylvester equation. In both tables, the symbols cond and iter are the condition number of the coefficient matrix A and the iteration number of the methods, respectively.
5. Conclusion
We proposed a new scheme for solving the semi Syl-
Table 1. Numerical results of the new scheme and
-GLLSQR algorithm for the semi Sylvester equation with the first example.

Table 2. Numerical results of the new scheme and
-GLLSQR algorithm for the semi Sylvester equation with the second example.

Figure 1. Comparing the new scheme with the
-GLLSQR algorithm with n = 500, s = 5.

Figure 2. Comparing the new scheme with the
-GLLSQR algorithm with n = 4000 s = 4.
vester equation. By forcing some conditions on coefficent matrices A, B and E, We converted the semi Sylvester equation to s linear systems with different coefficent matrices and right-hands. Then we applied the Galerkin projection method for obtaining the numerrical solution, and we showed the efficiency of the new scheme. In Table 1, was shown that when the condition number of the coefficient matrix A is to be large then the new scheme is better then the
-GL-LSQR algorithm for solving the semi Sylvester equation. But in Table 2, the
-GL-LSQR algorithm is better than new scheme in point of view iteration number for sparse and wellconditioned matrix A.
6. Acknowledgements
The authors would like to thank the anonymouws referees for their helpful suggestions, which would greatly improve the article.