Асимптоти c Сложность b.transpose () * A ^ (- 1) * b

Question

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;
}

очевидно, этот код имеет асимптотику c сложность O (n ^ 3) с аргументацией:

Асимптотика c сложность равна O (n ^ 3) , потому что код решает $ n $ линейных систем уравнений с (nxn) верхней треугольной матрицей системы. Это составляет $ n $ обратных замен, каждая из которых стоит O (n ^ 2) операций.

Я бы подумал: - Транспонирование может стоить n операций. Хотя мы, вероятно, можем пренебречь этим, так как мы просто переключаемся со строки на col Major или наоборот. (Понятия не имею, что на самом деле здесь делает Эйген). Затем мы получаем верхнюю три angular часть А. Это тоже «бесплатно». Затем мы получаем обратное значение этой верхней три angular части A. Это стоит нам $ n ^ 2 $. Затем мы в основном вычисляем b.transpose () * A ^ (- 1) b, который снова равен n * 1009. * n

Итак, в целом мы получаем O (n * n ^ 2 * n) = O (n4)

Что не так с моими рассуждениями?

Answer 1

Да, сложность этого кода равна O (n ^ 3), потому что вычисление обратной матрицы angular матрицы 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) c. Не нужно говорить, что эта новая версия будет значительно быстрее!