Более быстрые вычисления в стиле прогнозируемой нормы (квадратичная форма, метрическая матрица ...) - PullRequest
Новая
       12

Более быстрые вычисления в стиле прогнозируемой нормы (квадратичная форма, метрическая матрица ...)

4 голосов
/ 03 апреля 2010

Мне нужно выполнить множество оценок в форме 

X(:,i)' * A * X(:,i)   i = 1...n

где X (:, i) - вектор, а A - симметричная матрица. Якобы я могу сделать это в цикле 

for i=1:n
    z(i) = X(:,i)' * A * X(:,i)
end

, который медленный, или векторизация как 

z = diag(X' * A * X)

, что недопустимо тратит ОЗУ, когда в X много столбцов. В настоящее время я компромисс на 

Y = A * X
for i=1:n
    z(i) = Y(:,i)' * X(:,i)
end

, который немного быстрее / легче, но все же кажется неудовлетворительным.

Я надеялся, что может быть какая-то идиома или трюк с matlab / scilab для более эффективного достижения этого результата?

Ответы [ 3 ]

3 голосов
/ 03 апреля 2010

Попробуйте это в MATLAB: 

z = sum(X.*(A*X));

Это дает результаты, эквивалентные предложению Федерико с использованием функции DOT , но должно выполняться немного быстрее. Это потому, что функция DOT внутренне вычисляет результат так же, как я делал выше, используя функцию SUM . Тем не менее, DOT также имеет дополнительные проверки входных аргументов и дополнительные вычисления для случаев, когда вы имеете дело с комплексными числами, что является дополнительными издержками, которые вы, вероятно, не хотите или не нуждаетесь.

Примечание по вычислительной эффективности:

Несмотря на то, что разница во времени между тем, как быстро выполняются два метода, небольшая, если вы собираетесь выполнить операцию много раз, она начнет складываться. Чтобы проверить относительные скорости, я создал две матрицы случайных значений размером 100 на 100 и рассчитал время для двух методов на несколько прогонов, чтобы получить среднее время выполнения: 

    METHOD        AVERAGE EXECUTION TIME
--------------------------------------------
Z = sum(X.*Y);        0.0002595 sec
Z = dot(X,Y);         0.0003627 sec

Использование SUM вместо DOT , следовательно, сокращает время выполнения этой операции примерно на 28% для матриц с примерно 10 000 элементов. Чем больше матрицы, тем более незначительной будет разница между этими двумя методами.

Подводя итог, если это вычисление представляет собой существенное узкое место в том, как быстро работает ваш код, я бы выбрал решение, использующее SUM . В противном случае, любое решение должно быть в порядке.

3 голосов
/ 03 апреля 2010

Попробуйте это: 

z = dot(X, A*X)

У меня нет Matlab для тестирования, но он работает в Octave, поэтому я ожидаю, что Matlab будет иметь аналогичную функцию dot().

С помощью Октавы: 

  -- Function File:  dot (X, Y, DIM)
     Computes the dot product of two vectors. If X and Y are matrices,
     calculate the dot-product along the first non-singleton dimension.
     If the optional argument DIM is given, calculate the dot-product
     along this dimension.
1 голос
/ 03 апреля 2010

Для полноты, gnovice ответ в Scilab будет 

z = sum(X .* Y, 1)'
...