In
numerical linear algebra
Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathematics ...
, the Bartels–Stewart algorithm is used to numerically solve the
Sylvester matrix equation . Developed by R.H. Bartels and G.W. Stewart in 1971,
it was the first
numerically stable
In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algor ...
method that could be systematically applied to solve such equations. The algorithm works by using the
real Schur decompositions of
and
to transform
into a triangular system that can then be solved using forward or backward substitution. In 1979,
G. Golub,
C. Van Loan and S. Nash introduced an improved version of the algorithm,
known as the Hessenberg–Schur algorithm. It remains a standard approach for solving
Sylvester equations when
is of small to moderate size.
The algorithm
Let
, and assume that the eigenvalues of
are distinct from the eigenvalues of
. Then, the matrix equation
has a unique solution. The Bartels–Stewart algorithm computes
by applying the following steps:
1.Compute the
real Schur decompositions
:
:
The matrices
and
are block-upper triangular matrices, with diagonal blocks of size
or
.
2. Set
3. Solve the simplified system
, where
. This can be done using forward substitution on the blocks. Specifically, if
, then
:
where
is the
th column of
. When
, columns