Bartels–Stewart algorithm

E695944

algorithm in numerical linear algebra matrix equation solver numerical algorithm

The Bartels–Stewart algorithm is a numerical linear algebra method that efficiently solves certain matrix equations, particularly Sylvester and Lyapunov equations, using Schur decompositions.

Try in SPARQL Jump to: Statements Referenced by

Statements (50)

Predicate	Object
instanceOf	algorithm in numerical linear algebra ⓘ matrix equation solver ⓘ numerical algorithm ⓘ
advantage	avoids explicit Kronecker product formulation ⓘ reduces Sylvester equation to sequence of simpler triangular problems ⓘ
appliesTo	A X A^T - X + Q = 0 ⓘ AX + X B^T + Q = 0 ⓘ AX + XB = C ⓘ
basedOn	back substitution ⓘ triangular matrix equations ⓘ
category	direct method for matrix equations ⓘ
complexity	O(n^3) for n×n matrices (up to constants depending on sizes) ⓘ
field	computational mathematics ⓘ numerical linear algebra ⓘ
implementedIn	LAPACK NERFINISHED ⓘ MATLAB lyap function ⓘ SciPy scipy.linalg.solve_continuous_lyapunov ⓘ SciPy scipy.linalg.solve_discrete_lyapunov NERFINISHED ⓘ SciPy scipy.linalg.solve_sylvester NERFINISHED ⓘ
input	matrix A ⓘ matrix B ⓘ matrix C ⓘ
namedAfter	George W. Stewart NERFINISHED ⓘ Richard H. Bartels NERFINISHED ⓘ
originalAuthors	G. W. Stewart NERFINISHED ⓘ R. H. Bartels NERFINISHED ⓘ
originalJournal	Communications of the ACM NERFINISHED ⓘ
originalPublication	Solution of the matrix equation AX + XB = C ⓘ
output	matrix X ⓘ
property	backward stable in typical implementations ⓘ exploits triangular structure ⓘ numerically stable ⓘ
relatedTo	Hessenberg–Schur method NERFINISHED ⓘ Lyapunov equation solvers in control libraries ⓘ
requirement	matrices A and B have no common eigenvalues for unique solution of Sylvester equation ⓘ
solves	Sylvester equation NERFINISHED ⓘ continuous Lyapunov equation ⓘ discrete Lyapunov equation ⓘ
step	compute Schur decomposition of A ⓘ compute Schur decomposition of B ⓘ solve resulting triangular Sylvester equations ⓘ transform Sylvester equation into Schur basis ⓘ
usedIn	control theory ⓘ model reduction ⓘ solution of Riccati equations via Lyapunov subproblems ⓘ stability analysis ⓘ
uses	Schur decomposition NERFINISHED ⓘ complex Schur decomposition ⓘ real Schur decomposition NERFINISHED ⓘ
yearIntroduced	1972 ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Lyapunov equation → solvedBy → Bartels–Stewart algorithm ⓘ