我有两个方阵 A 和 B。A 是对称的,B 是对称正定的。我想计算 $trace(AB^{-1})$。现在,我计算 B 的 Cholesky 分解,在方程 $A=CB$ 中求解 C,并对对角线元素求和。
有没有更有效的处理方式?
我打算使用 Eigen。如果矩阵稀疏(A 通常可以是对角线,B 通常是带对角线),您能否提供一个实现?
我有两个方阵 A 和 B。A 是对称的,B 是对称正定的。我想计算 $trace(AB^{-1})$。现在,我计算 B 的 Cholesky 分解,在方程 $A=CB$ 中求解 C,并对对角线元素求和。
有没有更有效的处理方式?
我打算使用 Eigen。如果矩阵稀疏(A 通常可以是对角线,B 通常是带对角线),您能否提供一个实现?
如果B
是稀疏的,它可能是有效的(即 O(n),假设 的良好条件数)B
解决x_i
B x_i = a_i
(示例共轭梯度代码在 Wikipedia 上给出)。取a_i
的列向量A
,得到B^{-1} A
O(n^2) 中的矩阵。然后您可以对对角线元素求和以获得迹线。通常,执行这种稀疏逆乘法比获得完整的特征值集更容易。为了比较,Cholesky 分解是 O(n^3)。(请参阅下面关于 Cholesky 的 Darren Engwirda 的评论)。
如果您只需要跟踪的近似值,您实际上可以通过平均将成本降低到 O(qn)
r^T (A B^{-1}) r
在q
随机向量r
上。通常q << n
. 这是一个无偏估计,前提是随机向量的分量r
满足
< r_i r_j > = \delta_{ij}
其中< ... >
表示 的分布的平均值r
。例如,分量r_i
可以是具有单位方差的独立高斯分布。或者它们可以从 +-1 中统一选择。通常,轨迹的比例为 O(n),轨迹估计中的误差的比例为 O(sqrt(n/q)),因此相对误差的比例为 O(sqrt(1/nq))。
如果广义特征值的计算效率更高,则可以计算广义特征值,A*v = lambda* B *v
然后对所有 lambda 求和。