计算科学 - 是否有计算以下表达式的改进方法？ - 吾爱随笔录

计算科学优化算法表现矩阵复杂

2021-12-02 12:12:31

给定一个对称矩阵 $Y \in \mathbb{R}^{n \times n}$ , 和任意矩阵 $X \in \mathbb{R}^{n \times n}$ , 和一个向量 $v \in \mathbb{R}^{n \times 1}$ , 是否可以计算以下表达式 $O(n^2)$ 时间？

d i a g (X^{T} Y X) \cdot v

$diag(X^TYX) \cdot v$

在哪里 $diag(X)$ 返回一个 $n \times n$ 矩阵，其主要对角元素等于 $X$ 和非对角元素等于 0，和 $X^T$ 是转置 $X$ .

1个回答

让我试着帮忙，但如果我错了，请纠正我，因为我只是把它从我的帽子里拉出来：

我将扩展计算以帮助查看正在发生的事情。

让我们写 $A = (X^TY)$

所以你想计算 $\sum_k{a_{ik}x_{ki}\nu_i}$ 对于每个 $i$

和 $a_{ik}=\sum_l{x_{li}y_{lk}}$

$\left(diag(X^TYX)⋅v\right)_i =\sum_k{\sum_l{x_{li}y_{lk}}x_{ki}\nu_i}$ 这是 $O(n^3)$ .

现在让我们提出假设：由于 $Y$ 是对称的， $y_{lk}=y_{kl}$ . 总之，只有产品 $x_{li}x_{ki}$ 这也是关于对称的 $k$ 和 $l$ .

所以 $\left(diag(X^TYX)⋅v\right)_i = 2\times\sum_k{\sum_{l>k}{x_{li}y_{lk}}x_{ki}\nu_i} + \sum_{k}{x_{ki}y_{kk}x_{ki}\nu_i}$

那是 $n$ 次 $\frac{n(n+1)}{2}$ 计算。所以你可以将计算除以几乎 $2$ 但不是 $n$ .

其它你可能感兴趣的问题