Количество флопов в коде Matlab Gaussian Elimination

Мне трудно понять, почему этот код Matlab для выполнения исключения Гаусса без поворота с использованием факторизации LU занимает (2/3) * n^3 флопс. (FLOPs: операции с плавающей запятой и not FLOPS: операции с плавающей запятой в секунду)

function x = GaussianElimination(A,b)

n = length(b);
for k = 1:n-1
    for i = k+1:n
        mult = A(i,k)/A(k,k);
        A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);
        b(i) = b(i) - mult*b(k);
    end
end

x = zeros(n,1);
x(n) = b(n)/A(n,n);

for k = n-1:-1:1
    x(k) = (b(k) - A(k,k+1:n)*x(k+1:n))/A(k,k);
end

end

Если бы кто-нибудь мог объяснить мне, как подсчитываются флопы для тех вложенных циклов, которые начинаются с k+1, я был бы признателен.

PS: я не говорю здесь об алгоритмической сложности.


matlab flops time-complexity linear-algebra linear-equation
person hazer_drum    schedule 12.10.2013    source источник
comment
Вы говорите об алгоритмической сложности? Я понимаю термин flops как аббревиатуру от операций с плавающей запятой в секунду, обычно выражаемую в мегафлопах, гигафлопсах, терафлопсах и т. д. Но здесь кажется, что вы спрашиваете о сложности алгоритма, который я никогда не видел выражается во флопах. ???   -  person Bob Jarvis - Reinstate Monica    schedule 13.10.2013
comment
Нет, флопы = операции с плавающей запятой. Вот почему это сбивает меня с толку, потому что это не считается алгоритмической сложностью.   -  person hazer_drum    schedule 13.10.2013
comment
Очевидно, инструкции по информатике прошли мимо меня, и мои знания больше не пригодятся. Удачи.   -  person Bob Jarvis - Reinstate Monica    schedule 13.10.2013
comment
После дополнительного поиска выясняется, что FLOP и FLOPS — это две разные аббревиатуры, поэтому я обновил свой вопрос.   -  person hazer_drum    schedule 13.10.2013
comment
Да, FLOPS — это количество операций с плавающей запятой. См. нижнюю часть старого сообщения основателя MathWorks. Клив Молер. Сказанное еще более актуально сегодня с JIT-ускорением. Вопрос в том, хотите ли вы подсчитать истинное количество флопов, выполненных вашим компьютером, или число, которое будет использоваться человеком, вручную реализующим алгоритм, такой как исключение Гаусса.   -  person horchler    schedule 13.10.2013
comment
Я даже не уверен, что (2/3) * n^3 флоп для компьютера или человека, но я бы предположил, что это для человека?   -  person hazer_drum    schedule 13.10.2013

Ответы (1)


arrow_upward
2
arrow_downward

Я, наконец, понял это сам.

FLOP подсчитывается немного иначе, чем алгоритмическая сложность, в том смысле, что члены более низкого порядка по-прежнему игнорируются, но коэффициент перед членом высшего порядка имеет значение.

В этом конкретном примере, поскольку мы игнорируем члены более низкого порядка, мы рассматриваем только +, -, *, / операций в тройном вложенном цикле и игнорируем другие операции с плавающей запятой в остальной части алгоритма. то есть следующая строка

    A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);
  • первый цикл работает от 1 до n
  • второй цикл проходит от k до n
  • третий цикл выполняется от k до n (неявно в коде Matlab с использованием :)

Таким образом, эта строка выполняется почти n^3 раза и ровно n*n + (n-1)*(n-1) + ... + 2*2 + 1*1 раз, что эквивалентно (1/3)*n^3 флопам при игнорировании членов более низкого порядка.

Однако в этой строке есть две операции с плавающей запятой: операция - и операция *.

Следовательно, это дает (2/3)*n^3.

person hazer_drum    schedule 15.10.2013