Bartels–Stewart algorithm

The Hessenberg–Schur algorithm

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

Software and implementation

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.

Alternative approaches

For large systems, the ${\displaystyle \mathcal{O}(m^3+n^3)}$ cost of the Bartels–Stewart algorithm can be prohibitive. When ${\displaystyle A}$ and ${\displaystyle 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. Iterative methods can also be used to directly construct low rank approximations to ${\displaystyle X}$ when solving ${\displaystyle AX-XB=C}$.