Требуется найти степень (целое положительное число) матрицы действительных чисел. Существует множество эффективных алгоритмов умножения матриц (например, некоторые параллельные алгоритмы - Кэннона, DNS ), но существуют ли алгоритмы, предназначенные именно для определения мощности матрицы и более эффективные, чем последовательное выполнение умножения матриц? Я особенно заинтересован в параллельных алгоритмах.
11
Ответы:
Если у вас есть несколько процессоров, которые могут работать параллельно, то вы можете рассчитать любую мощность до мощности (2 ^ k) за k шагов. Например: чтобы вычислить , вы рассчитываете:M15
Этап 1: РассчитатьM2
Этап 2: Рассчитать и M 4 = M 2 ∗ M 2M3=M2∗M M4=M2∗M2
Этап 3: вычислить и M 8 = M 4 ∗ M 4M7=M4∗M3 M8=M4∗M4
Этап 4: РасчетM15=M8∗M7
Это на одно умножение больше, чем вычисление в трех умножениях и повышение M 5 до третьей степени в двух других умножениях, но должно быть быстрее, если у вас есть два процессора. Для произвольной высокой мощности вам понадобится больше процессоров.M5 M5
Если вы используете алгоритм перебора для умножения, умножая строку на столбец, вы можете сэкономить некоторое время, рассчитав одну строку продукта, а затем сразу же использовать эту строку для следующего продукта. Это помогло бы при расчете , где можно начать вычисление M 3 , как только первый ряд M 2 был рассчитан; это не будет то , что полезно с M 4 , так как нам нужны обе строки и столбцы М 2 . Для больших держав вы, вероятно, могли бы определить, какие полномочия рассчитывать.M3 M3 M2 M4 M2
И после публикации этого становится очевидным , что вы можете использовать несколько процессоры очень легко: Вы начинаете путем вычисления первой строки . Когда у вас есть этот ряд, у вас есть вся информация, необходимая для вычисления первой строки M 3 = M 2 ∗ M , поэтому вы рассчитываете второй ряд M 2 и первый ряд M 3 параллельно. Затем вы можете рассчитать третий ряд М 2 , второй ряд М 3 и первый ряд М 4 параллельно и так далее.M2= М* M M3= М2* M M2 M3 M2 M3 M4
Это будет выполнять намного больше операций, чем необходимо (например, 14 умножений матриц для вместо минимальных 5 или 6 четырехэтапного метода). Если мощность невелика по сравнению с количеством процессоров, это все равно будет быстрее. Но вычисление M 1000 с четырьмя процессорами с использованием этого метода будет неэффективным; сделать это оптимальным способом было бы интересной проблемой.M15 M1000
Комбинирование подходов: например, используя четыре процессора, вы можете вычислять AB, ABC, ABCD и ABCDE практически параллельно, вычисляя каждый продукт по одной строке за раз. Это позволяет рассчитать все четыре от до M 5, используя четыре процессора примерно за одно время, как один продукт с одним процессором.M2 M5
Учитывая эти четыре результата и оригинальный M, вы можете вычислить четыре из матриц до М 25 в то же время снова, при условии , что матрицы в большинстве пяти держав друг от друга. Таким образом , каждая мощность до М 25 может быть рассчитана примерно в два раз времени одного процессора матричного продукта.M6 M25 M25
С помощью этих вычисленных матриц все матрицы до и еще несколько до M 125 можно рассчитать в три раза за время одного матричного продукта, если доступны четыре процессора. С k процессорами это должно возрасти как минимум до мощности k ( k + 1 ) 2 .M108 M125 к ( к + 1 )2
источник
Существует два уровня, с помощью которых можно анализировать параллельные ускорения с помощью возведения в степень матрицы: «макро-алгоритмический» уровень, который решает, какие матрицы умножать, и «микро-алгоритмический» уровень, где вы можете ускорить сами умножения с помощью параллелизма.
Для последнего Википедия предполагает, что для умножения матрицы на n мы можем достичь сложности O ( log 2 ( n ) ) теоретически с неограниченным числом процессоров или O ( n ) с более реалистичным параллельным алгоритмом.N N O ( журнал2( н ) ) O ( n )
(Примечание: страница википедии предназначена для общих матриц-вычислений. Я не уверен, что это можно распараллелить еще дальше, используя информацию о том, что мы возводим в квадрат матрицу.)
Вопрос в том, можем ли мы победить это параллелизмом? Я утверждаю, что ответ - нет.
Простая причина заключается в том, что возведение в степень посредством возведения в квадрат является по сути алгоритмом динамического программирования; это позволяет вам пропустить всю работу, повторно используя подрезультаты, но это, в свою очередь, создает зависимость данных, которая запрещает параллелизм. Если мы избавимся от зависимости от данных, но мы также значительно увеличим объем работы, которую мы должны сделать.
Однако, если бы мы выполнили возведение в степень таким образом, это выглядело бы так:
источник
источник