b.transpose()*A^(-1)*b 的渐近复杂度
Asymptotic Complexity of b.transpose()*A^(-1)*b
double sumtrv1(const Eigen::MatrixXd &A, const Eigen::VectorXd &b) {
const int n = A.cols();
assert((A.rows() == n) && (b.size() == n));
return b.transpose() *
A.triangularView<Eigen::Upper()>.solve(
Eigen::MatrixXd::Identity(n,n)) *
b;
}
很明显，这段代码的渐近复杂度为 O(n^3)，推理如下：
The asymptotic complexity is O(n^3), because the code is solving $n$
linear systems of equations with an (n x n) upper triangular
system matrix. This amounts to $n$ backward substitutions, each of
which costs O(n^2) operations.
我的想法是：
- 转置可能会花费 n 个操作。尽管我们可能会忽略它，因为我们只是从行切换到主列，反之亦然。 （不知道 Eigen 在这里真正做了什么）
然后我们得到 A 的上三角部分。这也是 "free"。
然后我们得到 A 的这个上三角部分的倒数。这花费了我们 $n^2$
然后我们基本上计算 b.transpose()*A^(-1)b 又是 nn
总的来说，我们得到 O(n*n^2*n)=O(n4)
我的推理有什么问题？
是的，这段代码的复杂度是 O(n^3)，因为计算三角矩阵 A 的逆是 O(n^3)：你有 n 向后替换（单位矩阵的 n 列中的每一列）和每个向后替换成本 O(n^2)。然后你还有一个矩阵向量乘积成本为 O(n^2)，一个内积成本为 O(n)，但与 O(n^3) 相比，这两个操作可以忽略不计，整体复杂度为 O(n^ 3).
也就是说，您可以重写表达式以获得 O(n^2) 复杂度：
b' * triu(A)^-1 * I * b = b' * triu(A)^-1 * b
在 Eigen 语言中，你得到：
return b.transpose() * A.triangularView<Eigen::Upper()>.solve(b);
你现在有一个后向代入 O(n^2) 加上一个内积 O(n)，产生 O(n^2) 渐近复杂度。不用说这个新版本会快得多！
double sumtrv1(const Eigen::MatrixXd &A, const Eigen::VectorXd &b) {
const int n = A.cols();
assert((A.rows() == n) && (b.size() == n));
return b.transpose() *
A.triangularView<Eigen::Upper()>.solve(
Eigen::MatrixXd::Identity(n,n)) *
b;
}
很明显，这段代码的渐近复杂度为 O(n^3)，推理如下：
The asymptotic complexity is O(n^3), because the code is solving $n$ linear systems of equations with an (n x n) upper triangular system matrix. This amounts to $n$ backward substitutions, each of which costs O(n^2) operations.
我的想法是： - 转置可能会花费 n 个操作。尽管我们可能会忽略它，因为我们只是从行切换到主列，反之亦然。 （不知道 Eigen 在这里真正做了什么） 然后我们得到 A 的上三角部分。这也是 "free"。 然后我们得到 A 的这个上三角部分的倒数。这花费了我们 $n^2$ 然后我们基本上计算 b.transpose()*A^(-1)b 又是 nn
总的来说，我们得到 O(n*n^2*n)=O(n4)
我的推理有什么问题？
是的，这段代码的复杂度是 O(n^3)，因为计算三角矩阵 A 的逆是 O(n^3)：你有 n 向后替换（单位矩阵的 n 列中的每一列）和每个向后替换成本 O(n^2)。然后你还有一个矩阵向量乘积成本为 O(n^2)，一个内积成本为 O(n)，但与 O(n^3) 相比，这两个操作可以忽略不计，整体复杂度为 O(n^ 3).
也就是说，您可以重写表达式以获得 O(n^2) 复杂度：
b' * triu(A)^-1 * I * b = b' * triu(A)^-1 * b
在 Eigen 语言中，你得到：
return b.transpose() * A.triangularView<Eigen::Upper()>.solve(b);
你现在有一个后向代入 O(n^2) 加上一个内积 O(n)，产生 O(n^2) 渐近复杂度。不用说这个新版本会快得多！