Bartels–Stewart algorithm: Difference between revisions

Revision as of 09:37, 27 September 2020

Latest revision as of 21:01, 14 April 2025

(3 intermediate revisions by 2 users not shown)

Line 1:

{{short description|Algorithm in numerical linear algebra}}

In [[numerical linear algebra]], the '''Bartels–Stewart algorithm''' is used to numerically solve the [[Sylvester equation|Sylvester matrix equation]] <math> AX - XB = C</math>. Developed by R.H. Bartels and G.W. Stewart in 1971,<ref name=":0">{{Cite journal|last1=Bartels|first1=R. H.|last2=Stewart|first2=G. W.|date=1972|title=Solution of the matrix equation AX + XB = C [F4]|journal=Communications of the ACM|volume=15|issue=9|pages=820–826|doi=10.1145/361573.361582|issn=0001-0782|doi-access=free}}</ref> it was the first [[numerical stability|numerically stable]] method that could be systematically applied to solve such equations. The algorithm works by using the [[Schur decomposition|real Schur decompositions]] of <math>A</math> and <math>B</math> to transform <math> AX - XB = C</math> into a triangular system that can then be solved using forward or backward substitution. In 1979, [[Gene H. Golub|G. Golub]], [[Charles F. Van Loan|C. Van Loan]] and S. Nash introduced an improved version of the algorithm,<ref name=":1">{{Cite journal|last1=Golub|first1=G.|last2=Nash|first2=S.|last3=Loan|first3=C. Van|date=1979|title=A Hessenberg–Schur method for the problem AX + XB= C|journal=IEEE Transactions on Automatic Control|volume=24|issue=6|pages=909–913|doi=10.1109/TAC.1979.1102170|issn=0018-9286|hdl=1813/7472|hdl-access=free}}</ref> known as the Hessenberg–Schur algorithm. It remains a standard approach for solving [[Sylvester equation| Sylvester equations]] when <math>X</math> is of small to moderate size.

== The algorithm ==

Line 19:

: <math>(R - s_{kk}I)y_k = f_{k} + \sum_{j = k+1}^n s_{kj}y_j,</math>

where <math>y_k</math> is the <math>k</math>th column of <math>Y</math>. When <math>s_{k-1, k} \neq 0</math>, columns <math>[ y_{k-1} \mid y_{k}]</math> should be concatenated and solved for simultaneously.

4. Set <math>X = UYV^T.</math>

Line 36:

== Alternative approaches ==

For large systems, the <math>\mathcal{O}(m^3 + n^3)</math> cost of the Bartels–Stewart algorithm can be prohibitive. When <math>A</math> and <math>B</math> 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 method|Krylov subspace]] iterations, methods based on the [[Alternating direction implicit method|alternating direction implicit]] (ADI) iteration, and hybridizations that involve both projection and ADI.<ref>{{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}}</ref> Iterative methods can also be used to directly construct [[Low-rank approximation|low rank approximations]] to <math>X</math> when solving <math>AX-XB = C</math>.

== References ==

Line 46:

[[Category:Algorithms]]

[[Category:Control theory]]

[[Category:Matrices (mathematics)]]

[[Category:Numerical linear algebra]]