Fast algorithms for the Sylvester equation AX-XBT=C
Fast algorithms for the Sylvester equation AX-XBT=C
复制标题
DOI：
10.1016/s0304-3975(00)00322-4
复制
发表时间：
2001-05-28
影响因子：
1.1
通讯作者：
Kirrinnis, P
中科院分区：
文献类型：
--
作者：
Kirrinnis, P
对于任意域\(F\)上给定的矩阵，\(A\in F^{m\times m}\)，\(B\in F^{n\times n}\)，\(C\in F^{m\times n}\)，矩阵方程\(AX - XB^{T}=C\)有唯一解\(X\in F^{m\times n}\)当且仅当\(A\)和\(B\)的谱不相交。我们描述一种算法，对于\(m,n\leq N\)，该算法在域\(F\)中用\(O(N^{\beta}\cdot\log N)\)次算术运算计算解\(X\)，其中\(\beta>2\)满足\(M\times M\)矩阵可以用\(O(M^{\beta})\)次算术运算相乘，例如\(\beta = 2.376\)。在此之前，似乎已知的最好运算次数界是\(O(m^{3}\cdot n^{3})\)次算术运算。数值分析的现有技术水平是\(O(n^{3}+m^{3})\)次浮点运算，但这些算法（由巴特尔斯/斯图尔特以及戈卢布/纳什/范洛恩提出）涉及舒尔分解，即它们计算\(A\)和\(B\)中至少一个的特征值，因此不能推广到一般的域\(F\)。©2001爱思唯尔科学出版社。保留所有权利。
For given matrices Al is an element of F-m X m, B is an element of F-n X n , and C is an element of F-m X n over an arbitrary field F, the matrix equation AX - XBT = C has a unique solution X is an element of F-m X n if and only if A and B have disjoint spectra. We describe an algorithm that computes the solution X for m, n less than or equal toN with O(N-beta . logN) arithmetic operations in F, where beta > 2 is such that M X M matrices can be multiplied with O(M-beta) arithmetic operations, e.g., beta = 2.376. It seems that before no better bound than O(m(3) . n(3)) arithmetic operations was known. The state of the art in numerical analysis is O(n(3) + m(3)) flops, but these algorithms (due to Bartels/Stewart and Golub/Nash/van Loan) involve Schur decompositions, i.e., they compute the eigenvalues of at least one of A and B, and can hence not be transferred for general F. (C) 2001 Elsevier Science B.V. AH rights reserved.