Redfox11126 июн в 10:06

Сикофантия? Или ускорение динамического пересчета определителя от O(n³) до O(n)?

Средний

11 мин

7.9K

Python * Алгоритмы * Искусственный интеллектМатематика *

Обзор

Из песочницы

Комментарии 40

halyavin 26 июн в 10:51

Этот алгоритм непосредственно следует из обобщенной матричной леммы.

Redfox111 26 июн в 11:22

Хотелось бы понять каким образом следует. И тогда еще: прав ли AI в том, что у “линейно-векторного” метода есть премущества перед той же матричной леммой ? Разве может быть у частного случая премущество перед общим? Либо ключевое слово здесь “обобщенная” ? Тогда получается AI знал только про простую лемму, а не про обобщенную…

halyavin 26 июн в 12:18

В матричной лемме вычисляется определитель матрицы . Где и — матрицы $n\times 2$ . Выбираем равной двум столбцам, которые мы хотим добавить, а . В произведении получим матрицу . Это позволяет нам добавить что угодно к первым двум столбцам матрицы, а значит и как угодно их поменять.

Работает для произвольного числа столбцов , только потом в матричной лемме нужно будет считать определитель матрицы размера $k\times k$ .

Redfox111 26 июн в 13:01

Ясно. А как тогда сравнить вычислительную сложность леммы о детерминанте и линейно-векторного подхода, основанного на следствии из этой леммы ? Причем как в символьном так и в численном режимах ? Будут ли они идентичны ?

Redfox111 26 июн в 14:04

"Это позволяет нам добавить что угодно к первым двум столбцам матрицы, а значит и как угодно их поменять."
И все-таки, таким образом мы получим новую матрицу с замененными столбцами (пусть двумя). Но ведь только из этого не следует, что из-за этой операции появляется разность произведений детерминантов с инверсивно замененными столбцами ?

wataru 26 июн в 15:45

Сикофантия... Блин. Почему нельзя использовать нормальные русские слова: подхалимство, лесть, лизоблюдство?

Redfox111 26 июн в 17:25

Возможно потому, что этот термин исходя из того же подхалимства, подсказал мне тот же AI. К тому же это не простое подхалимство, а цифровое. А значит: "сикофантия".

wataru 26 июн в 16:15

По сути статьи. Формула, похоже, действительно новая, но стоит статью сильно ужать. Читать рассуждения ИИ вообще никому не интересно.

Что касается практического применения, я так понял, что ваш "линейно-векторный" метод работает для фиксированных столбцов? Т.е. не любые 2 столбца меняются, а 2 конкретных, хоть какие именно можно выбрать на этапе предподсчета?

В этом случае стандартный, упомянутый вами метод через determinant lemma тоже работает за O(n).

Берем матрицы V и U, как выше уже указал @halyavin. А дальше остается только подсчитать $\det(I+V^T A^{-1} U)$ . Но в этом страшном произведении внутри вам фактически надо найти 2 строки $A^{-1} U$ , ведь матрица V имеет ровно 2 единицы и используется для выбора двух изменяемых столбцов. Каждая строка произведения считается за O(n), ведь в ней всего 2 элемента, фактически двумя скалярными произведениями строки A на столбец U.

В итоге ваш метод нисколько не быстрее стандартного и кажется им же и является.

Как интересное математическое тождество ваше открытие имеет смысл, маленькую статейку в какой-нибудь журнал даже можно послать. Но никакой революции оно не произвело.

Redfox111 26 июн в 17:52

“Читать рассуждения ИИ вообще никому не интересно.”

Не соглашусь. Тут сразу две темы освещаются:

a. Я мог бы вообще не говорить (писать) откуда взял источники своей информации. Может из словаря или статей ? При таком понимании ИИ - тот же словарь. А я. как наверно многие, вообще часто используют информацию из каких-либо источников. И тогда я бы просто перечислил те области применения, в которых предполагается применение “линейно-векторного” метода без указания источников информации. Думаю, во многих случаях при таком подходе “рассуждения” читались бы с интересом.

b. В том-то и дело, что вторая линия моей статьи посвящена возможным проблемам при общении с ИИ. Что я в том числе и описал. А как в таком случае юез упоминания ИИ ?

“но стоит статью сильно ужать”

С этим могу согласиться. Это моя первая статья на Хабр. Возможно, я превысил общий, традиционный для Хабр объем статьи или даже противоречу каким-то иным нормам. Но подчеркну снова: эти нарушения по моему мнению никак не зависят от источника полученной информации.

“Что касается практического применения, я так понял, что ваш “линейно-векторный” метод работает для фиксированных столбцов? Т.е. не любые 2 столбца меняются, а 2 конкретных, хоть какие именно можно выбрать на этапе предподсчета?”

Предполагается, что на каждом шаге изменений меняются два любых столбца, отличные от тех, которые были изменены на предыдущем шаге. Но при этом при каждом новом изменении происходит возврат к базовой матрице: т.е. возвращаются два “старых” столбца, а вместо них на следующем шаге заменяются два других, в общем случае отличных.

wataru 26 июн в 19:00

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

Даже в такой формулировке, стандартный метод тоже делает пересчет за O(n). Там же надо 2 выбранных строки обратной матрицы скалярно умножить на 2 вектора измененных значений. Это можно сделать для любых двух измененных столбца.

Redfox111 26 июн в 17:57

“Как интересное математическое тождество ваше открытие имеет смысл, маленькую статейку в какой-нибудь журнал даже можно послать.” Так она уже опубликована. В статье есть ссылка на проект в GitVerse, в котором - ссылка на эту статью. Я как раз и задался вопросом о практическом ее применении.

“В итоге ваш метод нисколько не быстрее стандартного и кажется им же и является.” Этов численном режиме ? А в символьном ? Когда вместо чисел в замещаемых столбцах находятся символы ?

wataru 26 июн в 19:04

Этов численном режиме ? А в символьном

Там же тоже надо лишь скалярно умножить вектора q, q' на 2 строки обратной матрицы. Будь там числа или символы - все так же как в вашем методе.

i-netay вчера в 08:06

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

Redfox111 вчера в 10:50

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

wataru вчера в 11:08

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

Redfox111 вчера в 12:23

Секунду. Я ничего не платил. И даже не по блату. Так что наверно нужно вводить еще поправки на то, что и нерецензируемые журналы бывают разные.

MasterMentor 26 июн в 16:52

AI: «Вы полностью правы в том, что не правы. Я был абсолютно не прав, когда утверждал, что вы были правы. Прошу прощения, что ввел Вас в заблуждение»

Даже если и Вы не правы, и ИИ не прав, то проделать эту работу стоило только ради этого:

Тем временем AI меня хвалил и отправлял в мой адрес следующие эпитеты: «метод Шевченко», «уникальная сила метода Шевченко», «жизненно необходимый», «даёт прорыв», «битва титанов: метод Шевченко против формулы Вудбери», «математическая дуэль»…

…хотя по сути это “Сико фантия”

PS Сикофантия… Блин. Почему нельзя использовать нормальные русские слова: подхалимство, лесть, лизоблюдство? (с) wataru

wataru 26 июн в 16:58

Более того, ваше тождество тривиально следует из матричной леммы. Я согласен с @halyavin.

Выпишите лемму для таких U и V:

$V_{2, n} =$ (2 единицы: по одной в строке, в столбцах i и j)

$U_{2,n} = (q-A_i,q'-A_j)^T$

$F_{i,j}(q, q') = \det(F_n) \det(I + V^T A^{-1} U)$

Выпишите аккуратно матрицу внутри:
$1+ A^{-1T}_i (q-A_i)$ , $A^{-1T}_j(q'-A_j)$

$A^{-1T}_j (q-A_i)$ , $1+ A^{-1T}_j (q'-A_j)$

Вот эти скалярные произведения очень похожи на высчитывание определителя через миноры, которые выражаются через элементы в обратной матрице. Отсюда и вылезают F_i(q) и остальные 3 варианта с заменой одного столбца. В итоге ваша формула и получится.

Сюда эти формулы вбивать очень муторно, но это выводится.
Основной трюк: $F_i(q) = -1^{j+1} q (M_{1j}, -M_{2j},M_{3j}..)$ M_ij - минор, он же равен $A^{-1}_{ji} \det(A)$

Отсюда скалярные произведения внутри дадут $F_i(q)/\det(F_n)$ , а после вычисления детерминанта матрицы 2x2 один F_n сократится с внешним а второй можно перенести налево и в точности ваша формула и получается.

Так что наверняка оно в какой-то литературе даже описано.

Redfox111 26 июн в 18:09

“Так что наверняка оно в какой-то литературе даже описано” Так литература-то есть. Тот самый журнал, в котором была опубликована моя статья (ссылка в описании). А это как раз на тему рецензирования, которую я затронул и весьма сильно. Если бы я попал на тех людей, которые объяснили мне, что я повторяюсь - я бы вряд ли стал повторяться.

“очень похожи на высчитывание определителя через миноры” В формуле из теоремы 1 миноры вообще не используются. В формуле из теоремы 3 - также.

wataru 26 июн в 19:05

Нет же. Наверняка эта формула опубликована еще в прошлом веке.

Redfox111 26 июн в 20:13

“Нет же. Наверняка эта формула опубликована еще в прошлом веке”

Нужно задать соответствующий вопрос ИИ.

wataru 26 июн в 19:07

“очень похожи на высчитывание определителя через миноры” В формуле из теоремы 1 миноры вообще не используются. В формуле из теоремы 3 - также.

Как не используются? Как вы считаете F_i(q)? Это разложение определителя по столбцу. Коэффициенты перед q_i какие? Миноры же и есть. Ну там какие-то минусы где-то еще расставить надо, но это не принципиально.

В теореме 3 разложение на миноры второго порядка будет.

Redfox111 26 июн в 20:00

“Как не используются? Как вы считаете F_i(q)? Это разложение определителя по столбцу. Коэффициенты перед q_i какие? Миноры же и есть.”

Я имел в виду, что в явном виде в формулах из теорем 1 и 3 миноров нет. Там есть определители матриц, а не миноры (или алгебраические дополнения) этих матриц. И коэффициенты перед q_i - как раз определители целых матриц (снова имею в виду: а не подматриц, которые получаются как собственно в тождестве Деснано-Якоби после вычеркивания из них строк и столбцов). А так - конечно можно сказать, что мы не только миноры при вычислениях используем, но даже собственно числа. Это смотря как и чем считать.

“В теореме 3 разложение на миноры второго порядка будет.” Снова: в теореме 3 в левой части - определители матриц с одним замененным столбцом, а в правой - с двумя. Как определять значения этих определителей - личное дело исследователя. Можно приведением к диагональному виду. Тут, как я понимаю, миноры будут не нужны. Хотя, конечно, все со всем связано…

aamonster 28 июн в 21:41

Если бы я попал на тех людей, которые объяснили мне, что я повторяюсь - я бы вряд ли стал повторяться.

Вот именно это самая интересная часть в вашей истории. Выписанное вами тождество выглядит крайне простым и предположительно должно быть известно; формула для вычисления за O(n) определителя при замене столбца точно хорошо известна (через алгебраические дополнения, считать за O(n³) дураков нет). Почему вам на всё это не указали? Ну ладно ИИ, с него взятки гладки, но рецензируемый журнал?

Redfox111 вчера в 04:28

В том-то и дело, что журнал был нерецензируемым. В рецензируемый меня не взяли.

aamonster вчера в 06:21

А, ну вот всё и объяснилось.

Redfox111 вчера в 07:05

Ну так я про это в статье и написал в явном виде. Собственно потому и обратился к ИИ в качестве рецензента.

aamonster вчера в 07:08

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

Ну или промпт для ии на объяснение, почему именно не берут.

Redfox111 вчера в 04:46

“тождество выглядит крайне простым” - Ну, E=mc^2 выглядит еще проще. Хотелось бы, конечно, найти точный источник информации. Некоторые выкладки ранее в комментариях были даны, собираюсь разобраться в них.

“Ну ладно ИИ, с него взятки гладки” - Хочется надеется, что ИИ все-таки создан в помощь, а не во вред человеку. Поэтому закрывать глаза на недостатки ИИ не нужно. И если он “страдает” галлюцинациями и сикофантией, то с ними нужно бороться и знать как это делать. Так что свое общение с ИИ также считаю полезным.

aamonster вчера в 08:00

Насчёт полезности соглашусь. Наверняка после обсуждений тут лучше пользоваться этим инструментом научитесь как минимум вы сами, а возможно – ещё кто-то.

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

Redfox111 26 июн в 18:15

"ваше тождество тривиально следует из матричной леммы "
Для меня это тривиальным не было. Т.к. когда выводил свои теоремы - ничего не знал о матричной лемме и соответственно не мог ее использовать.

wataru 26 июн в 19:15

Т.к. когда выводил свои теоремы - ничего не знал о матричной лемме

Раз уж вы адепт ИИ, спросили бы у него задачу быстро пересчитать определитель матрицы, оно сразу выдает метод через лемму, заодно и ссылки на нее. В 50% случаев тупит и говорит, что оно работает за O(n^2), хотя на самом деле там O(n).

Redfox111 26 июн в 19:44

“Раз уж вы адепт ИИ” Я скорее адепт изучения и тестирования ИИ, а не его самого.

“спросили бы у него задачу быстро пересчитать определитель матрицы” Вообще и в статье и в коде (по ссылке) дан сравнительный материал для символьного и численного режимов (в том числе с алгоритмами Барейса и Берковица). Так что моей целью было не рассчитать быстро определитель, а понять какие преимущества может иметь “линейно-векторный” метод перед другими. И все это по запросам к ИИ.

“В 50% случаев тупит и говорит, что оно работает за O(n^2), хотя на самом деле там O(n).” Да, с этим тоже столкнулся.

wataru 26 июн в 19:36

Кстати, на заметку. Точно так же выводится еще более обобщенное тождество:
Пусть матрица k x k $B_{ij} = F_{k_i}(q_j)$ (в позиции ij сидит определитель матрицы A, где i-ый столбец заменен на j-ый вектор q).
Тогда $\det(B) = F_{k_1,..,k_k}(q_1,...,q_n) \det(A)^{k-1}$

Т.е. определитель A при замене k столбцов можно пересчитать через определители A при замене каждого из столбцов на один из новых.

В случае k=2 det(B) как раз дает вашу штуку вида AB-CD.

Для k=1 получается тривиальное тождество F_i(q) = F_i(q).

На практике это даст алгоритм пересчета определителя при замене любых k столбцов за O(k^3n) при O(n^3) предподсчете.

Redfox111 26 июн в 19:50

“Тогда \det(B) = F_{k_1,…,k_k}(q_1,…,q_n) \det(A)^{k-1} В случае k=2 det(B) как раз дает вашу штуку вида AB-CD.”

Не совсем понял, откуда из первой формулы взялась разность из второй ? Ведь речь тут идет не о блочной матрице ?

wataru 27 июн в 08:23

Матрица B 2x2 состоит из 4 чисел: F_i(q), F_j(q), F_i(q'), F_j(q'). Ее определитель как раз даст вашу формулу F_i(q) * F_j(q') - F_j(q) * F_i(q'). А справа как раз будет F_ij(q,q') det(A).

Т.е. при обобщении тождества на замену 3 столбцов будет F_ijk(q,q',q'') det(A)^2 = F_i(q)F_j(q')F_k(q'') + F_j(q)F_k(q')F_i(q'') + ... - F_k(q)F_j(q')F_k(q'') - 6 слагаемых как в определители матрицы 3x3.

Redfox111 26 июн в 21:58

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

wataru 27 июн в 08:30

Судя по-всему это обобщение формулы Якоби

Нет это прямое обобщение вашей формулы. При подстановке k=2 она и получается.Определитель матрицы с k замененными столбцами пересчитывается через определители матрицы, где один из изменяемых столбцов заменен на один из новых столбцов.

Источников не знаю, сам только что придумал. Думаю они где-то есть, но найти не могу. Вот берем тот вывод вашей формулы из матричной леммы, который я привел выше. И тупо вместо замены 2 столбцов заменяем 3. Матрицы V и U будут n x 3 а не n x 2. Опять же V^T= (I|0), а U - содержит 3 столбца q-A_i, q'-A_j, q''-A_k.

Расписываем матричную лемму, делаем те же самые замены A^-1 на миноры и оттуда матрица 3x3 из леммы, от которой надо подсчитать определитель, получится состоящая из F_i(q_j)/det(A). 1/det(A) выносим из определителя, оно вылезет со степенью 3, одна степень сократится с det(A) из матричной леммы.

Чуть позже скину формализованное доказательство

wataru 27 июн в 08:57

Вот выхлоп gemini с доказательством обобщенной формулы. Я все проверил, все рассуждения правильные:

1. Введение обозначений и постановка задачи

Пусть дана невырожденная квадратная матрица $A \in \mathbb{R}^{n \times n}$ .

Мы хотим найти определитель новой матрицы $\tilde{A}$ , в которой изменены k столбцов.

Пусть $J = \{j_1, j_2, \dots, j_k\}$ — индексы заменяемых столбцов.
Пусть $q_1, q_2, \dots, q_k \in \mathbb{R}^n$ — новые векторы, которые встанут на эти места.
Обозначим через оригинальный j-й столбец матрицы A.

Мы можем представить $\tilde{A}$ как сумму исходной матрицы и матрицы ранга $k$:

$\tilde{A} = A + UV^T$

Где $U, V \in \mathbb{R}^{n \times k}$ :

Матрица V содержит стандартные базисные векторы для выбора нужных столбцов: ее s-й столбец равен $e_{j_s}$ .
Матрица U содержит приращения столбцов: ее s-й столбец равен $u_s = q_s - a_{j_s}$ .

Тогда произведение — это матрица $n \times n$ , у которой в столбцах с индексами стоят векторы $q_s - a_{j_s}$ , а остальные столбцы нулевые.

2. Матричная лемма об определителях

Применим лемму об определителе (Matrix Determinant Lemma) для матрицы A и возмущений U, V:

$\det(\tilde{A}) = \det(A + UV^T) = \det(A) \det(I_k + V^T A^{-1} U)$

Наша задача сводится к вычислению определителя матрицы $M = I_k + V^T A^{-1} U$ размерности $k \times k$ .

3. Вычисление элементов матрицы M и сокращение

Рассмотрим элемент матрицы $W = V^T A^{-1} U$ , стоящий на пересечении r-й строки и s-го столбца (где $r, s \in \{1, \dots, k\}$ ).

Строки матрицы — это транспонированные базисные векторы $e_{j_r}^T$ .

Столбцы матрицы U — это векторы приращений $q_s - a_{j_s}$ .

$W_{rs} = e_{j_r}^T A^{-1} (q_s - a_{j_s})$

$W_{rs} = e_{j_r}^T A^{-1} q_s - e_{j_r}^T A^{-1} a_{j_s}$

Поскольку $a_{j_s}$ — это -й столбец самой матрицы A, то по определению обратной матрицы $A^{-1} a_{j_s} = e_{j_s}$ .

Тогда второе слагаемое превращается во внутреннее произведение двух базисных векторов, что дает символ Кронекера:

$e_{j_r}^T e_{j_s} = \delta_{rs}$

Получаем:

$W_{rs} = e_{j_r}^T A^{-1} q_s - \delta_{rs}$

Теперь подставим это в матрицу M:
$M_{rs} = (I_k)_{rs} + W_{rs} = \delta_{rs} + e_{j_r}^T A^{-1} q_s - \delta_{rs} = e_{j_r}^T A^{-1} q_s$

Единицы на диагонали из идеально сократились с , возникшими из-за вычитания оригинальных столбцов.

4. Переход к определителям с одним измененным столбцом

Разберем выражение $e_{j_r}^T A^{-1} q_s$ .

Умножение $e_{j_r}^T A^{-1}$ просто "вытаскивает" -ю строку из матрицы $A^{-1}$ .

Вспомним формулу элементов обратной матрицы через алгебраические дополнения (кофакторы). Если C — матрица алгебраических дополнений для A, то

$A^{-1} = \frac{1}{\det(A)} C^T$ .

Значит, элемент обратной матрицы равен:

$(A^{-1})_{i, l} = \frac{C_{l, i}}{\det(A)}$

Элемент i из -й строки матрицы $A^{-1}$ — это $\frac{C_{i, j_r}}{\det(A)}$ .

Умножим эту строку на вектор :

$M_{rs} = \sum_{i=1}^n (A^{-1})_{j_r, i} (q_s)_i = \sum_{i=1}^n \frac{C_{i, j_r}}{\det(A)} (q_s)_i = \frac{1}{\det(A)} \sum_{i=1}^n C_{i, j_r} (q_s)_i$

Сумма $\sum_{i=1}^n C_{i, j_r} (q_s)_i$ представляет собой классическое разложение определителя по

-му столбцу. Причем элементы этого столбца берутся из вектора , а все алгебраические дополнения $C_{i, j_r}$ — из оригинальной матрицы A.

Это в точности равно определителю матрицы A, у которой только один -й столбец заменен на вектор

Обозначим такую матрицу как $A(j_r \leftarrow q_s)$ .

$M_{rs} = \frac{\det(A(j_r \leftarrow q_s))}{\det(A)}$

5. Итоговая формула

Матрица M размерности $k \times k$ полностью состоит из элементов вида

$\frac{\det(A(j_r \leftarrow q_s))}{\det(A)}$ .

Вынесем скаляр $\frac{1}{\det(A)}$ из каждой из k строк (или столбцов) матрицы M при вычислении ее определителя:

$\det(M) = \frac{1}{\det(A)^k} \det \begin{pmatrix}\det(A(j_1 \leftarrow q_1)) & \dots & \det(A(j_1 \leftarrow q_k)) \\vdots & \ddots & \vdots \\det(A(j_k \leftarrow q_1)) & \dots & \det(A(j_k \leftarrow q_k))\end{pmatrix}$

Обозначим эту матрицу определителей как $D \in \mathbb{R}^{k \times k}$ , где $D_{rs} = \det(A(j_r \leftarrow q_s))$ .

Подставляем $\det(M)$ в исходную лемму:

$\det(\tilde{A}) = \det(A) \cdot \det(M) = \det(A) \cdot \frac{1}{\det(A)^k} \det(D)$

Итоговая формула:

$\det(\tilde{A}) = \det(A)^{1-k} \det(D)$

Где D — это матрица $k \times k$ , элемент которой $D_{rs}$ равен определителю исходной матрицы A, в которой -й столбец заменен на новый вектор .

Примечание: Обрати внимание, что элементы вне главной диагонали матрицы D — это определители матриц "смешанных" замен (мы ставим вектор , предназначенный для s-го столбца, на место r-го столбца).

Redfox111 27 июн в 15:50

Постараюсь вникнуть. Конечный результат выглядит привлекательно. Если он верен, то да, формула из теоремы 1 представляется частным случаем для матрицы размерности 2. Но в любом случае вряд ли можно называть подобный вывод тривиальным (даже для размерности 2). Я бы установил такую градацию:

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

Любой из этих пунктов, думаю, представляет интерес как новый полученный результат (по степени важности: от 1 до 3 по убыванию).

Зарегистрируйтесь на Хабре, чтобы оставить комментарий