Bartels–Stewart algorithm#The Hessenberg–Schur algorithm

Let $X,\; C\; \backslash in\; \backslash mathbb\{R\}^\{m\; \backslash times\; n\}$, and assume that the eigenvalues of $A$ are distinct from the eigenvalues of $B$. Then, the matrix equation $AX\; -\; XB\; =\; C$ has a unique solution. The Bartels–Stewart algorithm computes $X$ by applying the following steps:

1.Compute the real Schur decompositions

: $R\; =\; U^TAU,$

: $S\; =\; V^TB^TV.$

The matrices $R$ and $S$ are block-upper triangular matrices, with diagonal blocks of size $1\; \backslash times\; 1$ or $2\; \backslash times\; 2$.

2. Set $F\; =\; U^TCV.$

3. Solve the simplified system $RY\; -\; YS^T\; =\; F$, where $Y\; =\; U^TXV$. This can be done using forward substitution on the blocks. Specifically, if $s\_\{k-1,\; k\}\; =\; 0$, then

: $(R\; -\; s\_\{kk\}I)y\_k\; =\; f\_\{k\}\; +\; \backslash sum\_\{j\; =\; k+1\}^n\; s\_\{kj\}y\_j,$

where $y\_k$ is the $k$th column of $Y$. When $s\_\{k-1,\; k\}\; \backslash neq\; 0$, columns $[\; y\_\{k-1\}\; \backslash mid\; y\_\{k\}]$ should be concatenated and solved for simultaneously.

4. Set $X\; =\; UYV^T.$

Using the QR algorithm, the real Schur decompositions in step 1 require approximately $10(m^3\; +\; n^3)$ flops, so that the overall computational cost is $10(m^3\; +\; n^3)\; +\; 2.5(mn^2\; +\; nm^2)$.

In the special case where $B=-A^T$ and $C$ is symmetric, the solution $X$ will also be symmetric. This symmetry can be exploited so that $Y$ is found more efficiently in step 3 of the algorithm.

The Hessenberg–Schur algorithm replaces the decomposition $R\; =\; U^TAU$ in step 1 with the decomposition $H\; =\; Q^TAQ$, where $H$ is an upper-Hessenberg matrix. This leads to a system of the form $HY\; -\; YS^T\; =\; F$ that can be solved using forward substitution. The advantage of this approach is that $H\; =\; Q^TAQ$ can be found using Householder reflections at a cost of $(5/3)m^3$ flops, compared to the $10m^3$ flops required to compute the real Schur decomposition of $A$.

The subroutines required for the Hessenberg-Schur variant of the Bartels–Stewart algorithm are implemented in the SLICOT library. These are used in the MATLAB control system toolbox.

For large systems, the $\backslash mathcal\{O\}(m^3\; +\; n^3)$ cost of the Bartels–Stewart algorithm can be prohibitive. When $A$ and $B$ are sparse or structured, so that linear solves and matrix vector multiplies involving them are efficient, iterative algorithms can potentially perform better. These include projection-based methods, which use Krylov subspace iterations, methods based on the alternating direction implicit (ADI) iteration, and hybridizations that involve both projection and ADI.{{Cite journal|last=Simoncini|first=V.|s2cid=17271167|date=2016|title=Computational Methods for Linear Matrix Equations|journal=SIAM Review|language=en-US|volume=58|issue=3|pages=377–441|doi=10.1137/130912839|issn=0036-1445|hdl=11585/586011|hdl-access=free}} Iterative methods can also be used to directly construct low rank approximations to $X$ when solving $AX-XB\; =\; C$.

{{Reflist}}

{{Numerical linear algebra}}

{{DEFAULTSORT:Bartels-Stewart algorithm}}

Category:Algorithms

Category:Control theory

Category:Matrices (mathematics)

Category:Numerical linear algebra