如何有效地反转ķ⊗ M+一世吨⊗ ΣK⊗M+IT⊗Σ?

计算科学 线性代数 效率
2021-11-29 09:29:47

我正在寻找一种有效反转的倒数是维度的单位矩阵,是对角矩阵,沿主对角线只有正元素。

KM+ITΣ
M,KITTΣ

如果我只有,我只会做但是,对于额外的术语,我看不出如何有效地反转它。KMK1M1

2个回答

通常没有办法计算克罗内克积之和的倒数。但是,假设有一个共同因素,假设这里的和你的总和是IT

A=KIT+ITΣ

求解线性系统就等同于求解Sylvester 方程因此,解决您的问题的一种方法可能是尝试将作为一个共同因素引入AIT

(IM)1(KM+ITΣ)=KIT+ITΣM1

您可以在此维基百科页面上找到 Kronecker 产品的有用公式列表

扩展我之前的评论。有有效的算法来解决以下形式的线性系统

(KM+ITΣ)vec(X)=vec(B),
所以在实践中你可以只使用那些而不是显式的逆。在某些领域,显式逆被高估了。:)

诀窍是这些线性系统等价于矩阵方程

MXK+ΣXIT=B,
这被称为广义西尔维斯特方程

有一些有效的算法可以解决这些方程O(larger_dimension_of_B3) 例如,请参阅https://dl.acm.org/citation.cfm?id=146929https://people.cs.umu.se/isak/recsy/基本上,这个想法是使用两个 QZ 分解同时将所有系数减少为三角形形式,然后可以通过反向替换来求解得到的系统。

在您的情况下,您可以通过利用其中一个系数是一个单位这一事实来稍微简化一下。ΣX=Y, 要得到

(MΣ1)YK+Y=B,
这是另一个经典矩阵方程(离散时间 Sylvester 方程),可以用稍微快一点的算法求解,该算法也在 Matlab 单线中实现为Y = dlyap(-M/Sigma, K', -B)不幸的是,据我所知,在 Numpy/Scipy 中没有此变体的求解器;它只有一个经典西尔维斯特方程的求解器,您可以将其与@Reid.Atcheson 的答案中描述的方法一起使用。

在这种情况下MΣ1K具有单位圆内的所有特征值,您也可以将此方程的封闭形式的解写为无限级数

Y=k=0(MΣ1)kB(K)k.
这是从应用诺依曼级数得出的(IM)1=k=0Mk到 Kroneckerized 矩阵(IT2K(MΣ1)).