Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 55
Это просто замечательно. Никогда не подозревал ранее, что благодаря матрицам можно вытворять такое. Спасибо за полезные примеры.
Действительно, хорошее направление для развития оптимизирующих компиляторов.
Напомнило Задачу о порядке перемножения матриц
Напомнило Задачу о порядке перемножения матриц
У вас нотация довольно необычная. Обычно в математике используются векторы-столбцы и умножают матрицы на векторы а не наоборот. Потратил минуту чтобы понять, почему же матрица выглядит именно так.
А вообще довольно интересно.
А вообще довольно интересно.
Вообще-то в математике есть много чего, в том числе и row-vector наравне с column-vector (обычно их определяют как матрицы 1xN и Nx1).
Более того, столбцы можно считать обычными векторами, а строки — ковекторами (функционалами на векторах), тогда произведение строки на столбец будет соответствовать применению функционала к вектору, а столбца на строку — взятию тензорного произведения вектора на функционал (и получится линейный оператор).
Таки тензоры рулят:)
Таки тензоры рулят:)
Можно, только без векторного пространства и преобразований координат в нём они ничем не отличаются от матриц 1xN и Nx1 )
Ну это один из способов записи (при фиксированном базисе). А тензорное произведение — это обобщение произведения матриц, которое, в свою очередь, обобщение, например, применения функционала к вектору.
А транспонирование матрицы — это свертка с \delta_i^j.
В общем, мне лично нравятся такие теории, которые выявляют общее в на первый взгляд существенно различных вещах.
Но это были так, мысли вслух)
А транспонирование матрицы — это свертка с \delta_i^j.
В общем, мне лично нравятся такие теории, которые выявляют общее в на первый взгляд существенно различных вещах.
Но это были так, мысли вслух)
а теперь, то же самое для
:D
loop 100000000
psw = md5(psw + "salt")
end:D
Гениально…
Когда читал про оптический компьютер, который фактически является укорителем перемножения матриц, то какраз думал про то, каким алгоритмом можно привести любой код к матричным вычислениям (а потом, получив их в виде математического выражения, а их можно упрощать, приводить к какому то другому виду, и т.п.)… осталось придумать, какой операция над матрицей должен стать операнд if then else… только ветвлений не хватает до полного катарсиса, а так же зависимость количества итераций цикла от значения операндов (одно следует из другого), чувствую это возможно, но как…
p.s. а теперь добавьте сюда параллельные вычисления ведь одновременные вычисления с разными переменными неплохо вписываются в одну операцию с матрицами…
Когда читал про оптический компьютер, который фактически является укорителем перемножения матриц, то какраз думал про то, каким алгоритмом можно привести любой код к матричным вычислениям (а потом, получив их в виде математического выражения, а их можно упрощать, приводить к какому то другому виду, и т.п.)… осталось придумать, какой операция над матрицей должен стать операнд if then else… только ветвлений не хватает до полного катарсиса, а так же зависимость количества итераций цикла от значения операндов (одно следует из другого), чувствую это возможно, но как…
p.s. а теперь добавьте сюда параллельные вычисления ведь одновременные вычисления с разными переменными неплохо вписываются в одну операцию с матрицами…
Спасибо за статью. Есть вопрос: можно ли реализовать(имеется ввиду через матричные преобразования) битовые операции: NOT, OR, AND (все операнды — переменные)?
если вместо сложения взять XOR, вместо умножения — AND, алгебраические тождества будут выполняться (получим вычисления в поле вычетов по модулю 2). NOT можно получить формулой NOT x = 1 XOR x
другой любопытный пример — пусть сложение OR, а умножение AND.
если взять матрицу A смежности графа (A[i,j]=1 если между i и j есть ребро), то A^2 — матрица достижимости пути за 2 шага, A^3 — за 3 и т.д… A^n — матрица связности (An[i,j]=1 если есть путь от i к j, n — число вершин графа, любой кратчайший путь от i к j не длинее n, поэтому степень выше n рассматривать избыточно). возведение в степень n для поиска матрицы связности тоже можно делать этим быстрым алгоритмом
другой любопытный пример — пусть сложение OR, а умножение AND.
если взять матрицу A смежности графа (A[i,j]=1 если между i и j есть ребро), то A^2 — матрица достижимости пути за 2 шага, A^3 — за 3 и т.д… A^n — матрица связности (An[i,j]=1 если есть путь от i к j, n — число вершин графа, любой кратчайший путь от i к j не длинее n, поэтому степень выше n рассматривать избыточно). возведение в степень n для поиска матрицы связности тоже можно делать этим быстрым алгоритмом
Вот только матрицы перемножаются дольше, чем O(n^2), так что этот алгоритм будет работать дольше, чем O(n^2 log n), в то время как банальный поиск в ширину даст сложность O(n+m) для списка ребер (где m — количество ребер), или, для матрицы смежности, O(n^2).
но поиск в ширину/глубину — последовательный алгоритм (стек, очередь). распараллелить можно попробовать, но теории нет, чтобы сделать это формально, не задумываясь
Зато у него константа куда лучше, чем у быстрого перемножения матриц. И пригодные для практического использования алгоритмы умножения вроде бы имеют сложность O(n^{2+epsilon}) для, как правило, достаточно большого (>0.1) эпсилон.
Так что, поскольку это всё есть смысл обсуждать только для очень больших графов (десятки тысяч и больше вершин), то распараллеливание едва ли спасет алгоритм с худшей ассимптотикой и константой.
К тому же поиск пусть не в ширину, а в глубину вроде бы вполне красиво параллелится.
Так что, поскольку это всё есть смысл обсуждать только для очень больших графов (десятки тысяч и больше вершин), то распараллеливание едва ли спасет алгоритм с худшей ассимптотикой и константой.
К тому же поиск пусть не в ширину, а в глубину вроде бы вполне красиво параллелится.
и всё-таки, у этого подхода есть практическое применение, опережающее обход в ширину.
это когда нужно найти матрицу расстояний для каждой пары i, j
только уже не булевские операции надо использовать, а сложение обычное, а умножение — min
это когда нужно найти матрицу расстояний для каждой пары i, j
только уже не булевские операции надо использовать, а сложение обычное, а умножение — min
Ну да, для матрицы расстояний это получается обобщением алгоритма Флойда (который получается, если вместо быстрого перемножения матриц использовать обычное). Но для матрицы достижимости такой метод всё-таки неинтересен.
Кстати, а алгоритмы быстрого перемножения матриц не завязаны на, например, дистрибутивность умножения (я этого не помню, а смотреть и думать сейчас лень)?
Флойдом можно найти матрицу достижимости за куб — на практике это должно быть всегда быстрее, чем возведение матрицы смежности в степень.
Нет, конечно. Быстрое умножение матриц имеет не такую уж большую константу.
Даже если при больших N быстрое возведение в степень с быстрым умножением будут быстрее, чем флойд, я бы все равно остановился на флойде, хотя бы из-за его простоты.
Вариант с поисками в ширину тоже приятный — у него тоже кубическая сложность на плотных графах (а на разряженных еще меньше), но зато его можно легко запустить на нескольких процессорах сразу. Аналогично, если надо найти не матрицу достижимости, а все кратчайшие пути, на современном железе, наверное, N дийкстр будут очень эффективны, потому что их можно тоже легко распараллелить, сохраняя все ту же кубическую сложность.
Вариант с поисками в ширину тоже приятный — у него тоже кубическая сложность на плотных графах (а на разряженных еще меньше), но зато его можно легко запустить на нескольких процессорах сразу. Аналогично, если надо найти не матрицу достижимости, а все кратчайшие пути, на современном железе, наверное, N дийкстр будут очень эффективны, потому что их можно тоже легко распараллелить, сохраняя все ту же кубическую сложность.
Угу. А пузырек вместо быстрой сортировки из-за его простоты Вы не выберете? Как и перемножение матриц «в лоб» вместо быстрых алгоритмов?)
Простота реализации важна в некоторых случаях, но далеко не во всех. Вы, думаю, не обрадуетесь видеокартам в 5 раз дороже и в 10 раз медленнее из-за того, что их разработчики, как и Вы, предпочитают медленные, но простые алгоритмы.
А все стандартные алгоритмы быстрого перемножения матриц вроде бы прекрасно параллелятся.
Простота реализации важна в некоторых случаях, но далеко не во всех. Вы, думаю, не обрадуетесь видеокартам в 5 раз дороже и в 10 раз медленнее из-за того, что их разработчики, как и Вы, предпочитают медленные, но простые алгоритмы.
А все стандартные алгоритмы быстрого перемножения матриц вроде бы прекрасно параллелятся.
Я думаю причиной этого небольшого разногласия является мое устаревшее представление о быстром умножении. Лучшее, что я знаю, работает за степень примерно 2.7. На графе с 10000 вершин разница с кубом будет в 15 раз, но быстрое возведение в степень потребует еще логарифм, который от 10000 даст 14, и смысл потеряется, потому что у быстрого умножения костанта выше, чем у флойда.
Если есть алгоритм быстрого умножения заметно быстрее, чем за (N^2.7), то тогда мои размышления о флойде, вероятно, заметно отличались бы.
Если есть алгоритм быстрого умножения заметно быстрее, чем за (N^2.7), то тогда мои размышления о флойде, вероятно, заметно отличались бы.
Из применимых на практике вроде бы быстрее всего прямые суммы Шенхаге, которые вроде бы работают примерно за n^2.52. Что дает выигрыш в 63 раза по сравнению с лобовым.
С учетом логарифма — выигрыш в 6 раз на 10000 и в 15 на 100. Что, скорее всего, с лихвой перекрывает константу.
С учетом логарифма — выигрыш в 6 раз на 10000 и в 15 на 100. Что, скорее всего, с лихвой перекрывает константу.
Вообще я, быть может, высказался немного резко, приношу извинения. Просто мне очень уж не нравятся фразы вида «даже если по-другому будет лучше, всё равно сделаю как проще».
Асимптотически лучший алгоритм перемножения матриц имеет экспоненту 2.373 (т.е. сложность n2.373)
Есть задачи, которые решаются возведением матрицы смежности графа в степень.
Например: codeforces.ru/contest/147/problem/B.
Например: codeforces.ru/contest/147/problem/B.
Зависит от способа записи:)
NOT X при любом разумном способе записывается как 2^k — 1 — X.
А вот OR и AND, скорее всего, ни при какой разумной записи выразить будет нельзя. Разве что хранить вектор значений всех возможных функций наших переменных:)
NOT X при любом разумном способе записывается как 2^k — 1 — X.
А вот OR и AND, скорее всего, ни при какой разумной записи выразить будет нельзя. Разве что хранить вектор значений всех возможных функций наших переменных:)
я имел ввиду матрицы не из чисел, а из bool
Ну, в Z_2 AND вообще нелинейная операция и выразить ее линейно нельзя)
не понял утверждения.
умножение в действительных числах тоже не выражается через сложение.
умножение в действительных числах тоже не выражается через сложение.
Вопрос был «можно ли реализовать(имеется ввиду через матричные преобразования) битовые операции».
Насколько я понимаю, имелся в виду тот же метод, что и в статье, т.е. вектор из переменных (и, быть может, побочных значений) мы линейным преобразованием переделываем в вектор функций от этих переменных (и, быть может, побочных значений).
Утверждение было: преобразование (x, y) -> (x AND y, z(x, y)) нелинейно над Z_2^2 ни для какой функции z.
Насколько я понимаю, имелся в виду тот же метод, что и в статье, т.е. вектор из переменных (и, быть может, побочных значений) мы линейным преобразованием переделываем в вектор функций от этих переменных (и, быть может, побочных значений).
Утверждение было: преобразование (x, y) -> (x AND y, z(x, y)) нелинейно над Z_2^2 ни для какой функции z.
Z_2 операция AND и есть умножение
Произведение любых матриц ассоциативно, не только квадратных, разве нет?
Оригинальный подход — за него однозначный плюс :) Хоть и малоприменим на практике, так как позволяет брать только уж совсем специфичные случаи.
Простая идея, простая реализация, молодец! Подобный DSL очень бы пригодился на всяких codeforces/topcoder :)
Отличная статья, приятно видеть такие на хабре. Она почти вернула мне веру в то, что математика в программировании таки небесполезна :)
Всегда знал, что матрицами можно «сворачивать» вычисления, использовал это и в расчетах четырехполюсников, и когда с 3D разбирался.
Но никогда не понимал, ПОЧЕМУ это работает? ПОЧЕМУ блин так происходит, А?
То есть, я пользуюсь аппаратом, но не понимаю, почему он работает.
Я уже считаю, что это какое-то непознанное свойство материи или там пространства-времени, которое так отображается в математике нашего мира.
Но никогда не понимал, ПОЧЕМУ это работает? ПОЧЕМУ блин так происходит, А?
То есть, я пользуюсь аппаратом, но не понимаю, почему он работает.
Я уже считаю, что это какое-то непознанное свойство материи или там пространства-времени, которое так отображается в математике нашего мира.
«Почему» — очень сложный вопрос. То, что он работает, можно доказать. Является ли это свойством реальности или лишь свойством нашей теории — сказать, скорее всего, невозможно.
Причем описание матрицами линейных преобразований — это еще очень простой аппарат. Вот то, что работают дифференциальные формы, тензорный анализ на гильбертовых пространствах, обобщенные функции и т.д. — гораздо удивительнее.
Пользуясь случаем, в очередной раз прорекламирую статью «Непостижимая эффективность математики в естественных науках».
Причем описание матрицами линейных преобразований — это еще очень простой аппарат. Вот то, что работают дифференциальные формы, тензорный анализ на гильбертовых пространствах, обобщенные функции и т.д. — гораздо удивительнее.
Пользуясь случаем, в очередной раз прорекламирую статью «Непостижимая эффективность математики в естественных науках».
Это действительно замечательно и я всерьёз намерен использовать это для ускорения вычислений. Жаль, правда, что такой язык не обладает полнотой, т.к. может работать только с циклами, для которых точно известно количество итераций, что даёт очень узкий класс решаемых задач (это даже не примитивно-рекурсивные, для которых известно максимальное количество итераций — ещё уже). И поэтому, наверное, языком программирования это вообще называться не может. Или я что-то проглядел?
Алгоритм кстати на столько прост, что его можно автоматически внедрять в код, подставляя его в код вместо циклов… ведь во время выполнения больше случаев, когда количество итераций известно…
p.s. я считаю идею нужно развивать, ведь математические выражения можно упрощать не только через возведения в степень (правда алгоритм получается не совсем тривиальным)… основная польза от этого — нереально крутые возможности по распараллеливанию кода (матричные вычисления этому очень способствуют).
p.s. я считаю идею нужно развивать, ведь математические выражения можно упрощать не только через возведения в степень (правда алгоритм получается не совсем тривиальным)… основная польза от этого — нереально крутые возможности по распараллеливанию кода (матричные вычисления этому очень способствуют).
Любобытно.
Возникла идея: а что если расширить цикл и на нецелые числа и вычислять степени матриц с помощью разложения в ряд Тейлора? Тогда возможно будет вычислять корни.
Например вот так: loop 0.5. Не уверен, что это корректная операция, но попробовать стоит.
Возникла идея: а что если расширить цикл и на нецелые числа и вычислять степени матриц с помощью разложения в ряд Тейлора? Тогда возможно будет вычислять корни.
Например вот так: loop 0.5. Не уверен, что это корректная операция, но попробовать стоит.
Вычислять корни не получится — умножать-то можно только на константу.
умножение (только на константу)
Вы внимательно прочитали, что я написал?
Я говорил про возведение матриц в дробную степень и умножение переменных на константу тут совсем не при чем.
Я говорил про возведение матриц в дробную степень и умножение переменных на константу тут совсем не при чем.
Ну расскажите мне, как умножив на какую-либо константу половину раза, Вы сможете вычислить корень из переменной (корни из констант, очевидно, не нужны — это те же константы).
Предположим, что мы как-то придумали возведение в степень. Скомбинировали тысячу различных извращений (включая ряды Тейлора, Маклорена, Лорана — кого пожелаете) и получили его (а точнее — её, чудесно-волшебную матрицу, возводящую элементы любого вектора в некоторую степень, допустим, 3). Т.е. мы получили для вектора v (пусть он будет таким: [ a b 1 ]) матрицу M, такую, что v * M = [ a³ … … ]. Тогда имеем для произвольного λ:
с другой стороны
Таким образом, λa³ = (λa)³, a = 0 (возводить нули в степень скучно) => λ = λ³, но у нас-то λ любое!
Очевидно, что если бы такая матрица M существовала, но она должна была бы зависеть от текущих переменных, т.е. являться функцией вектора M(v). А это ломает всё, что мы здесь придумали — цепочку вычислений
v = v * M1v
v = v * M2v
…
v = v * Mnv
(для упрощения скобки у вызовов функции опущены) Мы уже не сможем «свернуть» так же просто, как в статье. Разве что
v = v * M1v * M2(v * M1v) * M3(v * M1v * M2(v * M1v)) * … * Mn(v * M1v * M2(v * M1v) * … * Mn-1(…))
однако вычислять это в таком виде — очевидно, феерическая глупость.
Предположим, что мы как-то придумали возведение в степень. Скомбинировали тысячу различных извращений (включая ряды Тейлора, Маклорена, Лорана — кого пожелаете) и получили его (а точнее — её, чудесно-волшебную матрицу, возводящую элементы любого вектора в некоторую степень, допустим, 3). Т.е. мы получили для вектора v (пусть он будет таким: [ a b 1 ]) матрицу M, такую, что v * M = [ a³ … … ]. Тогда имеем для произвольного λ:
λ[ a b 1 ] * M = [ λa λb λ ] * M = [ (λa)³ … … ]с другой стороны
λ[ a b 1 ] * M = λ ([ a b 1 ] * M) = λ [ a³ … … ] = [ λa³ … … ]Таким образом, λa³ = (λa)³, a = 0 (возводить нули в степень скучно) => λ = λ³, но у нас-то λ любое!
Очевидно, что если бы такая матрица M существовала, но она должна была бы зависеть от текущих переменных, т.е. являться функцией вектора M(v). А это ломает всё, что мы здесь придумали — цепочку вычислений
v = v * M1v
v = v * M2v
…
v = v * Mnv
(для упрощения скобки у вызовов функции опущены) Мы уже не сможем «свернуть» так же просто, как в статье. Разве что
v = v * M1v * M2(v * M1v) * M3(v * M1v * M2(v * M1v)) * … * Mn(v * M1v * M2(v * M1v) * … * Mn-1(…))
однако вычислять это в таком виде — очевидно, феерическая глупость.
Привет — два года спустя пользователь hx0 написал подробную статьи про свой модуль оптимизации байт-кода Python, основанный на алгоритме из твоей статьи. Оставляю этот комментарий, чтобы поместить линк на более новую статью: «Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень».
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования