Вычисление постоянного - Computing the permanent

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

Перманент определяется аналогично определителю как сумма произведений наборов элементов матрицы, лежащих в различных строках и столбцах. Однако если определитель взвешивает каждый из этих продуктов со знаком ± 1 на основе паритетность множества, перманент весит их всех знаком +1.

Хотя определитель можно вычислить в полиномиальное время к Гауссово исключение, обычно считается, что перманент нельзя вычислить за полиномиальное время. В теория сложности вычислений, Теорема Доблести утверждает, что вычисление перманентов # P-hard, и даже # P-complete для матриц, в которых все записи 0 или 1 Доблестный (1979). Это помещает вычисление перманента в класс задач, которые, как считается, вычислить еще сложнее, чем НП. Известно, что вычисление перманента невозможно для однородного по пространству журнала АКК⁰ схемы. (Аллендер и Гор 1994 )

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

Определение и наивный алгоритм

Перманент п-к-п матрица А = (а_{я, j}) определяется как

${ displaystyle operatorname {perm} (A) = sum _ { sigma in S_ {n}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}.}$

Сумма здесь распространяется на все элементы σ множества симметричная группа S_п, т.е. по всем перестановки чисел 1, 2, ..., п. Эта формула отличается от соответствующей формулы для определителя только тем, что в определителе каждое произведение умножается на знак перестановки σ, а в этой формуле каждое произведение беззнаковое. Формула может быть напрямую переведена в алгоритм, который наивно расширяет формулу, суммируя по всем перестановкам и в сумме, умножая каждую запись матрицы. Это требует п! п арифметические операции.

Формула Райзера

Самый известный^[1] общий точный алгоритм обусловлен Х. Дж. Райзер  (1963 ). Метод Райзера основан на включение – исключение формула, которая может быть дана^[2] следующим образом: Пусть ${ displaystyle A_ {k}}$ быть полученным от А удалив k колонны, пусть ${ Displaystyle P (A_ {k})}$ быть произведением строковых сумм ${ displaystyle A_ {k}}$, и разреши ${ displaystyle Sigma _ {k}}$ быть суммой значений ${ Displaystyle P (A_ {k})}$ по всем возможным ${ displaystyle A_ {k}}$. потом

${ displaystyle operatorname {perm} (A) = sum _ {k = 0} ^ {n-1} (- 1) ^ {k} Sigma _ {k}.}$

Его можно переписать в терминах элементов матрицы следующим образом^[3]

${ displaystyle operatorname {perm} (A) = (- 1) ^ {n} sum _ {S substeq {1, dots, n }} (- 1) ^ {| S |} prod _ {i = 1} ^ {n} sum _ {j in S} a_ {ij}.}$

Формулу Райзера можно вычислить с помощью ${ Displaystyle О (2 ^ {п-1} п ^ {2})}$ арифметические операции, или ${ Displaystyle О (2 ^ {п-1} п)}$ путем обработки наборов ${ displaystyle S}$ в Код Грея порядок.^[4]

Формула Баласубраманиана – Бакса – Франклина – Глинна

Другая формула, которая кажется такой же быстрой, как у Райзера (или, возможно, даже вдвое быстрее), содержится в двух кандидатских диссертациях. диссертации; видеть (Баласубраман, 1980 г. ), (Bax 1998 ); также(Бакс и Франклин 1996 ). Методы нахождения формулы совершенно разные, они связаны с комбинаторикой алгебры Мюра и с теорией конечных разностей соответственно. Другой способ, связанный с теорией инвариантов, - через поляризационная идентичность для симметричный тензор (Глинн 2010 ). Формула обобщается на бесконечно много других, как обнаружено всеми этими авторами, хотя неясно, быстрее ли они, чем основная. Видеть (Глинн 2013 ).

Простейшая известная формула этого типа (когда характеристика поля не равна двум):

${ displaystyle operatorname {perm} (A) = { frac {1} {2 ^ {n-1}}} left [ sum _ { delta} left ( prod _ {k = 1} ^ {n} delta _ {k} right) prod _ {j = 1} ^ {n} sum _ {i = 1} ^ {n} delta _ {i} a_ {ij} right], }$

где внешняя сумма по всем ${ Displaystyle 2 ^ {п-1}}$ векторов ${ displaystyle delta = ( delta _ {1} = 1, delta _ {2}, dots, delta _ {n}) in { pm 1 } ^ {n}}$.

Особые случаи

Планарный и K_3,3-свободный

Количество идеальное соответствие в двудольный граф считается перманентом графа матрица двойственности, а перманент любой матрицы 0-1 может быть интерпретируется таким образом как количество точных совпадений на графике. За планарные графы (независимо от двудольности) Алгоритм FKT вычисляет количество точных совпадений за полиномиальное время, изменяя знаки тщательно выбранного подмножества записей в Матрица Тутте графика, так что Пфаффиан итоговых кососимметричная матрица (в квадратный корень своего детерминант ) - количество точных совпадений. Этот метод можно обобщить на графы, не содержащие подграфов. гомеоморфный к полный двудольный граф K_3,3.^[5]

Георгий Полиа задал вопрос^[6] о том, когда можно изменить знаки некоторых элементов матрицы 01 01 так, чтобы определитель новой матрицы был перманентом матрицы А. Не все матрицы 01 "конвертируемы" таким образом; на самом деле известно (Маркус и Минк (1961) ) что нет линейного отображения ${ displaystyle T}$ такой, что ${ Displaystyle OperatorName {per} , T (A) = det A}$ для всех ${ Displaystyle п раз п}$ матрицы ${ displaystyle A}$. Характеристика "конвертируемых" матриц была дана следующим образом: Маленький (1975) который показал, что такие матрицы - это в точности те, которые являются матрицей двойственности двудольных графов, которые имеют Пфаффовская ориентация: такая ориентация краев, что для каждого четного цикла ${ displaystyle C}$ для которого ${ Displaystyle G setminus C}$ имеет идеальное совпадение, имеется нечетное количество ребер, направленных вдоль C (и, следовательно, нечетное число с противоположной ориентацией). Также было показано, что это именно те графы, которые не содержат подграф, гомеоморфный ${ displaystyle K_ {3,3}}$, как указано выше.

Вычисление по модулю числа

По модулю 2, перманент такой же, как определитель, поскольку ${ Displaystyle (-1) Equiv 1 { pmod {2}}.}$ Его также можно вычислить по модулю ${ displaystyle 2 ^ {k}}$ во время ${ Displaystyle O (п ^ {4k-3})}$ за ${ Displaystyle к geq 2}$. Однако это UP-жесткий для вычисления перманента по модулю любого числа, не являющегося степенью двойки. Доблестный (1979)

Существуют различные формулы, представленные Глинн (2010) для вычисления по простому модулю пВо-первых, это метод, использующий символьные вычисления с частными производными.

Во-вторых, для п = 3 есть следующая формула для nxn-матрицы ${ displaystyle A}$с участием главногонесовершеннолетние (Коган (1996) ):

${ displaystyle operatorname {per} (A) = (- 1) ^ {n} Sigma _ {J substeq {1, dots, n }} det (A_ {J}) det (A_ { bar {J}}),}$

куда ${ displaystyle A_ {J}}$ является подматрицей ${ displaystyle A}$ индуцированные строками и столбцами ${ displaystyle A}$проиндексировано ${ displaystyle J}$, и ${ displaystyle { bar {J}}}$ является дополнением ${ displaystyle J}$ в ${ Displaystyle {1, точки, п }}$, а определитель пустой подматрицы определен равным 1.

(На самом деле это разложение можно обобщить на произвольное характеристика p как следующую пару дуальных тождеств:

${ displaystyle operatorname {per} (A) = (- 1) ^ {n} Sigma _ {{J_ {1}}, ..., {J_ {p-1}}}} det (A_ {J_ {1}}) ... det (A_ {J_ {p-1}})}$

${ displaystyle operatorname {det} (A) = (- 1) ^ {n} Sigma _ {{J_ {1}}, ..., {J_ {p-1}}} operatorname {per} ( A_ {J_ {1}}) ... operatorname {per} (A_ {J_ {p-1}})}$

где в обеих формулах сумма берется по всем (p-1) -наборам ${ displaystyle {J_ {1}}, ..., {J_ {p-1}}}$ которые являются разделами множества ${ Displaystyle {1, точки, п }}$ на p-1 подмножество, некоторые из них, возможно, пусты.

Первая формула имеет аналог гафниана симметричной ${ displaystyle A}$ и нечетный p:

${ displaystyle operatorname {haf} ^ {2} (A) = (- 1) ^ {n} Sigma _ {{J_ {1}}, ..., {J_ {p-1}}} det (A_ {J_ {1}}) ... det (A_ {J_ {p-1}}) (- 1) ^ {| J_ {1} | + ... + | J _ {(p-1) / 2} |}}$

с суммой, взятой по тому же набору индексов. Более того, в характеристика нулевое аналогичное выражение суммы свертки, включающее как перманент, так и определитель, дает Гамильтонов цикл полином (определяется как ${ displaystyle operatorname {ham} (A) = sum _ { sigma in H_ {n}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}}$ куда ${ displaystyle {H_ {n}}}$ - множество n-перестановок, имеющих только один цикл):${ displaystyle operatorname {ham} (A) = Sigma _ {J substeq {2, dots, n }} det (A_ {J}) operatorname {per} (A _ { bar {J }}) (- 1) ^ {| J |}}$ . В характеристика 2 последнее равенство превращается в ${ displaystyle operatorname {ham} (A) = Sigma _ {J substeq {2, dots, n }} det (A_ {J}) operatorname {det} (A _ { bar {J }})}$ что, таким образом, дает возможность полиномиально вычислить Гамильтонов цикл многочлен любого унитарный ${ displaystyle U}$ (т.е. такие, что ${ Displaystyle U ^ {T} U = I}$ куда ${ displaystyle I}$ является единичной nxn-матрицей), поскольку каждый минор такой матрицы совпадает со своим алгебраическим дополнением: ${ displaystyle operatorname {ham} (U) = operatorname {det} ^ {2} (U + I _ {/ 1})}$ куда ${ displaystyle I _ {/ 1}}$ является единичной nxn-матрицей, в которой индекс 1,1 заменен на 0. Более того, она, в свою очередь, может быть дополнительно обобщена для унитарный nxn-матрица ${ displaystyle U}$ в качестве ${ displaystyle operatorname {ham_ {K}} (U) = operatorname {det} ^ {2} (U + I _ {/ K})}$ куда ${ displaystyle K}$ является подмножеством {1, ..., n}, ${ displaystyle I _ {/ K}}$ - единичная nxn-матрица, в которой элементы индексов k, k заменены на 0 для всех k, принадлежащих ${ displaystyle K}$, и мы определяем ${ displaystyle operatorname {ham_ {K}} (A) = sum _ { sigma in H_ {n} {(K)}} prod _ {i = 1} ^ {n} a_ {i, сигма (я)}}$ куда ${ displaystyle {H_ {n} {(K)}}}$ - множество n-перестановок, каждый цикл которых содержит хотя бы один элемент ${ displaystyle K}$.)

Из этой формулы вытекают следующие тождества над полями характеристика 3:

для любого обратимый ${ displaystyle A}$

${ displaystyle operatorname {per} (A ^ {- 1}) operatorname {det} ^ {2} (A) = operatorname {per} (A)}$;

для любого унитарный ${ displaystyle U}$ , т.е. квадратная матрица ${ displaystyle U}$ такой, что ${ Displaystyle U ^ {T} U = I ,}$ куда ${ displaystyle I}$ - единичная матрица соответствующего размера,

${ Displaystyle OperatorName {пер} ^ {2} (U) = det (U + V) det (-U)}$

куда ${ displaystyle V}$ матрица, элементами которой являются кубы соответствующих элементов матрицы ${ displaystyle U}$.

Также было показано (Коган (1996) ), что, если мы определим квадратную матрицу ${ displaystyle A}$ как k-полуунитарный, когда ${ displaystyle rank (A ^ {T} A-I ,)}$ = kперманент 1-полуунитарной матрицы вычислим за полиномиальное время над полями характеристика 3, а для k > 1 проблема становится # 3-П-полный. (Параллельная теория касается Гамильтонов цикл многочлен от характеристика 2: хотя вычисление его на унитарных матрицах возможно за полиномиальное время, проблема является # 2-P-полной для k-полуунитарных матриц для любого k> 0). Последний результат был существенно расширен в 2017 г. (Кнежевич и Коэн (2017) ) и было доказано, что в характеристика 3 есть простая формула, связывающая перманенты квадратной матрицы и ее частичной обратной (для ${ displaystyle A_ {11}}$ и ${ displaystyle A_ {22}}$ будучи квадратным, ${ displaystyle A_ {11}}$ существование обратимый ):

${ displaystyle operatorname {per} left ({ begin {matrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {matrix}} right) = operatorname {det} ^ {2} left (A_ {11} right) operatorname {per} left ({ begin {matrix} A_ {11} ^ {- 1} & A_ {11} ^ {- 1} A_ {12} A_ {21} A_ {11} ^ {- 1} & A_ {22} -A_ {21} A_ {11} ^ {- 1} A_ {12} end {matrix}} right)}$

и это позволяет за полиномиальное время сократить вычисление перманента матрицы размером nxn с подмножеством из k или k-1 строк, выражаемых как линейные комбинации другого (непересекающегося) подмножества из k строк, до вычисления перманента из ( nk) x (nk) - или (n-k + 1) x (n-k + 1) -матрица соответственно, поэтому введен оператор сжатия (аналогичный гауссовской модификации, применяемой для вычисления определителя), который «сохраняет» постоянный в характеристика 3. (Аналогично, стоит отметить, что Гамильтонов цикл многочлен от характеристика 2 также обладает своими инвариантными матричными сжатиями с учетом того факта, что ham (A) = 0 для любой nxn-матрицы A, имеющей три равных строки, или, если n> 2, пару индексов i, j, таких, что ее i -я и j-я строки идентичны, и его i-й и j-й столбцы также идентичны.) Закрытие этого оператора определяется как предел его последовательного применения вместе с преобразованием транспонирования (используется каждый раз, когда оператор покидает матрица без изменений) также является отображением оператора, когда применяется к классам матриц, один класс к другому. Тогда как оператор сжатия отображает класс 1-полуунитарных матриц в себя и классы унитарный и 2-полуунитарные, сжатие-замыкание 1-полуунитарного класса (а также класса матриц, полученных из унитарный единиц путем замены одной строки на произвольный вектор-строку - перманент такой матрицы есть, с помощью разложения Лапласа, сумма перманентов 1-полуунитарных матриц и, соответственно, вычислимая за полиномиальное время) пока неизвестна и напряженно связанных с общей проблемой вычислительной сложности перманента в характеристика 3 и главный вопрос P против NP: как было показано в (Кнежевич и Коэн (2017) ), если такое сжатие-замыкание представляет собой набор всех квадратных матриц над полем характеристика 3 или, по крайней мере, содержит матричный класс, на котором вычисляется перманент. # 3-П-полный (как и класс 2-полуунитарных матриц), то перманент вычислим за полиномиальное время в этом характеристика.

Кроме того, проблема поиска и классификации возможных аналогов постоянно сохраняющих компрессий, существующих в характеристика 3 для других простых характеристик сформулировано (Кнежевич и Коэн (2017) ), давая следующее тождество для матрицы размера nxn ${ displaystyle A}$ и два n-вектора (все их элементы из набора {0, ..., p-1}) ${ displaystyle alpha}$ и ${ displaystyle beta}$ такой, что ${ displaystyle { sum _ {i = 1} ^ {n} alpha _ {i}} = { sum _ {j = 1} ^ {n} beta _ {j}}}$, справедливые в произвольном простом числе характеристика п:

${ displaystyle operatorname {per} (A ^ { left ( alpha, beta right)}) = operatorname {det} ^ {p-1} (A) operatorname {per} left (A ^ {-1} right) ^ { left ((p-1 right) { vec {1}} _ {n} - beta, left (p-1 right) { vec {1}} _ {n} - alpha)} ( prod _ {i = 1} ^ {n} alpha _ {i}!) ( prod _ {j = 1} ^ {n} beta _ {j}! ) left (-1 right) ^ {n + sum _ {i = 1} ^ {n} alpha _ {i}}}$

где для nxm-матрицы ${ displaystyle M}$, n-вектор ${ displaystyle x}$ и m-вектор ${ displaystyle y}$, оба вектора имеют все свои элементы из набора {0, ..., p-1}, ${ Displaystyle М ^ {(х, у)}}$ обозначает матрицу, полученную от ${ displaystyle M}$ через повторение ${ displaystyle x_ {i}}$ умножает на его i-ю строку для i = 1, ..., n и ${ displaystyle y_ {j}}$ умножить на его j-й столбец для j = 1, ..., m (если кратность некоторой строки или столбца равна нулю, это будет означать, что строка или столбец были удалены, и, таким образом, это понятие является обобщением понятия подматрицы), и ${ displaystyle { vec {1}} _ {n}}$ обозначает n-вектор, все элементы которого равны единице. Это тождество является точным аналогом классической формулы, выражающей минор матрицы через минор ее инверсии, и, следовательно, демонстрирует (еще раз) своего рода двойственность между определителем и перманентом как относительными имманантами. (Собственно собственный аналог гафниана симметричной ${ displaystyle A}$ и нечетное простое число p равно ${ displaystyle operatorname {haf} ^ {2} (A ^ { left ( alpha, alpha right)}) = operatorname {det} ^ {p-1} (A) operatorname {haf} ^ {2} left (A ^ {- 1} right) ^ { left ((p-1 right) { vec {1}} _ {n} - alpha, left (p-1 right) ) { vec {1}} _ {n} - alpha)} ( prod _ {i = 1} ^ {n} alpha _ {i}!) ^ {2} (- 1) ^ {n ( п-1) / 2 + п + сумма _ {я = 1} ^ {п} альфа _ {я}}}$ ).

И, как еще более широкое обобщение для частичного обратного случая в простом числе характеристика p, для ${ displaystyle A_ {11}}$, ${ displaystyle A_ {22}}$ будучи квадратным, ${ displaystyle A_ {11}}$ существование обратимый и размер ${ displaystyle {n_ {1}}}$Икс${ displaystyle {n_ {1}}}$, и ${ displaystyle { sum _ {i = 1} ^ {n} alpha _ {i}} = { sum _ {j = 1} ^ {n} beta _ {j}}}$, выполняется также тождество

${ displaystyle operatorname {per} left ({ begin {matrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {matrix}} right) ^ { left ( alpha, beta right)} = operatorname {det} ^ {p-1} (A_ {11}) operatorname {per} left ({ begin {matrix} A_ {11} ^ {- 1} & A_ {11} ^ {- 1} A_ {12} A_ {21} A_ {11} ^ {- 1} & A_ {22} -A_ {21} A_ {11} ^ {- 1} A_ {12} конец {матрица}} right) ^ { left ((p-1 right) { vec {1}} _ {n} - beta, left (p-1 right) { vec {1} } _ {n} - alpha)} ( prod _ {i = 1} ^ {n} alpha _ {1, i}!) ( prod _ {j = 1} ^ {n} beta _ { 1, j}!) Left (-1 right) ^ {n_ {1} + sum _ {i = 1} ^ {n} alpha _ {1, i}}}$

где общие векторы кратности строки / столбца ${ displaystyle alpha}$ и ${ displaystyle beta}$ для матрицы ${ displaystyle A}$ генерировать соответствующие векторы кратности строки / столбца ${ displaystyle alpha _ {s}}$ и ${ displaystyle beta _ {t}}$, s, t = 1,2, для его блоков (то же самое ${ displaystyle A}$частичный обратный элемент в правой части равенства).

Приблизительный расчет

Когда записи А неотрицательны, перманент можно вычислить примерно в вероятностный полиномиальное время с точностью до εM, куда M - значение перманента, а ε> 0 произвольно. Другими словами, существует полностью полиномиальная схема рандомизированной аппроксимации (FPRAS) (Джеррам, Вигода и Синклер (2001) Ошибка harvtxt: нет цели: CITEREFJerrumVigodaSinclair2001 (помощь)).

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

Можно приблизительно подсчитать количество точных соответствий в графе с помощью самовосстановление постоянного, с использованием FPAUS в сочетании с хорошо известным сокращением от отбора проб до подсчета из-за Джеррам, доблестный и Вазирани (1986) Ошибка harvtxt: нет цели: CITEREFJerrumValiantVazirani1986 (помощь). Позволять ${ Displaystyle M (G)}$ обозначают количество совершенных совпадений в ${ displaystyle G}$. Грубо говоря, для любого конкретного ребра ${ displaystyle e}$ в ${ displaystyle G}$, путем выборки множества совпадений в ${ displaystyle G}$ и подсчитывая, сколько из них совпадают в ${ displaystyle G setminus e}$, можно получить оценку отношения ${ Displaystyle rho = { гидроразрыва {M (G)} {M (G setminus e)}}}$. Номер ${ Displaystyle M (G)}$ затем ${ displaystyle rho M (G setminus e)}$, куда ${ Displaystyle М (G setminus e)}$ можно аппроксимировать, применяя тот же метод рекурсивно.

Другой класс матриц, для которых перманент может быть вычислен приближенно, - это набор положительно-полуопределенные матрицы (теоретико-сложная задача приближения перманента таких матриц с точностью до мультипликативной ошибки считается открытой^[7]). Соответствующий рандомизированный алгоритм основан на модели выборка бозонов и использует инструменты, необходимые для квантовая оптика, чтобы представить перманент положительно-полуопределенных матриц как ожидаемое значение конкретной случайной величины. Последний затем аппроксимируется его выборочным средним.^[8] Этот алгоритм для некоторого набора положительно-полуопределенных матриц аппроксимирует их перманент за полиномиальное время с точностью до аддитивной ошибки, которая более надежна, чем стандартный классический алгоритм полиномиального времени Гурвица.^[9]

Примечания

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

дальнейшее чтение

• Барвинок, А. (2017), «Аппроксимация перманентов и гафнианов», Дискретный анализ, arXiv:1601.07518, Дои:10.19086 / da.1244.