Умножение матричной цепочки - Matrix chain multiplication

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

Есть много вариантов, потому что умножение матриц ассоциативный. Другими словами, каким бы ни был товар в скобках, полученный результат останется прежним. Например, для четырех матриц А, B, C, и D, мы бы хотели иметь:

((AB)C)D = (А(до н.э))D = (AB)(CD) = А((до н.э)D) = А(B(CD)).

Однако порядок, в котором продукт заключен в круглые скобки, влияет на количество простых арифметических операций, необходимых для вычисления продукта, то есть вычислительная сложность. Например, если А представляет собой матрицу 10 × 30, B является матрицей 30 × 5, а C матрица 5 × 60, то

вычисление (AB)C требуется (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500 операций, а

вычисление А(до н.э) требуется (30 × 5 × 60) + (10 × 30 × 60) = 9000 + 18000 = 27000 операций.

Очевидно, что первый метод более эффективен. Обладая этой информацией, формулировку задачи можно уточнить следующим образом: «как определить оптимальные скобки для продукта п матрицы? "Проверка всех возможных скобок (грубая сила ) потребует время выполнения то есть экспонента от числа матриц, что очень медленно и непрактично для больших п. Более быстрое решение этой проблемы может быть достигнуто путем разделения проблемы на набор связанных подзадач. Решив подзадачи один раз и повторно используя решения, можно значительно сократить необходимое время выполнения. Эта концепция известна как динамическое программирование.

Алгоритм динамического программирования

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

• Возьмите последовательность матриц и разделите ее на две подпоследовательности.
• Найдите минимальную стоимость перемножения каждой подпоследовательности.
• Сложите эти затраты вместе и прибавьте стоимость умножения двух матриц результатов.
• Сделайте это для каждой возможной позиции, в которой последовательность матриц может быть разделена, и возьмите минимум по всем из них.

Например, если у нас есть четыре матрицы ABCD, мы вычисляем затраты, необходимые для нахождения каждого из (А)(BCD), (AB)(CD), и (ABC)(D), выполняя рекурсивные вызовы, чтобы найти минимальные затраты на вычисление ABC, AB, CD, и BCD. Затем мы выбираем лучший. Более того, это дает не только минимальные затраты, но также демонстрирует лучший способ выполнения умножения: сгруппируйте его так, чтобы получить наименьшие общие затраты, и сделайте то же самое для каждого фактора.

Однако, если мы реализуем этот алгоритм, мы обнаружим, что он так же медленен, как и наивный способ пробовать все перестановки! Что пошло не так? Ответ в том, что мы делаем много лишней работы. Например, выше мы сделали рекурсивный вызов, чтобы найти лучшую стоимость для вычисления обоих ABC и AB. Но для поиска оптимальной стоимости вычисления ABC также необходимо найти лучшую стоимость для AB. По мере того как рекурсия становится глубже, возникает все больше и больше ненужных повторений этого типа.

Одно простое решение называется мемоизация: каждый раз, когда мы вычисляем минимальную стоимость, необходимую для умножения определенной подпоследовательности, мы сохраняем ее. Если нас когда-либо попросят вычислить его снова, мы просто даем сохраненный ответ и не пересчитываем его. Поскольку есть около п²/ 2 различных подпоследовательности, где п - количество матриц, для этого требуется достаточно места. Можно показать, что этот простой трюк сокращает время выполнения до O (п³) из O (2^п), что более чем достаточно для реальных приложений. Это сверху вниз динамическое программирование.

Следующий восходящий подход ^[1] вычисляет, для каждых 2 ≤ k ≤ n, минимальные затраты всех подпоследовательностей длины k с использованием уже вычисленных затрат на меньшие подпоследовательности. Он имеет такое же асимптотическое время выполнения и не требует рекурсии.

Псевдокод:

// Матрица A [i] имеет размерность dims [i-1] x dims [i] для i = 1..nMatrixChainOrder(int тускнеет[]){    // длина [dims] = n + 1    п = тускнеет.длина - 1;    // m [i, j] = минимальное количество скалярных умножений (т.е. стоимость)    // необходимо вычислить матрицу A [i] A [i + 1] ... A [j] = A [i..j]    // Стоимость равна нулю при умножении одной матрицы    за (я = 1; я <= п; я++)        м[я, я] = 0;    за (len = 2; len <= п; len++) { // Длина подпоследовательности        за (я = 1; я <= п - len + 1; я++) {            j = я + len - 1;            м[я, j] = МАКСИНТ;            за (k = я; k <= j - 1; k++) {                Стоимость = м[я, k] + м[k+1, j] + тускнеет[я-1]*тускнеет[k]*тускнеет[j];                если (Стоимость < м[я, j]) {                    м[я, j] = Стоимость;                    s[я, j] = k; // Индекс разделения подпоследовательности, для которого была достигнута минимальная стоимость                }            }        }    }}

• Примечание. Первый индекс для dims - 0, а первый индекс для m и s - 1.

А Ява реализация с использованием индексов массива с отсчетом от нуля вместе с удобным методом для печати решенного порядка операций:

общественный учебный класс MatrixOrderOptimization {    защищенный int[][]м;    защищенный int[][]s;    общественный пустота matrixChainOrder(int[] тускнеет) {        int п = тускнеет.длина - 1;        м = новый int[п][п];        s = новый int[п][п];        за (int lenMinusOne = 1; lenMinusOne < п; lenMinusOne++) {            за (int я = 0; я < п - lenMinusOne; я++) {                int j = я + lenMinusOne;                м[я][j] = Целое число.MAX_VALUE;                за (int k = я; k < j; k++) {                    int Стоимость = м[я][k] + м[k+1][j] + тускнеет[я]*тускнеет[k+1]*тускнеет[j+1];                    если (Стоимость < м[я][j]) {                        м[я][j] = Стоимость;                        s[я][j] = k;                    }                }            }        }    }    общественный пустота printOptimalParenthesizations() {        логический[] inAResult = новый логический[s.длина];        printOptimalParenthesizations(s, 0, s.длина - 1, inAResult);    }    пустота printOptimalParenthesizations(int[][]s, int я, int j,  / * для красивой печати: * / логический[] inAResult) {        если (я != j) {            printOptimalParenthesizations(s, я, s[я][j], inAResult);            printOptimalParenthesizations(s, s[я][j] + 1, j, inAResult);            Нить istr = inAResult[я] ? "_результат " : " ";            Нить jstr = inAResult[j] ? "_результат " : " ";            Система.из.println("А_" + я + istr + "* A_" + j + jstr);            inAResult[я] = истинный;            inAResult[j] = истинный;        }    }}

В конце этой программы у нас есть минимальная стоимость полной последовательности.

Более эффективные алгоритмы

Есть алгоритмы более эффективные, чем О(п³) алгоритм динамического программирования, хотя они и более сложные.

Ху и Шинг (1981)

Алгоритм, опубликованный в 1981 году Ху и Шингом, достигает О(п бревноп) вычислительная сложность.^[2][3][4]Они показали, как можно преобразовать задачу умножения цепочки матриц (или уменьшенный ) в проблему триангуляция из правильный многоугольник. Многоугольник ориентирован так, что есть горизонтальная нижняя сторона, называемая основанием, которая представляет конечный результат. Другой п стороны многоугольника по часовой стрелке представляют матрицы. Вершины на каждом конце стороны - это размеры матрицы, представленной этой стороной. С п матриц в цепочке умножения есть п−1 бинарные операции и C_п−1 способы размещения скобок, где C_п−1 это (п−1) -й Каталонский номер. Алгоритм использует, что есть также C_п−1 возможные триангуляции многоугольника с п+1 стороны.

На этом изображении показаны возможные триангуляции регулярного шестиугольник. Они соответствуют различным способам размещения скобок для упорядочивания умножения произведения 5 матриц.

В приведенном ниже примере есть четыре стороны: A, B, C и конечный результат ABC. A - матрица 10 × 30, B - матрица 30 × 5, C - матрица 5 × 60, а конечный результат - матрица 10 × 60. Правильный многоугольник в этом примере - это 4-угольник, то есть квадрат:

Матричное произведение AB представляет собой матрицу 10x5, а BC - матрицу 30x60. В этом примере возможны две триангуляции:

• 

  Многоугольное представление (AB) C

• 

  Многоугольное представление A (BC)

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

(AB)C: (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500 умножений

А(до н.э): (30 × 5 × 60) + (10 × 30 × 60) = 9000 + 18000 = 27000 умножений

Hu & Shing разработала алгоритм, который находит оптимальное решение задачи разделения минимальной стоимости в О(п бревноп) время.

Аппроксимирующий алгоритм Чин-Ху-Шинга

Во введении ^[4] представлен аппроксимирующий алгоритм - аппроксимирующий алгоритм Чин-Ху-Шинга. Хотя этот алгоритм дает приближение к оптимальной триангуляции, его стоит объяснить, поскольку он облегчает понимание методов, используемых Ху-Шингом в их работе.

В каждую вершину V многоугольника связан вес ш. Предположим, у нас есть три последовательные вершины ${\displaystyle V_{i-1},V_{i},V_{i+1}}$, и это ${\displaystyle V_{min}}$ - вершина с минимальным весом ${\displaystyle w_{min}}$.Смотрим на четырехугольник с вершинами ${\displaystyle V_{min},V_{i-1},V_{i},V_{i+1}}$ (по часовой стрелке). Мы можем выполнить триангуляцию двумя способами:

• ${\displaystyle (V_{min},V_{i-1},V_{i})}$ и ${\displaystyle (V_{min},V_{i+1},V_{i})}$, со стоимостью ${\displaystyle w_{min}w_{i-1}w_{i}+w_{min}w_{i+1}w_{i}}$
• ${\displaystyle (V_{min},V_{i-1},V_{i+1})}$ и ${\displaystyle (V_{i-1},V_{i},V_{i+1})}$ со стоимостью ${\displaystyle w_{min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}$.

Поэтому если

${\displaystyle w_{min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{min}w_{i-1}w_{i}+w_{min}w_{i+1}w_{i}}$

или эквивалентно

${\displaystyle {\frac {1}{w_{i}}}+{\frac {1}{w_{min}}}<{\frac {1}{w_{i+1}}}+{\frac {1}{w_{i-1}}}}$

удаляем вершину ${\displaystyle V_{i}}$ от многоугольника и добавьте сторону ${\displaystyle (V_{i-1},V_{i+1})}$ к триангуляции. Повторяем этот процесс до тех пор, пока ${\displaystyle V_{i}}$ удовлетворяет указанному выше условию. для всех остальных вершин ${\displaystyle V_{n}}$, добавляем сторону ${\displaystyle (V_{min},V_{n})}$ к триангуляции. Это дает нам почти оптимальную триангуляцию.

Обобщения

Задача умножения цепочки матриц обобщается на решение более абстрактной проблемы: заданная линейная последовательность объектов, ассоциативная бинарная операция над этими объектами и способ вычисления стоимости выполнения этой операции над любыми двумя заданными объектами (а также со всеми частичными объектами). results), вычислите способ с минимальными затратами для группировки объектов, чтобы применить операцию к последовательности.^[5] Один несколько надуманный частный случай этого - конкатенация строк списка строк. В C, например, стоимость конкатенации двух строк длины м и п с помощью strcat это O (м + п), так как нам нужно O (м) пора найти конец первой строки и O (п) пора скопировать вторую строку в ее конец. Используя эту функцию стоимости, мы можем написать алгоритм динамического программирования, чтобы найти самый быстрый способ сцепления последовательности строк. Однако такая оптимизация бесполезна, потому что мы можем напрямую объединить строки во времени, пропорциональном сумме их длин. Аналогичная проблема существует для одного связанные списки.

Другое обобщение - решение проблемы при наличии параллельных процессоров. В этом случае вместо того, чтобы складывать затраты на вычисление каждого фактора матричного произведения, мы берем максимум, потому что мы можем делать их одновременно. Это может сильно повлиять как на минимальную стоимость, так и на окончательную оптимальную группировку; предпочтение отдается более "сбалансированным" группам, которые загружают все процессоры. Есть и более изощренные подходы.^[6]

Смотрите также

• Ассоциэдр
• Решетка Тамари

Рекомендации

1. Кормен, Томас Х; Лейзерсон, Чарльз Э; Ривест, Рональд Л.; Штейн, Клиффорд (2001). «15.2: Умножение матрицы на цепочку». Введение в алгоритмы. Второе издание. MIT Press и McGraw-Hill. С. 331–338. ISBN  978-0-262-03293-3.
2. Ху, ТС; Шинг, MT (1982). «Вычисление продуктов матричной цепи, часть I» (PDF). SIAM Журнал по вычислениям. 11 (2): 362–373. CiteSeerX  10.1.1.695.2923. Дои:10.1137/0211028. ISSN  0097-5397.
3. Ху, ТС; Шинг, MT (1984). «Вычисление продуктов матричной цепи, часть II» (PDF). SIAM Журнал по вычислениям. 13 (2): 228–251. CiteSeerX  10.1.1.695.4875. Дои:10.1137/0213017. ISSN  0097-5397.
4. Артур, Czumaj (1996). «Очень быстрая аппроксимация матричной цепочки продуктов» (PDF). Журнал алгоритмов. 21: 71–79. CiteSeerX  10.1.1.218.8168. Дои:10.1006 / jagm.1996.0037.
5. Г. Баумгартнер, Д. Бернхольд, Д. Кочорва, Р. Харрисон, М. Нойен, Дж. Рамануджам и П. Садаяппан. Платформа оптимизации производительности для компиляции выражений тензорного сжатия в параллельные программы. 7-й Международный семинар по высокоуровневым моделям параллельного программирования и поддерживающим средам (HIPS '02). Форт-Лодердейл, Флорида. 2002 доступно на http://citeseer.ist.psu.edu/610463.html и в http://www.csc.lsu.edu/~gb/TCE/Publications/OptFramework-HIPS02.pdf
6. Хиджо Ли, Чон Ким, Сон Чже Хон и Сонгу Ли. Распределение процессоров и планирование задач продуктов матричной цепочки в параллельных системах В архиве 2011-07-22 на Wayback Machine. IEEE Trans. по параллельным и распределенным системам, Vol. 14, No. 4, pp. 394–407, апрель 2003 г.