7

我有两个方阵 A 和 B。A 是对称的,B 是对称正定的。我想计算 $trace(AB^{-1})$。现在,我计算 B 的 Cholesky 分解,在方程 $A=CB$ 中求解 C,并对对角线元素求和。

有没有更有效的处理方式?

我打算使用 Eigen。如果矩阵稀疏(A 通常可以是对角线,B 通常是带对角线),您能否提供一个实现?

4

2 回答 2

5

如果B是稀疏的,它可能是有效的(即 O(n),假设 的良好条件数)B解决x_i

B x_i = a_i

(示例共轭梯度代码在 Wikipedia 上给出)。取a_i的列向量A,得到B^{-1} AO(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))。

于 2011-09-22T04:27:37.477 回答
1

如果广义特征值的计算效率更高,则可以计算广义特征值,A*v = lambda* B *v然后对所有 lambda 求和。

于 2011-09-22T01:39:50.560 回答