1 Introduction

Given matrices \(A \in \mathbb {C}^{m\times m}\), \(B\in \mathbb {C}^{n\times n}\) and \(C \in \mathbb {C}^{m\times n}\), we will focus on the problem of solving the matrix equation

$$\begin{aligned} A X + X B = C \end{aligned}$$
(1.1)

in the variable \(X\in \mathbb {C}^{m\times n}\), which is called a continuous Sylvester equation. In the special case \(B = A^{H}\) and \(C = C^{H}\), where \(K^{H}\) denotes the conjugate transpose of K, the continuous Sylvester equation (1.1) reduces to the Lyapunov equation. It is well-known that this equation has a unique solution for X if and only if A and \(-B\) do not have common eigenvalues (see, e.g., Horn and Johnson 1991; Lancaster and Tismenetsky 1985).

Throughout this paper, we will assume that A and B in (1.1) are positive definite and positive semi-definite, respectively, or vice versa. Recall the general (weaker) definition of positive (semi-)definiteness, which says that a matrix \(K\in \mathbb {C}^{n\times n}\) is said to be positive (semi-)definite if its Hermitian part \(\frac{1}{2}(K+K^{H})\) is positive (semi-)definite. In general, this condition implies that the real part of \(\varvec{z}^HK\varvec{z}\) is positive (non-negative), for all non-zero vectors \(\varvec{z}\in \mathbb {C}^n\).

A Sylvester equation, in general, and a Lyapunov equation, in particular, are formulated in various applications. These arise in systems theory and control, matrix eigen-decompositions, model reduction, numerical solution of matrix differential Riccati equations, image processing, among many others. The importance of these applications motivated the extensive theoretical study of Sylvester equations along with the development of practical algorithms to compute approximate solutions; see, e.g., (Benner et al. 2009; Kürschner et al. 2014; Li et al. 2018; Liu et al. 2020; Smith 1968; Simoncini 2016; Tian et al. 2020; Wachspress 1988; Xiong and Lam 2006) and a large literature therein.

A possible approach to deal with the Sylvester equation (1.1) consists in vectorizing the unknown matrix X and translating the matrix equation into a linear system \(\mathscr {A} \textbf{x} = \textbf{c}\), where \(\textbf{x}\) and \(\textbf{c}\) are the column-stacking vectors of the matrices X and C, respectively, and \(\mathscr {A}\) is the Kronecker sum of the matrices A and \(B^{T}\), that is, \(\mathscr {A}= I_{m} \otimes A + B^{T} \otimes I_{n}\), with symbol \(\otimes \) denoting the standard Kronecker product. Either direct or iterative methods can be applied to solve this linear system. Another approach is to treat the Sylvester equation (1.1) in its original form using an iterative method directly applied to the matrices A, B and C.

When matrices A and B are large, the dimension of the coefficient matrix \( \mathscr {A}\) in the linear system \(\mathscr {A} \textbf{x} = \textbf{c}\) will be considerably larger and, in general, data storage and computational time become difficult issues. For this reason, the first approach is mainly used in problems of small or medium dimension.

Following the second approach mentioned above, the Alternating Direction Implicit (ADI) method is a popular two-step iterative procedure to obtain a solution to the Sylvester equation (1.1). In this paper we will consider ADI-like methods which, in fact, are analogues to the classical ADI iteration method introduced by Peaceman and Rachford in the context of solving partial differential equations, see (Peaceman and Rachford 1955; Simoncini 2016). A variant of ADI, called factored ADI, was formulated to construct the solution X in factored form, see (Benner et al. 2009; Li and White 2002). The effectiveness of factored ADI depends on whether X is well-approximated by a low rank matrix. This is known to be true under various assumptions about A and B.

In the last two decades, the development of iterative methods based on the concept of matrix splitting have attracted several scholars. In particular, the widely known HSS iteration method proposed in Bai et al. (2003) for solving positive definite, non-Hermitian linear systems, makes use of the Hermitian and skew-Hermitian splitting of the coefficient matrix and it is a resource that motivated several HSS-type iteration methods for solving linear systems, see, e.g., (Bai et al. 2007, 2006, 2007; Benzi 2009; Liu et al. 2018). In Bai (2011), for the first time, a variant of the HSS iteration method, which is an alternating direction implicit method in the spirit analogous to the ADI iteration method, was applied to solve the Sylvester equation (1.1). Numerous other efficient and robust algorithms were proposed in the same spirit, see, e.g., (Li and He 2022; Li et al. 2018; Liu et al. 2022; Wang et al. 2013; Zheng and Ma 2014).

Sylvester equations can also be solved using direct methods like Bartels-Stewart and Hessenberg-Schur methods, see (Bartels and Stewart 1972; Golub et al. 1979). The Bartels-Stewart method is based on the reduction of the matrices A and B to real Schur form (quasi-triangular form) using the QR algorithm for eigenvalues, followed by the use of direct methods to solve several linear systems for the columns of X. In the Hessenberg-Schur method the matrix A is reduced to Hessenberg form and only matrix B is decomposed into the quasi-triangular Shur form. This method is faster than the Bartels-Stewart method. These direct methods are \(\mathcal{{O}}(m^3+n^3)\) and therefore it is only beneficial to use ADI when matrix–vector multiplication and linear solvers involving A and B can be applied cheaply.

In some particular cases (when A or B is invertible), the Sylvester equation may be rewritten into a Stein matrix equation, after a suitable transformation, e.g., the Caley transformation, \( X=\widehat{A}XB+\widehat{C}, \) with \(\widehat{A}=-A^{-1}\), \(\widehat{C}=A^{-1}C\). An extensive amount of iterative methods based on the Smith method were studied and developed for solving the Stein matrix equation in recent years, like (rational) Krylov methods (see Li et al. 2013; Sadkane 2012; Zhou et al. 2009). Despite the lack of a rigorous error analysis, the Smith iteration exhibits very good numerical and computational properties and, when the same shift parameter is used at every iteration, it is equivalent to the ADI iteration.

We propose two relaxation strategies to the classical ADI iterative scheme - an extrapolated variant (EADI) and a block successive overrelaxation variant (block SOR-ADI). These are not strategies for solving inexactly the arising linear systems, but strategies that include in each iteration the usage of a new parameter \(\omega \) to improve the approximation obtained and thus to accelerate the convergence rate. We based our work in the results presented in Liu et al. (2020).

The new schemes EADI and block SOR-ADI are described in Sections 3 and 4, respectively, after a brief summary of the ADI iteration scheme and some of its convergence properties in Sect. 2. Our numerical experiments, shown in Section 5, suggest that these new schemes can increase the convergence rate of the ADI iterative method and thus be considered attractive solvers.

2 ADI iteration

The method of alternating directions (ADI) is described below. It is a two-step iteration process that alternately updates the column and row spaces of an approximate solution to the Sylvester equation (1.1). An initial guess \(X^{(0)}\) is required, as well as shift parameters \(\alpha \) and \(\beta \). An intimate connection between this iterative process and Smith’s algorithm (Smith 1968) was mentioned in Wachspress (1988).

ADI iteration. Given an initial approximation \(X^{(0)}\) and two positive constants \(\alpha \) and \(\beta \), repeat the steps

$$\begin{aligned} {\left\{ \begin{array}{ll} (\alpha I + A) X^{(k+\frac{1}{2})} = X^{(k)} (\alpha I - B) + C \qquad \quad \big (\text {solve for }X^{(k+\frac{1}{2})}\big )\\ X^{(k+1)} (\beta I + B)= (\beta I - A) X^{(k+\frac{1}{2})} + C \qquad \left( \text {solve for }X^{(k+1)}\right) \end{array}\right. }, \end{aligned}$$
(2.1)

for \(k=0,1,2,\dots , \) until \(\left\{ X^{(k)}\right\} \) converges.

The choice of the shift parameters \((\alpha , \beta )\) strongly determines the convergence rate of the ADI scheme. Some algorithms use different shifts, say \(\{(\alpha _k, \beta _k)\}_{k=0}^N\) in N iterations, see (Benner et al. 2009; Lu and Wachspress 1991; Wachspress 1988, 2009). Following the strategy adopted in Liu et al. (2020), here we decided to use two fixed shifts \((\alpha , \beta )\) in every iteration of ADI.

The two steps in (2.1) require the solution of two linear systems involving matrices \(\alpha I + A\) and \(\beta I + B\). The assumption that matrices A and B are both positive semi-definite, even though one of the matrices is also positive definite, allows us to adequately choose shifts \(\alpha \) and \(\beta \) so that the matrices \(\alpha I + A\) and \(\beta I + B\) are reasonably diagonally dominant. This diagonal dominance property guarantees that both incomplete factorization and splitting iteration are applicable, stable and efficient, as mentioned in Bai et al. (2006). Furthermore, the convergence speed of Krylov subspace iteration methods such as GMRES can be considerably accelerated for some adequate preconditioner for these classes of matrices, see (Bai 2016).

When it concerns to analyze the theoretical convergence of the ADI iteration (2.1), it is common to rewrite this iteration in the matrix–vector form,

$$\begin{aligned} \textbf{x}^{(k+1)} = \mathscr {H} \textbf{x}^{(k)} + \mathscr {G}\textbf{c}, \end{aligned}$$
(2.2)

where \({\mathscr {H}},\mathscr {G}\in \mathbb {C}^{{mn}\times {mn}}\) and \(\textbf{x},\textbf{c}\in \mathbb {C}^{{mn}\times {1}}\). The matrices \(\mathscr {H}=\mathscr {H}(\alpha , \beta )\) and \(\mathscr {G}=\mathscr {G}(\alpha , \beta )\) are defined by

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathscr {H}= \left[ (\beta I + B)^{-T}(\alpha I - B)^{T}\right] \otimes \left[ (\beta I - A)(\alpha I + A)^{-1}\right] \\ \mathscr {G} = (\alpha + \beta ) \left[ (\beta I + B)^{-T} \otimes (\alpha I + A)^{-1}\right] \end{array}\right. } \end{aligned}$$
(2.3)

where \(\textbf{x}\) and \(\textbf{c}\) are the column-stacking vectors of the matrices X and C, respectively, and \(\otimes \) is the symbol for the standard Kronecker product. To derive these expressions, use direct substitution in (2.1) and recall that vectorizing UXV column-wise gives \((V^T\otimes U)\textbf{x}\), for any square matrices U, V and conformable matrix X. The matrix \({\mathscr {H}}\) is called the iteration matrix of the scheme (2.2) and we will denote its spectral radius by \(\rho (\mathscr {H})\).

Suppose that A is a positive definite matrix and B is a positive semi-definite matrix, in the weaker sense (recall the definition from the Introduction). We now present a sufficient condition for convergence of the ADI iterative process (2.1) in this case. Assume that equation (1.1) has a unique solution \({X^*}\) and let \(\left\{ X^{(k)}\right\} \), \(k=0,1,2,\ldots \), be the sequence of approximations to \({X^*}\) obtained with the iterative scheme (2.1). Let \(\lambda _j, j=1, \ldots ,m\), be the eigenvalues of A and \(\mu _i, i=1,\ldots ,n\), the eigenvalues of B. Then, by the assumptions of definiteness,

$$\begin{aligned} {\text {Re}}(\lambda _j)>0, \; j=1,\ldots , m,\qquad \text { and } \qquad {\text {Re}}(\mu _i)\ge 0, \; i=1,\ldots , n, \end{aligned}$$

where \({\text {Re}}(x)\), for \(x \in \mathbb {C}\), denotes the real part of x. According to (Liu et al. 2020, Theorem 1), for positive constants \(\alpha \) and \(\beta \), if

$$\begin{aligned} -\min _j\mathrm{{Re}}(\lambda _j)<\frac{\alpha -\beta }{2}<\min _i\mathrm{{Re}}(\mu _i), \end{aligned}$$

then \(\rho (\mathscr {H}) <1 \), or, equivalently, the sequence \(\left\{ X^{(k)}\right\} \) converges to the exact solution \({X^*}\).

3 Extrapolated ADI iteration

Extrapolation is a commonly used acceleration technique in the study of iterative methods. In this section, we introduce an extrapolated ADI iteration (EADI) for solving the Sylvester equation (1.1). To improve the approximation computed in each iteration of the ADI method, this EADI iteration incorporates an extra step (refinement step), using a new parameter \(\omega \), at a low computational cost. Following similar ideas to what is used in stationary iterative methods, the parameter \(\omega \) is fixed in every iteration, the same way that shifts \((\alpha ,\beta )\) are also fixed. The EADI iteration is defined as follows.

EADI iteration. Given an initial approximation \(X^{(0)}\), positive constants \(\alpha \), \(\beta \) (shift parameters) and \(\omega \) (extrapolation parameter), repeat the steps

$$\begin{aligned} {\left\{ \begin{array}{ll} (\alpha I + A) X^{(k+\frac{1}{2})} = X^{(k)} (\alpha I - B) + C\qquad \quad \big (\text {solve for }X^{(k+\frac{1}{2})}\big )\\ \widetilde{X}^{(k)} (\beta I + B)= (\beta I - A) X^{(k+\frac{1}{2})} + C \quad \qquad \left( \text {solve for }\widetilde{X}^{(k)}\right) \\ X^{(k+1)} = (1-\omega )X^{(k)} + \omega \widetilde{X}^{(k)} \end{array}\right. }, \end{aligned}$$
(3.1)

for \(k=0,1,2,\dots , \) until \(\left\{ X^{(k)}\right\} \) converges.

According to the formulation (2.2), the first two steps of the EADI iteration (3.1) can be rewritten in the matrix–vector form

$$\begin{aligned} \widetilde{\textbf{x}}^{(k)} = \mathscr {H} \textbf{x}^{(k)} + \mathscr {G}\textbf{c}, \end{aligned}$$
(3.2)

where \(\mathscr {H}\) and \(\mathscr {G}\) are the matrices defined in (2.3). Then, from the third step of (3.1), we obtain

$$\begin{aligned} \textbf{x}^{(k+1)} = \left[ (1 - \omega )I + \omega \mathscr {H}\right] \textbf{x}^{(k)} + \omega \mathscr {G}\textbf{c}. \end{aligned}$$
(3.3)

Thus, the iteration matrix of the EADI single-step iterative formula (3.3), denoted by \(\mathscr {H}_{\omega }=\mathscr {H}_{\omega }{(\alpha ,\beta , \omega )}\), is defined by

$$\begin{aligned} \mathscr {H}_{\omega }= (1 - \omega )I + \omega \mathscr {H}. \end{aligned}$$
(3.4)

The following result gives inclusion intervals for the parameters \(\alpha , \beta \) and \(\omega \) for which the convergence of the EADI iterative procedure (3.1) is ensured.

Theorem 3.1

Let matrices A and B in equation (1.1) be positive definite and positive semi-definite, respectively, or vice versa (using the weaker definition), and let \(\alpha , \beta , \omega \) be three positive constants. Let \(\lambda _j, j=1, \ldots ,m\), be the eigenvalues of A, \(\mu _i, i=1,\ldots ,n\), the eigenvalues of B and \(\rho (\mathscr {H} )\) the spectral radius of \(\mathscr {H}\) in (2.3). If

$$\begin{aligned} -\min _j\mathrm{{Re}}(\lambda _j)<\frac{\alpha -\beta }{2}<\min _i\mathrm{{Re}}(\mu _i) \qquad \text {and} \qquad 0<\omega <\frac{2}{1+\rho (\mathscr {H})}, \end{aligned}$$
(3.5)

then the sequence \(\left\{ X^{(k)}\right\} \), \(k=0,1,2 \ldots ,\) generated by the EADI iteration (3.1) converges to the exact solution \({X}^*\) of (1.1).

Proof

We will show that the given conditions imply that \(\rho (\mathscr {H}_{\omega }) < 1\), a necessary and sufficient condition for the convergence of the sequence \(\left\{ X^{(k)}\right\} \).

As it has been observed at the end of Sect. 2, the first condition on the shift parameters \(\alpha \) and \(\beta \) guarantees the convergence of the ADI iterative expression (2.2), which means that \(\rho (\mathscr {H}) < 1\).

Now notice that given an eigenvalue \(\lambda \) of \(\mathscr {H}\), \((1 - \omega ) + \omega \lambda \) is an eigenvalue of \(\mathscr {H}_{{\omega }}\) and thus

$$\begin{aligned} \rho (\mathscr {H}_{{\omega }}) = \max _{\lambda \in \lambda (\mathscr {H})} |(1 - \omega ) + \omega \lambda |. \end{aligned}$$
(3.6)

For \(\lambda = a + i b\), \(a,b \in \mathbb {R}\), \(i^2=-1\), we have \(|a| \le |\lambda | <1\), \(|b| \le |\lambda | <1\) and

$$\begin{aligned} {|1 - \omega + \omega \lambda |}^{2}&= {|1 - \omega (1-a) + \omega bi|}^2 = 1 - 2 \omega (1 - a) + \omega ^2 (1 - a)^2 + \omega ^2b^{2}\\&=1 -\left[ 2 \omega (1 - a) - \omega ^2 \left( 1 - 2a + |\lambda |^{2}\right) \right] . \end{aligned}$$

So, if \(2 \omega (1 - a) > \omega ^2 (1 - 2a + |\lambda |^{2})\), we will have \({|1 - \omega + \omega \lambda |}^{2} < 1\) and thus \(\rho (\mathscr {H}_{{\omega }})<1\). Observe that, since \(\omega >0\), by assumption, and \(1 - 2a + |\lambda |^{2}>0\), that condition is equivalent to

$$\begin{aligned} 0< \omega < \frac{2(1-a)}{1 - 2a + |\lambda |^{2}}. \end{aligned}$$
(3.7)

To complete the proof it only remains to verify that \(0<\omega <\dfrac{2}{1+\rho (\mathscr {H})}\), the condition stated in the theorem, implies (3.7). In fact,

$$\begin{aligned} \frac{2}{1+\rho (\mathscr {H})} \le \frac{2}{1+|\lambda |} \le \frac{2(1-a)}{1 - 2a + |\lambda |^{2}}. \end{aligned}$$

given that the inequality \(1 - 2a + |\lambda |^{2}\le (1+|\lambda |)(1-a)\) is equivalent to \((a+|\lambda |)(1-|\lambda |)\ge 0\) which is always true when \(|a| \le |\lambda | < 1\), since this condition implies \(a+|\lambda |\ge 0\) and \(1-|\lambda |>0\).

We have proved that the restrictions (3.5) on the range of the values \(\alpha , \beta \) and \(\omega \) imply that \(\rho (\mathscr {H}_{{\omega }}) < 1\) and, therefore, ensure the convergence of the EADI iteration, under the stated assumptions on positiveness of the matrices A and B. \(\square \)

Observe that when \(0<\rho (\mathscr {H})<1\) we will have \(1<\dfrac{2}{1+\rho (\mathscr {H})}<2\) and thus, in practice, the choice \(0<\omega <1\) will always permit convergence (although it might not be the optimal choice).

We would like to acknowledge that the convergence condition \(0<\omega <\dfrac{2}{1+\rho (\mathscr {H})}\) in Theorem 3.1 can also be directly derived from Theorem 1 in Cao (1998). We thank an anonymous referee for this useful observation.

4 Block SOR-ADI iteration

In this section, motivated by the work presented in Bai et al. (2007); Bai and Ng (2012) by Bai, Golub and Ng, we will describe a block successive overrelaxation version of the ADI iterative scheme (block SOR-ADI) and derive convergence conditions for this new version.

First we notice that if the sequence \(\left\{ X^{(k)}\right\} \), \(k=0,1,2 \ldots ,\) obtained using (2.1), converges to the exact solution \({X^*}\) of the equation (1.1), then we have

$$\begin{aligned} \left\{ \begin{array}{cc} (\alpha I + A) {X^*} - {X^*} (\alpha I - B)=A {X^*} + {X^*} B = C\\ {X^*} (\beta I + B) - (\beta I - A) {X^*} =A {X^*} + {X^*} B = C \end{array}\right. . \end{aligned}$$

From (2.1) we are able to define the fixed-point matrix equations

$$\begin{aligned} \left\{ \begin{array}{cc} (\alpha I + A) X &{}= Y (\alpha I - B) + C\\ Y (\beta I + B) &{}= (\beta I - A) X + C \end{array}\right. \end{aligned}$$
(4.1)

and can establish that if \(X^*\) is the exact solution of the equation (1.1), then it is the fixed point of both equations above. The reverse is also true. Thus, analogously to (Bai et al. 2007, Theorem 3.1) we have the following result.

Theorem 4.1

The fixed-point matrix equations in (4.1) and the original matrix equation (1.1) are equivalent equations.

Adopting a matrix–vector formulation, the two equations in (4.1) can be represented by

$$\begin{aligned} W \textbf{z} = \textbf{b} \end{aligned}$$
(4.2)

where

$$\begin{aligned} W=\begin{bmatrix}I \otimes (\alpha I + A) &{} -(\alpha I - B)^{T} \otimes I \\ - I \otimes (\beta I - A) &{} (\beta I + B)^{T} \otimes I \end{bmatrix}, \quad \textbf{z}= \begin{bmatrix} \textbf{x}\\ \textbf{y}\end{bmatrix}, \quad \textbf{b}=\begin{bmatrix} \textbf{c}\\ \textbf{c}\end{bmatrix}, \end{aligned}$$
(4.3)

for \(\textbf{x}\), \(\textbf{y}\) and \(\textbf{c}\) representing the column-stacking vectors of the matrices X, Y and C, respectively. We will show that, under the conditions considered in Theorem 3.1, the coefficient matrix \(W=W(\alpha ,\beta )\) is nonsingular and, thus, the use of the Gauss-Seidel method can be considered.

Theorem 4.2

Let matrices A and B and parameters \(\alpha \) and \(\beta \) satisfy the assumptions and conditions given in Theorem 3.1. The coefficient matrix W in the equation (4.3) is nonsingular.

Proof

The positive definiteness or semi-definiteness assumptions on A and B and the fact that \(\alpha ,\beta >0\) imply that matrices \(I \otimes (\alpha I + A)\) and \((\beta I + B)^{T} \otimes I \) are positive definite and hence nonsingular. Recall the eigenvalue property of the Kronecker product.

Applying the mixed-product and inversion properties of the Kronecker operator, we can decompose W into a matrix product,

$$\begin{aligned} W = \begin{bmatrix} I &{} O \\ - I \otimes \left[ (\beta I - A)(\alpha I + A)^{-1}\right] &{} I \end{bmatrix} \begin{bmatrix} I \otimes (\alpha I + A) &{} -(\alpha I - B)^{T} \otimes I \\ O &{} S\end{bmatrix} \end{aligned}$$

with matrix S, the Schur complement of W, given by

$$\begin{aligned} S=\left[ (\beta I + B)^{T} \otimes I\right] - \left\{ (\alpha I - B)^{T} \otimes \left[ (\beta I - A)(\alpha I + A)^{-1}\right] \right\} . \end{aligned}$$

Thereby, we obtain

$$\begin{aligned} S= & {} \left[ (\beta I + B)^{T} \otimes I \right] \left\{ I - \left[ (\beta I + B)^{-T} \otimes I \right] \left[ (\alpha I - B)^{T} \otimes \left[ (\beta I - A)(\alpha I + A)^{-1}\right] \right] \right\} \\= & {} \left[ (\beta I + B)^{T} \otimes I \right] \left\{ I - \left[ (\beta I + B)^{-T}(\alpha I - B)^{T}\right] \otimes \left[ (\beta I - A)(\alpha I + A)^{-1}\right] \right\} \\= & {} \left[ (\beta I + B)^{T} \otimes I \right] \left( I - \mathscr {H}\right) , \end{aligned}$$

where \(\mathscr {H}\) is the iteration matrix of the ADI scheme, defined in (2.3). Under the given assumptions, \(\rho (\mathscr {H})<1\). Thus, since both matrices \((\beta I + B)^{T} \otimes I \) and \(\left( I - \mathscr {H}\right) \) are nonsingular, W is also nonsingular. \(\square \)

In what follows, we will describe a block SOR-ADI iterative method to solve the block \(2\times 2\) linear system (4.2) and establish its convergence properties. First, it is suitable to present the block Jacobi and the block Gauss-Seidel iterations. Let the decomposition

$$\begin{aligned} \begin{aligned} W&= \begin{bmatrix} I \otimes (\alpha I + A) &{} O \\ O &{} (\beta I + B)^{T} \otimes I \end{bmatrix} - \begin{bmatrix} O &{} (\alpha I - B)^{T} \otimes I \\ I \otimes (\beta I - A) &{} O \end{bmatrix} \\&= M_{J} - N_{J} \end{aligned} \end{aligned}$$

be the block Jacobi splitting of W. Thus,

$$\begin{aligned} M_{J}^{-1}=\begin{bmatrix} I \otimes (\alpha I + A)^{-1} &{} O \\ O &{} (\beta I + B)^{-T} \otimes I \end{bmatrix} \end{aligned}$$

and the block Jacobi iterative scheme is defined by

$$\begin{aligned} \textbf{z}^{(k+1)} = \mathscr {T}_{J} \textbf{z}^{(k)} + M^{-1}_{J} \textbf{b}, \end{aligned}$$
(4.4)

where the iteration matrix \(\mathscr {T}_{J}=\mathscr {T}_{J}(\alpha ,\beta )\) obtained is

$$\begin{aligned} \mathscr {T}_{J}= M_{J}^{-1}N_{J}=\begin{bmatrix} O &{} (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1} \\ (\beta I + B)^{-T} \otimes (\beta I - A) &{} O \end{bmatrix}. \end{aligned}$$
(4.5)

The block Gauss-Seidel splitting of W,

$$\begin{aligned} \begin{aligned} W&= \begin{bmatrix} I \otimes (\alpha I + A) &{} O \\ - I \otimes (\beta I - A) &{} (\beta I + B)^{T} \otimes I \end{bmatrix} - \begin{bmatrix} O &{} (\alpha I - B)^{T} \otimes I \\ O &{} O \end{bmatrix} \\&= M_{GS} - N_{GS}, \end{aligned} \end{aligned}$$

leads to the block Gauss-Seidel iterative scheme

$$\begin{aligned} \textbf{z}^{(k+1)} = \mathscr {T}_{GS} \textbf{z}^{(k)} + M_{GS}^{-1}\textbf{b}, \end{aligned}$$
(4.6)

where the iteration matrix \(\mathscr {T}_{GS}=\mathscr {T}_{GS}(\alpha ,\beta )\) is defined by \(\mathscr {T}_{GS} = M_{GS}^{-1}N_{GS}\). Since,

$$\begin{aligned} M_{GS}^{-1}=\begin{bmatrix} I \otimes (\alpha I + A)^{-1} &{} O \\ (\beta I + B)^{-T} \otimes \left[ (\beta I - A) (\alpha I + A)^{-1} \right] &{} (\beta I + B)^{-T} \otimes I \end{bmatrix}, \end{aligned}$$

we obtain

$$\begin{aligned} \mathscr {T}_{GS} = \begin{bmatrix} O &{} (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1} \\ O &{} \mathscr {H} \end{bmatrix}, \end{aligned}$$
(4.7)

where \(\mathscr {H}\) is the iteration matrix of the ADI method.

In practice, to improve the convergence rate of the Gauss-Seidel iteration, it is common to consider a variant of the method which incorporates a successive overrelaxation technique. Using a new parameter \(\omega \ne 0\) (relaxation parameter), in the block Gauss-Seidel iteration we consider the linear system

$$\begin{aligned} \omega W \textbf{z} = \omega \textbf{b}, \end{aligned}$$

equivalent to (4.3), and the coefficient matrix decomposition

$$\begin{aligned} \begin{aligned} \omega W&= \begin{bmatrix} I \otimes (\alpha I + A) &{} O \\ - \omega I \otimes (\beta I - A) &{} (\beta I + B)^{T} \otimes I \end{bmatrix} - \begin{bmatrix} (1-\omega )I \otimes (\alpha I + A) &{} \omega (\alpha I - B)^{T} \otimes I \\ O &{} (1-\omega )(\beta I + B)^{T} \otimes I \end{bmatrix} \\&= M_{SOR} - N_{SOR}. \end{aligned} \end{aligned}$$

The iterative equation obtained, called the block SOR iteration, is

$$\begin{aligned} \begin{aligned}&\textbf{z}^{(k+1)} =\\&\mathscr {T}_{SOR} \textbf{z}^{(k)} + \omega M_{SOR}^{-1} \textbf{b}, \end{aligned}\nonumber \\ \end{aligned}$$
(4.8)

where

$$\begin{aligned} M_{SOR}^{-1}=\begin{bmatrix} I \otimes (\alpha I + A)^{-1} &{} O \\ \omega (\beta I + B)^{-T} \otimes \left[ (\beta I - A) (\alpha I + A)^{-1}\right] &{} (\beta I + B)^{-T} \otimes I \end{bmatrix} \end{aligned}$$

and the iteration matrix \(\mathscr {T}_{SOR}=\mathscr {T}_{SOR}(\alpha ,\beta ,\omega )\) is given by

$$\begin{aligned} \mathscr {T}_{SOR}= M_{SOR}^{-1}N_{SOR}=\begin{bmatrix} (1-\omega )I\otimes I &{} \omega (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1} \\ \omega (1-\omega )(\beta I + B)^{-T} \otimes (\beta I -A) &{} (1-\omega )I\otimes I + \omega ^{2} \mathscr {H} \end{bmatrix}.\nonumber \\ \end{aligned}$$
(4.9)

Observe that with the choice \(\omega =1\) the block SOR method reduces to the block Gauss-Seidel method with \(\mathscr {T}_{SOR}=\mathscr {T}_{GS}\).

Recasting \(\textbf{z}^{(k)}=\begin{bmatrix} \textbf{x}^{(k)}\\ \textbf{y}^{(k)}\end{bmatrix}\) and \(\textbf{b} =\begin{bmatrix} \textbf{c} \\ \textbf{c} \end{bmatrix}\) from (4.2), we can express the block SOR iteration (4.8) as

$$\begin{aligned} {\left\{ \begin{array}{ll} \textbf{x}^{(k+1)} = (1-\omega ) \textbf{x}^{(k)} + \omega \left[ (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1}\right] \textbf{y}^{(k)}+ \omega \left[ I \otimes (\alpha I + A)^{-1}\right] \textbf{c}\\ \textbf{y}^{(k+1)} = \omega (1-\omega )\left[ (\beta I + B)^{-T} \otimes (\beta I -A)\right] \textbf{x}^{(k)}+ (1-\omega )\textbf{y}^{(k)} + \omega ^{2} \mathscr {H} \textbf{y}^{(k)}+\\ \hspace{1.5cm} +\omega ^2(\beta I + B)^{-T} \otimes \left[ (\beta I - A) (\alpha I + A)^{-1}\right] \textbf{c} + \omega \left[ (\beta I + B)^{-T} \otimes I\right] \textbf{c} \end{array}\right. } \end{aligned}$$
(4.10)

and the following step is to go back to the matrix-matrix formulation with the matrices X and Y in (4.1). Prior to this transformation, notice that we can write \(\mathscr {H} \) as a mixed-product,

$$\begin{aligned} \mathscr {H}=\left[ (\beta I + B)^{-T}\otimes (\beta I - A)\right] \left[ (\alpha I -B)^{T} \otimes (\alpha I + A)^{-1}\right] , \end{aligned}$$

and \(\textbf{y}^{(k+1)}\) in (4.10) can be simplified to

$$\begin{aligned} \textbf{y}^{(k+1)}&=(1-\omega )\textbf{y}^{(k)}+ \omega \left[ (\beta I + B)^{-T} \otimes (\beta I -A) \right] \bigg \{(1-\omega )\textbf{x}^{(k)}+\omega \left[ (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1}\right] \textbf{y}^{(k)}\\&\quad +\omega \left[ I \otimes (\alpha I + A)^{-1}\right] \textbf{c} \bigg \}+ \omega \left[ (\beta I + B)^{-T} \otimes I\right] \textbf{c}\\&=(1-\omega )\textbf{y}^{(k)}+ \omega \left[ (\beta I + B)^{-T} \otimes (\beta I -A) \right] \textbf{x}^{(k+1)}+ \omega \left[ (\beta I + B)^{-T} \otimes I\right] \textbf{c}. \end{aligned}$$

The scheme (4.10) can be transformed into the following matrix-matrix version which is called the block SOR-ADI iteration. Recall that for square matrices U, V and vector \(\textbf{x}\), the matrix-stacking of the vector \((V^T\otimes U)\textbf{x}\) can be given by UXV, where X is the matrix-stacking (column-wise) of the vector \(\textbf{x}\).

Block SOR-ADI iteration. Given initials approximations \(X^{(0)}\) and \(Y^{(0)}\) and positive constants \(\alpha \), \(\beta \) (shift parameters) and \(\omega \) (relaxation parameter), repeat the steps

$$\begin{aligned} {\left\{ \begin{array}{ll} X^{(k+1)} = (1-\omega )X^{(k)} + \omega (\alpha I + A)^{-1} \left[ Y^{(k)} (\alpha I - B) + C\right] \\ Y^{(k+1)} = (1-\omega )Y^{(k)} + \omega \left[ (\beta I - A) X^{(k+1)} + C \right] (\beta I + B)^{-1} \end{array}\right. } \end{aligned}$$
(4.11)

for \(k=0,1,2,\cdots , \) until \(\left\{ X^{(k)}\right\} \) and \(\left\{ Y^{(k)}\right\} \) converge.

An interesting observation is that this scheme of the block SOR-ADI iteration can be expressed as a certain combination of the ADI iteration and the extrapolated ADI iteration, so it is expectable that the convergence rate will be improved. In this context, observe that (4.11) is equivalent to

$$\begin{aligned} {\left\{ \begin{array}{ll} (\alpha I + A) X^{(k+\frac{1}{2})} = Y^{(k)} (\alpha I - B) + C\qquad \quad \;\;\;\left( \text {solve for }X^{(k+\frac{1}{2})}\right) \\ X^{(k+1)} = (1-\omega )X^{(k)} + \omega X^{(k+\frac{1}{2})}\\ Y^{(k+\frac{1}{2})} (\beta I + B)= (\beta I - A) X^{(k+1)} + C \quad \qquad \left( \text {solve for }Y^{(k+\frac{1}{2})}\right) \\ Y^{(k+1)} = (1-\omega )Y^{(k)} + \omega Y^{(k+\frac{1}{2})} \end{array}\right. }, \end{aligned}$$
(4.12)

for \(k=0,1,2,\cdots , \) until \(\left\{ X^{(k)}\right\} \) and \(\left\{ Y^{(k)}\right\} \) converge.

For both efficiency and numerical accuracy purposes, the scheme (4.12) is the approach to follow in a computational implementation of the SOR-ADI iteration (4.11), since the explicit computation of a matrix inverse should usually be avoided in favour of the computation of the solution of the equivalent linear system with multiple right-hand sides.

We can establish a relation between the eigenvalues of the block Jacobi iteration matrix \(\mathscr {T}_{J}=\mathscr {T}_{J}(\alpha ,\beta )\), the ADI iteration matrix \(\mathscr {H}=\mathscr {H}(\alpha , \beta )\) and the block Gauss-Seidel iteration matrix \(\mathscr {T}_{GS}=\mathscr {T}_{GS} (\alpha ,\beta )\). In case of convergence, these results allow us to compare the convergence rates. We state these relations in the following theorem.

Theorem 4.3

Let matrices A and B and parameters \(\alpha \) and \(\beta \) satisfy the assumptions and conditions given in Theorem 3.1. The following statements are true:

  1. (a)

    \(\mathscr {T}_{GS}\) and \(\mathscr {H}\) have the same set of non-zero eigenvalues.

  2. (b)

    If \(\lambda \) is an eigenvalue of \(\mathscr {T}_{J}\), then so is \(-\lambda \).

  3. (c)

    If \(\lambda \) is an eigenvalue of \(\mathscr {T}_{J}\), then \(\lambda ^2\) is an eigenvalue of \(\mathscr {H}\).

  4. (d)

    Conversely, if \(\mu \ne 0\) is an eigenvalue of \(\mathscr {H}\) and \(\lambda ^2=\mu \), then \(\lambda \) is an eigenvalue of \(\mathscr {T}_{J}\).

Thus, as a consequence, since \(\rho (\mathscr {H})<1\),

$$\begin{aligned} \rho (\mathscr {H})=\rho (\mathscr {T}_{GS}) = \big (\rho (\mathscr {T}_{J})\big )^{2}<1. \end{aligned}$$

This means that block Jacobi iteration (4.4), block Gauss-Seidel iteration (4.6) and ADI iteration (2.1) are all convergent methods. The block Gauss-Seidel iteration is twice as fast as the block Jacobi iteration.

Proof

  1. (a)

    If \(\mathscr {T}_{GS}\mathbf {{z}}=\mu \mathbf {{z}}\) with \(\textbf{z}= \begin{bmatrix} \textbf{u} \\ \textbf{v} \end{bmatrix}\), then from (4.7) we have

    $$\begin{aligned} (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1}\textbf{v}=\mu \textbf{u} \qquad \text {and} \qquad \mathscr {H}\textbf{v}=\mu \textbf{v}. \end{aligned}$$

    Thus, \(\mu \) is also an eigenvalue of \(\mathscr {H}\) with eigenvector \(\textbf{v}\).

    Conversely, if \(\mathscr {H}\textbf{v}=\mu \textbf{v}\), \(\mu \ne 0\), define \(\textbf{u}=(\alpha I - B)^{T} \otimes (\alpha I + A)^{-1}\textbf{v}/\mu \) and \(\textbf{z}= \begin{bmatrix} \textbf{u} \\ \textbf{v} \end{bmatrix}\). We then obtain \(\mathscr {T}_{GS}\mathbf {{z}}=\mu \mathbf {{z}}\).

  2. (b)

    Let \(\lambda \) be an eigenvalue of \(\mathscr {T}_{J} \) and \(\textbf{z}= \begin{bmatrix} \textbf{u} \\ \textbf{v} \end{bmatrix}\) the corresponding eigenvector. From the eigenvector equation \(\mathscr {T}_{J}\textbf{z} = \lambda \textbf{z}\), we have

    $$\begin{aligned} (\alpha I - B)^{T} \otimes (\alpha I + A)^{-1} \textbf{v} = \lambda \textbf{u} \qquad {\text{ and }} \qquad (\beta I + B)^{-T} \otimes (\beta I - A) \textbf{u} = \lambda \textbf{v}. \end{aligned}$$

    It is simple to verify that \(\mathscr {T}_{J}\varvec{\bar{z}} = -\lambda \varvec{\bar{z}}\) for \(\varvec{\bar{z}}= \begin{bmatrix} \textbf{u} \\ -\textbf{v} \end{bmatrix}\) and, thus, \(-\lambda \) is an eigenvalue of \(\mathscr {T}_{J}\) with eigenvector \(\varvec{\bar{z}}\).

Statements (c) and (d) follow directly from (a), as a corollary of Theorem 4.5 (see below), since \(\mathscr {T}_{SOR}=\mathscr {T}_{GS}\) for \(\omega =1\).

The assumptions on positive definiteness or semi-definiteness of the matrices A and B and the condition on \(\alpha \) and \(\beta \) imply that \(\rho (\mathscr {H}) < 1\), which says that the ADI iteration is convergent. Thus,

$$\begin{aligned}\rho (\mathscr {H})=\rho (\mathscr {T}_{GS}) = \big (\rho (\mathscr {T}_{J})\big )^{2}<1\end{aligned}$$

and all the three methods are convergent. \(\square \)

The following concept is an important property in the SOR convergence theory.

Definition 4.4

We say that a matrix T has block Property A if T is a block diagonal matrix or there exists a permutation matrix P such that

$$\begin{aligned} PTP^T=\begin{bmatrix}T_{11} &{} T_{12}\\ T_{21} &{} T_{22}\end{bmatrix} \end{aligned}$$

where \(T_{11}\) and \(T_{22}\) are block diagonal matrices.

The block consistently ordered property generalizes block Property A. See, for instance, (Young 1971).

Matrix W in (4.3) has block Property A. The (1, 1) block is a block diagonal matrix and for the (2, 2) block it is not difficult to verify that there is a permutation matrix \(P'\) such that

$$\begin{aligned}P'\left[ (\beta I + B)^{T} \otimes I\right] {P'}^T=I\otimes (\beta I + B)^{T}.\end{aligned}$$

So \(P=\begin{bmatrix} I &{} O\\ O &{} P' \end{bmatrix}\) is a permutation matrix that drives W into the desired block Property A structure. Recall that, in general, if U and V are square matrices, then \(U\otimes V\) and \(V\otimes U\) are even permutation similar, meaning that there exists a permutation matrix Q such that \(V\otimes U=Q(U\otimes V)Q^T\).

It is then possible to apply a classical result in matrix iterative analysis that relates the eigenvalues of the block Jacobi and the block SOR iteration matrices, \(\mathscr {T}_{J}\) and \(\mathscr {T}_{SOR}\).

Theorem 4.5

Let \(\omega \ne 0\). If \(\lambda \) is an eigenvalue of \(\mathscr {T}_{J}\) and \(\mu \) satisfies

$$\begin{aligned} (\mu + \omega - 1)^2=\mu \omega ^2 \lambda ^2, \end{aligned}$$
(4.13)

then \(\mu \) is an eigenvalue of \(\mathscr {T}_{SOR}\). Conversely, if \(\mu \ne 0\) is an eigenvalue of \(\mathscr {T}_{SOR}\) and \(\lambda \) satisfies (4.13), then \(\lambda \) is an eigenvalue of \(\mathscr {T}_{J}\).

Proof

Since matrix W in (4.3) satisfies Property A, the result follows directly from existing literature. See Theorem 4.5 in Varga (2000). \(\square \)

The convergence result for the block SOR-ADI iteration (4.11) follows from Theorems 4.3 and 4.5.

Theorem 4.6

Let matrices A and B and parameters \(\alpha \) and \(\beta \) satisfy the assumptions and conditions given in Theorem 3.1. Let \(\omega \ne 0\) be the relaxation parameter in the block SOR-ADI iteration (4.11).

  1. (1)

    Suppose that all the eigenvalues of \(\mathscr {T}_{J} \) are real. The block SOR-ADI iteration is convergent if and only if \(0< \omega < 2\).

  2. (2)

    Suppose that some eigenvalues of \(\mathscr {T}_{J} \) are complex. If for some positive number \(\tau \in (0,1)\) and each eigenvalue \(\mu = a + i b\) of \(\mathscr {T}_{J}\), the point (a, b) lies in the interior of the ellipse

    $$\begin{aligned} \mathscr {E}_\tau = \left\{ (u,v): u^2 + \frac{v^2}{\tau ^2} = 1\right\} \end{aligned}$$

    and \(\omega \) satisfies

    $$\begin{aligned} 0< \omega < \frac{2}{1 + \tau }, \end{aligned}$$
    (4.14)

    then the block SOR-ADI iteration is convergent. Conversely, if the block SOR-ADI iteration is convergent, then, for some \(\tau \in (0,1)\), all the eigenvalues of \(\mathscr {T}_{J} \) lie inside the ellipse \(\mathscr {E}_\tau \). Furthermore, if some eigenvalue lies on \(\mathscr {E}_\tau \) and if the block SOR-ADI iteration is convergente, then (4.14) holds.

Proof

Observe that the block SOR-ADI iteration (4.11) is convergent if and only if the block SOR iteration (4.8) is convergent. Another important observation here is that the assumptions considered imply that matrices \( (\alpha I + A)\) and \((\beta I + B)^{T} \) are nonsingular and, thus, matrix W in (4.3) not only satisfies Property A, but, in addition, all the diagonal blocks in this special block structure are invertible. Furthermore, block Property A is a sufficient condition for block consistently ordering.

  1. (1)

    From Theorem 4.3, we have \(\rho (\mathscr {T}_{J})<1\) and, by Theorem 2.2 in Young (1971), Chapter 6, this condition is equivalent to \(0< \omega < 2\) and \(\rho (\mathscr {T}_{SOR})<1\).

  2. (2)

    This result follows directly from Theorem 4.1 in Young (1971), Chapter 6. Since \(\rho (\mathscr {T}_{J})<1\), \(\tau \in (0,1)\).

\(\square \)

To get the most benefit from overrelaxation, we would like to find the value of \(\omega \) that minimizes \(\rho (\mathscr {T}_{SOR})\). A detailed discussion that the Jacobi spectral radius determines the smallest SOR spectral radius can be found in (Varga 2000, Section 4.3) and in (Young 1971, Section 6.4). The optimal value of \(\omega \) is

$$\begin{aligned} \omega _{opt} = \frac{2}{1+\sqrt{1-{(\rho (\mathscr {T}_{J}))}^2}} \end{aligned}$$

which gives the smallest spectral radius \(\rho (\mathscr {T}_{SOR}) =\omega _{opt}-1\).

5 Numerical examples

In this section we compare the computational performance of the three methods, ADI, EADI and block SOR-ADI, exhibiting some numerical examples. We also compare our methods with the Hermitian and skew-Hermitian splitting (HSS) method (Bai 2011), though some numerical examples presented in Liu et al. (2020) already show that the ADI method can outperform the HSS method. All the algorithms were implemented in Matlab (R2020b) in double precision (unit roundoff \(\varepsilon =2.2\, 10^{-16}\)) on a LAPTOP-KVSVAUU8 with an Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz and 8 GB RAM, under Windows 10 Home. See Appendix A for details on the implementations (Algorithms 1, 2 and 3 for ADI, EADI and SOR-ADI, respectively, and 4 for HSS). No parallel Matlab operations were used.

In Matlab one way to solve the linear system \(AX=B\) (multiple right-hand sides) is with \(X=\texttt {inv}(A)*B\). A better way, from the point of view of both execution time and numerical accuracy, is to use the matrix backslash operator \(X = A\backslash B\). When A is square, this produces the solution using Gaussian elimination, without explicitly forming the inverse \(A^{-1}\). The call \(Ad = \texttt {decomposition}(A)\) creates reusable matrix decompositions (LU, LDL, Cholesky, QR, and more) that enables us to solve linear systems more efficiently. The decomposition type is automatically chosen based on the properties of the input matrix A. For example, after computing \(Ad = \texttt {decomposition}(A)\) the call \(X = Ad\backslash B\) returns the same vector as \(X = A\backslash B\), but is typically much faster. This decomposition function is well-suited to solving problems that require repeated solutions, since the decomposition of the coefficient matrix does not need to be performed multiple times.

In each iteration, our methods require the solution of multiple linear systems with the same coefficient matrices, \((A+\alpha I)\) and \((B+\beta I)\). Using the above built-in Matlab functions in our implementations, the efficiency and accuracy will be improved by not forming explicitly the inverses \((A+\alpha I)^{-1}\) and \((B+\beta I)^{-1}\).

In all our numerical experiments we chose as initial approximations the null matrices, that is, \(X^{(0)}=O\), for ADI and EADI iterations, and \(X^{(0)}=Y^{(0)}=O\), for the block SOR-ADI iteration. The stopping criterion used was

$$\begin{aligned} \frac{ {\parallel R^{(k)} \parallel }_{F}}{ {\parallel C \parallel }_{F}} \le tol, \end{aligned}$$
(5.1)

where \(R^{(k)} = C-A X^{(k)} - X^{(k)} B \) is the residual attained at iteration k, tol is the desired accuracy, usually set to \(10^{-6}\), and \(\Vert \cdot \Vert _F\) denotes the Frobenius norm.

In our first example, we consider the two-dimensional convection-diffusion equation

$$\begin{aligned} -(u_{xx}+u_{yy})+\sigma (x,y) u_x+\tau (x,y) u_y=f(x,y) \end{aligned}$$
(5.2)

posed on the unit square \((0,1)\times (0,1)\) with Dirichlet-type boundary conditions. The coefficients \(\sigma \) and \(\tau \) represent the velocity components along the x and y directions, respectively, and here we take the case when \(\sigma \) and \(\tau \) are constant. See (Chen and Sheu 2000, p. 371). Different finite discretization schemes for the Laplacian operator \(u_{xx}+u_{yy}\) and for the first derivatives \(u_x\) and \(u_y\) lead to different linear systems which are naturally equivalent to standard Sylvester equations (with different discretization errors).

In Starke and Niethammer (1991) it is described how to obtain a general Sylvester equation \(AX+XB=C\) for any values of the coefficients \(\sigma \) and \(\tau \) using the second-order finite central differences operator. When \(\sigma \) and \(\tau \) are constant, A and B are tridiagonal Toeplitz matrices defined by

$$\begin{aligned} A={{\,\textrm{tridiag}\,}}\left( -1+\frac{\tau h}{2},2,-1-\frac{\tau h}{2}\right) \text { and } B={{\,\textrm{tridiag}\,}}\left( -1+\frac{\sigma h}{2},2,-1-\frac{\sigma h}{2}\right) \end{aligned}$$
(5.3)

for a uniform \(n\times n\) grid with step size \(h=1/(n+1)\). The matrix A corresponds to the discretization in the y-direction and the matrix B in the x-direction. If \(\tau =\sigma \) then \(A=B\).

A class of Sylvester equations, which arises from the discretization of various differential equations and boundary value problems using finite differences or Sinc-Galerkin schemes, can be found in Bai (2011); Wang et al. (2013); Zheng and Ma (2014).

Example 5.1

Here we consider the Sylvester equation (1.1) with matrices \(A,B\in \mathbb {R}^{n\times n}\) defined by (5.3). The parameters \(\tau \) and \(\sigma \) depend on the properties of the associated convection-diffusion problem with homogeneous Dirichlet boundary conditions. The function f is defined by \( f(x,y)=\varvec{e}^{x+y} \) and different values of \(\tau \), \(\sigma \) and \(h=\frac{1}{n+1}\) are tested.

The equation in this example was solved using ADI, EADI, block SOR-ADI and HSS methods. The summary of our experiments in terms of the number of iterations (iter) and the CPU time in seconds (\(\text {t}_{\text {CPU}}\)) is presented in Table 1 for different instances of the parameters \(\tau \) and \(\sigma \) and the order n of the matrices.

The values assigned to the shift parameters \(\alpha \) and \(\beta \), the same for ADI, EADI and SOR-ADI, followed from a few numerical tries starting from the values presented in (Liu et al. 2020, Tables 1, 2, 3) (see \(\alpha _{\exp }\) in those tables) which were obtained through a search procedure for similar matrices A and B. The choice of these parameters for the HSS method was made from analogous experiments. The extrapolation parameter in the EADI method and the relaxation parameter in the SOR-ADI method are denoted by \(\omega _{ext}\) and \(\omega _{sor}\), respectively, and the values chosen for these parameters were also settled from some numerical experiments.

Table 1 Performance of ADI, EADI, SOR-ADI and HSS methods for the Example 5.1
Full size table

In what respects to the number of iterations and the CPU time required by EADI and SOR-ADI methods to converge, given the residual tolerance (5.1), we observe a reduction in both indicators when compared to the ADI method. This reduction is more significative in the block SOR-ADI method, in particular in the case \(\tau =50\) and \(\sigma =0.1\). We can consider that the block SOR-ADI is the method which exhibits the best performance among the three methods (followed by the EADI method) - the number of iterations is sometimes less than a half, or even a third, of the number of iterations needed by the ADI method.

The comparison of the three methods ADI, EADI and block SOR-ADI with the HSS method shows that HSS is the slowest method in terms of the CPU time required. When compared with EADI and SOR-ADI, in addition to the number of iterations required being greater in most cases (about twice as much in half the cases) the computational cost of each HSS iteration is considerably higher and increases with n.

We now present a second example. This example is not connected to a practical application and it was devised only for testing purposes.

Example 5.2

Consider the problem of finding the solution of the Sylvester equation (1.1) with pentadiagonal Toeplitz matrices \(A\in \mathbb {R}^{m\times m}\) and \(B\in \mathbb {R}^{n\times n}\) given by

$$\begin{aligned} A={{\,\textrm{pentadiag}\,}}\left( -0.5,-1,r,-1,-0.5\right) \text { and } B={{\,\textrm{pentadiag}\,}}\left( -1,-0.5,s,-0.5,-1\right) ,\nonumber \\ \end{aligned}$$
(5.4)

where r and s are two non-zero real parameters, and matrix C is randomly generated from values uniformly distributed in [0, 10].

We considered different values for r and s and, in each case, different orders m and n of the matrices A and B, respectively. Table 2 contains the number of iterations and CPU time required by the four methods ADI, EADI, block SOR-ADI and HSS.

Table 2 Performance of ADI, EADI, SOR-ADI and HSS methods for the Example 5.2
Full size table

This is an interesting example. In the case \(r=4\) and \(s=3\), regardless of the order of the matrices A and B, the number of iterations is always the same (with residual tolerance \(tol=10^{-6}\)) for the four methods. We observe that both EADI and block SOR-ADI methods are more efficient than the ADI method—the number of iterations and the CPU time required are significantly reduced (a reduction of about 40%)—and their performance is approximately the same. The HSS method requires less iterations than the other three methods (only 2 or 3 iterations less than EADI and block SOR-ADI) but it is about twice or three times slower.

In the case \(r=10\) and \(s=3\), again the number of iterations is constant for any order of the matrices A and B, but here we found a significant superiority of the EADI method in relation to block SOR-ADI and ADI methods (although very satisfactory, this contradicts the general pattern which is that block SOR-ADI method is almost always more efficient than EADI). The HSS method requires more iterations than the EADI method and less iterations than the block SOR-ADI method, but in both cases the CPU time is greater.

6 Conclusion

We considered the problem of solving the continuous Sylvester equation \(AX+XB=C\) and, combining a classical method with classical acceleration techniques in a way that we have not seen directly presented in the literature before, we developed two iterative methods to solve this equation. These methods are variants of the ADI iterative method - an extrapolated variant (EADI) and a block successive overrelaxation variant (block SOR-ADI). We showed that these variants are closely related to each other, although their formulations did not anticipate this observation. Under certain assumptions of definiteness on matrices A and B, we established sufficient conditions for convergence of these two methods. The preliminary numerical examples provided show, as expected, that these schemes may be advantageous when compared to the basic ADI method. The convergence rate can be improved by the EADI method and, more significantly, by the block SOR-ADI method. Our experiments also show that these new methods are more efficient than the Hermitian and skew-Hermitian splitting (HSS) method. Even in the few cases when the number of iterations required by the HSS method is smaller, the significant higher computational cost of each iteration leads to a greater CPU time.

As future work, instead of using two fixed shifts throughout the whole iteration, we plan to incorporate in the proposed methods EADI and SOR-ADI heuristic shift-parameter strategies to compute different shifts (close to optimal) to be used in every step. We will be able to answer the question if the speed-up by our methods is also obtained when different ADI shifts are used, and compare the performance with existing ADI algorithms that follow the same approach, see (Benner et al. 2009; Li and White 2002; Wachspress 2009). Another interesting and related experiment would be to see if adding the refinement step of EADI to the factored ADI method (Benner et al. 2009) could improve its convergence rate.