# Sylvester equation / Seeking fast computation trick

step 1: I am implementing a fast solver and the idea is to solve a Sylvester equation of the form $$A_1 X+X B_1=S.$$

step 2: If the computed matrix X does not meet a tolerance criteria, I augment the matrices A_1 and B_1 and resolve the following Sylvester equation $$\begin{pmatrix}A_1 & A_2\end{pmatrix}X'+X' \begin{pmatrix}B_1 \\ B_2\end{pmatrix}= S.$$

Is there a fast way for using the previously computed matrix $$X$$ from step 1 without having to solve the full augmented Sylvester equation from step 2?

Update:

Lutz, thank you for your response. You are right. The first equation is as follows:

$$(I_{r_1} - A)X + X(I_{r_2} - B) = S,$$

where $$A$$ is an $$r_1 \times r_1$$ matrix and $$B$$ is an $$r_2 \times r_2$$ matrix.

The matrix $$A$$ is given by $$A_1 \cdot D_1 \cdot A_1^T$$, and $$B$$ is given by $$B_1 \cdot D_1 \cdot B_1^T$$, and $$S$$ is given by $$A_1^T \cdot D_2 \cdot B_1$$.

Then I augment the matrix $$A_1$$ as $$A_{11} = [A_1, A_2]$$, and matrix $$B_1$$ as $$B_{11} = [B_1, B_2]$$.

Then the new Sylvester equation to solve is given by:

$$(I_{r_1^*} - A_{\text{new}})X + X(I_{r_2^*} - B_{\text{new}}) = S_{\text{new}},$$

where $$A_{\text{new}} = A_{11} \cdot D_1 \cdot A_{11}^T$$, $$B_{\text{new}} = B_{11} \cdot D_1 \cdot B_{11}^T$$, and $$S_{\text{new}} = A_{11}^T \cdot D_2 \cdot B_{11}$$.

• Please check the dimensions, you can not enlarge square matrices this way to new square matrices. Is one of the $X$ transposed? Commented Jun 24, 2023 at 7:31
• Lutz, you were right. I have just updated the question with complete details of the construction of the matrices. Please let me know your thoughts. Commented Jun 24, 2023 at 8:17
• Yes, this makes more sense. Indeed, in the first formulation only $A_1,B_1$ need to be square, $X,S$ need to have the same format, but that can be rectangular. With the new formulation the construction process ensures the quadratic matrices, but of course also exhibits new terms that have to be compensated for, showing the non-triviality of the task. Did you follow any promising approaches, even if they did not run to the end? Commented Jun 24, 2023 at 10:44

I am afraid that your update is at odds/incompatible with many (all?) known techniques for solving Sylvester matrix equations.

Your update procedure is a fairly general update of the coefficient matrices that define the Sylvester equation. Without any restrictions on the extensions of $$A_1$$, $$B_1$$ there is no guarantee that the new equation is even uniquely solvable. The update is incompatible with Schur form of $$A$$ and $$B$$, which eliminates the possibility of recycling work done for the Bartel-Stewart method. The update can change the action of the coefficient matrices dramatically and this is likely to precludes the use of the Arnoldi methods by Jamoukha and Kasenally or the extended Krylov subspace method by Simoncini. There is chance that low-rank ADI method by Penzl can use the solution of the old equation as an initial guess for the solution to the new equation, but it is not at all certain that the old shift parameters will remain good. This will hinge on the change in the spectrum of $$A$$ and $$B$$. Nevertheless, this is probably the best place to start looking.

References:

R. H. Bartels and G. W. Stewart. Solution of the matrix equation AX+XB=C. Communication of the ACM, 15(9):820–826, 1972.

I. Jaimoukha and E. Kasenally. Krylov subspace methods for solving large Lyapunov equations. SIAM J. Matrix Anal, 31:227–251, 1994.

V. Simoncini. A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Scient. Computing, 29(3):1268–1288, 2007.

T. Penzl. A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comp. 2000, 21(4):1401–1418, 2000.

Obviously, this does not mean that what you seek is impossible, but if you find a solution, then it will be worthy of publication.