Существуют ли параллельные матричные алгоритмы возведения в степень, которые более эффективны, чем последовательное умножение?

11

Требуется найти степень (целое положительное число) матрицы действительных чисел. Существует множество эффективных алгоритмов умножения матриц (например, некоторые параллельные алгоритмы - Кэннона, DNS ), но существуют ли алгоритмы, предназначенные именно для определения мощности матрицы и более эффективные, чем последовательное выполнение умножения матриц? Я особенно заинтересован в параллельных алгоритмах.

Мистеру
источник
1
Что вы пробовали? Где вы застряли? Какие исследования вы провели? Помимо названия, где вопрос? Для версии решения вашей проблемы (из заголовка) ответ «да», но вы уже знаете это, верно?
Зло
2
@TomR Этот вопрос, вероятно, вас интересует
adrianN
1
Может как то так ? Или вы ищете что-то еще? Каковы размеры и полномочия в вашем приложении?
Зло
1
Вы можете вычислить n-ую степень с меньшим, чем n-1 умножением, когда n ≥ 4. Для больших матриц, как правило, целесообразно найти наименьшее возможное количество умножений (например, существует простой метод для вычисления n ^ 15 с 6 умножения, но это можно сделать с помощью 5). Затем вы можете применить тот же принцип, чтобы найти наименьшее количество последовательных умножений, которое будет сложнее.
gnasher729
1
Вы также должны учитывать количество параллелизма, доступного для вас. «Параллелизм» - это использование ресурсов, которые в противном случае были бы неиспользованными. Если реализация умножения матриц уже может эффективно использовать все доступные ресурсы, то для вычисления степеней матриц использовать нечего.
gnasher729

Ответы:

5

Если у вас есть несколько процессоров, которые могут работать параллельно, то вы можете рассчитать любую мощность до мощности (2 ^ k) за k шагов. Например: чтобы вычислить , вы рассчитываете:M15

Этап 1: Рассчитать M2

Этап 2: Рассчитать и M 4 = M 2M 2M3=M2MM4=M2M2

Этап 3: вычислить и M 8 = M 4M 4M7=M4M3M8=M4M4

Этап 4: Расчет M15=M8M7

Это на одно умножение больше, чем вычисление в трех умножениях и повышение M 5 до третьей степени в двух других умножениях, но должно быть быстрее, если у вас есть два процессора. Для произвольной высокой мощности вам понадобится больше процессоров.M5M5

Если вы используете алгоритм перебора для умножения, умножая строку на столбец, вы можете сэкономить некоторое время, рассчитав одну строку продукта, а затем сразу же использовать эту строку для следующего продукта. Это помогло бы при расчете , где можно начать вычисление M 3 , как только первый ряд M 2 был рассчитан; это не будет то , что полезно с M 4 , так как нам нужны обе строки и столбцы М 2 . Для больших держав вы, вероятно, могли бы определить, какие полномочия рассчитывать.M3M3M2M4M2

И после публикации этого становится очевидным , что вы можете использовать несколько процессоры очень легко: Вы начинаете путем вычисления первой строки . Когда у вас есть этот ряд, у вас есть вся информация, необходимая для вычисления первой строки M 3 = M 2M , поэтому вы рассчитываете второй ряд M 2 и первый ряд M 3 параллельно. Затем вы можете рассчитать третий ряд М 2 , второй ряд М 3 и первый ряд М 4 параллельно и так далее.M2знак равноM*MM3знак равноM2*MM2M3M2M3M4

Это будет выполнять намного больше операций, чем необходимо (например, 14 умножений матриц для вместо минимальных 5 или 6 четырехэтапного метода). Если мощность невелика по сравнению с количеством процессоров, это все равно будет быстрее. Но вычисление M 1000 с четырьмя процессорами с использованием этого метода будет неэффективным; сделать это оптимальным способом было бы интересной проблемой.M15M1000

Комбинирование подходов: например, используя четыре процессора, вы можете вычислять AB, ABC, ABCD и ABCDE практически параллельно, вычисляя каждый продукт по одной строке за раз. Это позволяет рассчитать все четыре от до M 5, используя четыре процессора примерно за одно время, как один продукт с одним процессором.M2M5

Учитывая эти четыре результата и оригинальный M, вы можете вычислить четыре из матриц до М 25 в то же время снова, при условии , что матрицы в большинстве пяти держав друг от друга. Таким образом , каждая мощность до М 25 может быть рассчитана примерно в два раз времени одного процессора матричного продукта.M6M25M25

С помощью этих вычисленных матриц все матрицы до и еще несколько до M 125 можно рассчитать в три раза за время одного матричного продукта, если доступны четыре процессора. С k процессорами это должно возрасти как минимум до мощности k ( k + 1 ) 2 .M108M125К(К+1)2

gnasher729
источник
4

Существует два уровня, с помощью которых можно анализировать параллельные ускорения с помощью возведения в степень матрицы: «макро-алгоритмический» уровень, который решает, какие матрицы умножать, и «микро-алгоритмический» уровень, где вы можете ускорить сами умножения с помощью параллелизма.

Для последнего Википедия предполагает, что для умножения матрицы на n мы можем достичь сложности O ( log 2 ( n ) ) теоретически с неограниченным числом процессоров или O ( n ) с более реалистичным параллельным алгоритмом.NNО(журнал2(N))О(N)

(Примечание: страница википедии предназначена для общих матриц-вычислений. Я не уверен, что это можно распараллелить еще дальше, используя информацию о том, что мы возводим в квадрат матрицу.)

AмA

AКО(журнал(К))

Вопрос в том, можем ли мы победить это параллелизмом? Я утверждаю, что ответ - нет.

Простая причина заключается в том, что возведение в степень посредством возведения в квадрат является по сути алгоритмом динамического программирования; это позволяет вам пропустить всю работу, повторно используя подрезультаты, но это, в свою очередь, создает зависимость данных, которая запрещает параллелизм. Если мы избавимся от зависимости от данных, но мы также значительно увеличим объем работы, которую мы должны сделать.

К

A1A2A3A4A5,,,AК

К2

(A1A2)(A3A4)(A5A6),,,(AК-1AК)

КО(журнал(К))

Однако, если бы мы выполнили возведение в степень таким образом, это выглядело бы так:

(AA)(AA)(AA),,,(AA)

A2

AКNNAО(журнал2(N)журнал(К))О(Nжурнал(К))

Курт Мюллер
источник
3

мжурналм2м

Aзнак равноSΛS-1Aмзнак равноSΛмS-1
мО(1)м
nbubis
источник