Возьмем граф с изначально нулевыми весами ребер. Найдем в нем любое минимальное остовное дерево. Увеличим вес каждого ребра в этом дереве на 1. Снова найдем минимальное остовное дерево относительно новых весов, и снова увеличим вес каждого ребра в этом дереве на 1, и так далее.
Пусть для ребра е, x_е — это доля деревьев, содержащих е. Будет ли в таком процессе предел у величин x_e, и если да, то что это за точка?
Оказывается, предел есть. Его можно описать через оптимальные разбиения графа (2007), и он супер важен для алгоритма динамического минимального разреза.
Но этот предел можно описать более геометрично: это проекция нуля на политоп остовных деревьев. То есть, точка в выпуклой оболочке индикаторных векторов всех возможных остовных деревьев, у которой наименьшая норма.
На графиках показано, как убывает погрешность х с количеством деревьев.
Пусть для ребра е, x_е — это доля деревьев, содержащих е. Будет ли в таком процессе предел у величин x_e, и если да, то что это за точка?
Оказывается, предел есть. Его можно описать через оптимальные разбиения графа (2007), и он супер важен для алгоритма динамического минимального разреза.
Но этот предел можно описать более геометрично: это проекция нуля на политоп остовных деревьев. То есть, точка в выпуклой оболочке индикаторных векторов всех возможных остовных деревьев, у которой наименьшая норма.
На графиках показано, как убывает погрешность х с количеством деревьев.
👍12🔥8❤3
О гамильтониане Ферми-Хаббарда
(fermions vs. hard-bosons)
Недавно делал семинар по численным методам, в том числе с ответом на вопрос о разнице между хард-бозонами и фермионами. Мы рассматриваем частицы на решётке. Если взять бозоны и выкрутить энергию на узле в +∞, то эффективно числа заполнения будут {0,1}, как и у фермионов. Будет ли в плане динамики между ними разница?
Разница будет, если у нас случится перепрыгивание одной частицы через другую (второй слайд) — в матричном элементе гамильтониана возникнет знак минус. Действительно, мы можем рассматривать базисные состояния, как вакуум на который подействовали операторами рождения (первый слайд). А если происходит такое туннелирование, то нужно упорядочить состояние, чтобы выразить результат через наш базис. Для бозонов на разных узлах операторы коммутируют и про упорядочивание можно не думать, а вот для фермионов они антикоммутируют
К слову в одномерном случае таких перепрыгиваний не будет, так что гамильтонианы будут идентичными. Это позволяет сводить 1d спиновые цепочки к невзаимодействующим фермионам (Jordan-Wigner transforamation), которые легко решаются)
P.S. Да, фермионы подразумевал спин-поляризованные (неразличимые)
(fermions vs. hard-bosons)
Недавно делал семинар по численным методам, в том числе с ответом на вопрос о разнице между хард-бозонами и фермионами. Мы рассматриваем частицы на решётке. Если взять бозоны и выкрутить энергию на узле в +∞, то эффективно числа заполнения будут {0,1}, как и у фермионов. Будет ли в плане динамики между ними разница?
Разница будет, если у нас случится перепрыгивание одной частицы через другую (второй слайд) — в матричном элементе гамильтониана возникнет знак минус. Действительно, мы можем рассматривать базисные состояния, как вакуум на который подействовали операторами рождения (первый слайд). А если происходит такое туннелирование, то нужно упорядочить состояние, чтобы выразить результат через наш базис. Для бозонов на разных узлах операторы коммутируют и про упорядочивание можно не думать, а вот для фермионов они антикоммутируют
AB=-BA. Так что когда фермион туннелирует, то в матричном элементе возникает множитель (-1)^{# частиц через которые перепрыгнули}.К слову в одномерном случае таких перепрыгиваний не будет, так что гамильтонианы будут идентичными. Это позволяет сводить 1d спиновые цепочки к невзаимодействующим фермионам (Jordan-Wigner transforamation), которые легко решаются)
P.S. Да, фермионы подразумевал спин-поляризованные (неразличимые)
❤13🔥5
Как генерировать (плохие) разрезы графов с помощью случайных деревьев
Возьмем граф - квадратную сетку n на n. Сгенерируем в нем случайное остовное дерево*. На первой картинке цветом показано расстояние от данной вершины до вершины в левом верхнем углу, если двигаться по ребрам дерева.
Для разреза графа определим sparsity как значение (количество разрезанных ребер)/(количество вершин в меньшей части). Нахождение sparsest cut — это известная NP-сложная задача.
На второй картинке показан разрез графа с наибольшей sparsity, который пересекается нашим остовным деревом ровно один раз. Насколько хорошее приближение у нас получилось? Спойлер: совсем не хорошее.
Полученная sparsity убывает как n^-0.75 (третья картинка). Минимальная sparsity равна 2 / n.
Зато можно сказать, что граница разреза имеет размерность Хаусдорфа 1.25 (в пределе мелкой сетки). Интересно, что такая же размерность у loop-erased random walk. Будет интересно, если кто-то докажет равенство этих размерностей.
Возьмем граф - квадратную сетку n на n. Сгенерируем в нем случайное остовное дерево*. На первой картинке цветом показано расстояние от данной вершины до вершины в левом верхнем углу, если двигаться по ребрам дерева.
Для разреза графа определим sparsity как значение (количество разрезанных ребер)/(количество вершин в меньшей части). Нахождение sparsest cut — это известная NP-сложная задача.
На второй картинке показан разрез графа с наибольшей sparsity, который пересекается нашим остовным деревом ровно один раз. Насколько хорошее приближение у нас получилось? Спойлер: совсем не хорошее.
Полученная sparsity убывает как n^-0.75 (третья картинка). Минимальная sparsity равна 2 / n.
Зато можно сказать, что граница разреза имеет размерность Хаусдорфа 1.25 (в пределе мелкой сетки). Интересно, что такая же размерность у loop-erased random walk. Будет интересно, если кто-то докажет равенство этих размерностей.
❤16🔥5
О сложности судоку
(или о хороших головоломках)
Что значит, что задача сложная? Возьмём к примеру судоку. С точки зрения компьютера мы могли бы запустить DFS и дальше размер дерева поиска решения и был бы сложностью. То есть пробуем поставить в пустой квадрат цифру, двигаемся дальше и если приходим к противоречию, то понимаем ошибочность предположения. Guess and try. Но делать так самому не очень интересно.
Вообще хорошее судоку составлено так, что каждый следующий шаг может быть получен из некоторых логических соображений. Например на картинке видно, что в одном из жёлтых квадратов должна стоять 6, поэтому в зелёном её быть не может — там 3. Так что решение сводится к тому что ищется некоторый паттерн, и если нашли то можем уменьшить пространство вариантов (хороший зоопарк паттернов).
Получается сложность сводится к самому сложному паттерну, необходимого для решения. Так и сделал у себя на сайте (картинка с него же). Делаем солвер с техниками (или берём готовый): генерируем возможное заполнение (их всего 5.5B с точностью до симметрий), убираем подсказки до минимального набора (убрать любую следующую приведёт к потере единственности решения) и дальше смотрим каким набором паттернов это решается.
В общем предлагаю вниманию мой минималистичный сайт с 5 уровнями сложности и автоматизированными заметками (включите в настройках prefill, auto clear и нажмите new game):
https://qdiag.xyz/sudoku/
(или о хороших головоломках)
Что значит, что задача сложная? Возьмём к примеру судоку. С точки зрения компьютера мы могли бы запустить DFS и дальше размер дерева поиска решения и был бы сложностью. То есть пробуем поставить в пустой квадрат цифру, двигаемся дальше и если приходим к противоречию, то понимаем ошибочность предположения. Guess and try. Но делать так самому не очень интересно.
Вообще хорошее судоку составлено так, что каждый следующий шаг может быть получен из некоторых логических соображений. Например на картинке видно, что в одном из жёлтых квадратов должна стоять 6, поэтому в зелёном её быть не может — там 3. Так что решение сводится к тому что ищется некоторый паттерн, и если нашли то можем уменьшить пространство вариантов (хороший зоопарк паттернов).
Получается сложность сводится к самому сложному паттерну, необходимого для решения. Так и сделал у себя на сайте (картинка с него же). Делаем солвер с техниками (или берём готовый): генерируем возможное заполнение (их всего 5.5B с точностью до симметрий), убираем подсказки до минимального набора (убрать любую следующую приведёт к потере единственности решения) и дальше смотрим каким набором паттернов это решается.
В общем предлагаю вниманию мой минималистичный сайт с 5 уровнями сложности и автоматизированными заметками (включите в настройках prefill, auto clear и нажмите new game):
https://qdiag.xyz/sudoku/
❤13🔥10
Фракталы Ньютона
(возвращение к старому)
Маленькая, но довольно интересная вещь.
Напоминание:
Метод Ньютона для поиска корней функции f(x) заключается в последовательном применении к некоторому исходному значению x₀ отображения
xₙ₊₁ = xₙ – f(xₙ) / f'(xₙ).
При "хороших" f и x₀ последовательность {xₙ} сходится к одному из корней f.
Если применять метод Ньютона для
f(x) = x² + 1,
начав с некоторого вещественного x₀, то вроде бы ничего особо интересного не получим. Точки будут скакать туда-сюда (рис. 1).
Но метод Ньютона работает много над какими полями, в частности над комплексными числами.
Если начать с
x₀ = 1 + i,
последовательность быстро сойдётся к i (рис. 2), а если, скажем, с
x₀ = 5 – 2i,
то к –i (рис. 3).
Несложно доказать, что области, откуда последовательность будет приходить в соответствующий корень, выглядят очень просто: это верхняя и нижняя полуплоскость.
На рис. 4 каждая точка из решётки, приближающей квадрат со стороной 2 вокруг нуля, окрашена в цвет, отвечающий тому корню, куда придёт последовательность.
Этот результат понятен, и ясно, как обобщить его на произвольный многочлен второй степени.
А что будет, если корней больше?
Получатся (просто по определению) множества Фату для рассматриваемого отображения. Это фрактальные множества, которые можно нарисовать численно, просто беря точки из решётки.
Два примера показаны на рис. 5 и 6.
Можно заметить, что отображения всегда выглядят довольно просто:
xₙ₊₁ = xₙ – ( Σᵢ (xₙ – rᵢ)⁻¹ )⁻¹,
где {rᵢ} — корни f.
Точки, не попавшие ни в одно из этих множеств Фату, образуют множество Жюлиа (рис. 7 и 8). В самом первом примере это множество было просто вещественной осью (это, разумеется, самый лучший одномерный фрактал).
Описанные картины называются (довольно естественно) фракталами Ньютона.
В комментариях .nb, в котором можно построить что-нибудь своё. Правда, вы не найдёте там каких-то продвинутых погромистских методов.
(возвращение к старому)
Маленькая, но довольно интересная вещь.
Напоминание:
Метод Ньютона для поиска корней функции f(x) заключается в последовательном применении к некоторому исходному значению x₀ отображения
xₙ₊₁ = xₙ – f(xₙ) / f'(xₙ).
При "хороших" f и x₀ последовательность {xₙ} сходится к одному из корней f.
Если применять метод Ньютона для
f(x) = x² + 1,
начав с некоторого вещественного x₀, то вроде бы ничего особо интересного не получим. Точки будут скакать туда-сюда (рис. 1).
Но метод Ньютона работает много над какими полями, в частности над комплексными числами.
Если начать с
x₀ = 1 + i,
последовательность быстро сойдётся к i (рис. 2), а если, скажем, с
x₀ = 5 – 2i,
то к –i (рис. 3).
Несложно доказать, что области, откуда последовательность будет приходить в соответствующий корень, выглядят очень просто: это верхняя и нижняя полуплоскость.
На рис. 4 каждая точка из решётки, приближающей квадрат со стороной 2 вокруг нуля, окрашена в цвет, отвечающий тому корню, куда придёт последовательность.
Этот результат понятен, и ясно, как обобщить его на произвольный многочлен второй степени.
А что будет, если корней больше?
Получатся (просто по определению) множества Фату для рассматриваемого отображения. Это фрактальные множества, которые можно нарисовать численно, просто беря точки из решётки.
Два примера показаны на рис. 5 и 6.
Можно заметить, что отображения всегда выглядят довольно просто:
xₙ₊₁ = xₙ – ( Σᵢ (xₙ – rᵢ)⁻¹ )⁻¹,
где {rᵢ} — корни f.
Точки, не попавшие ни в одно из этих множеств Фату, образуют множество Жюлиа (рис. 7 и 8). В самом первом примере это множество было просто вещественной осью (это, разумеется, самый лучший одномерный фрактал).
Описанные картины называются (довольно естественно) фракталами Ньютона.
В комментариях .nb, в котором можно построить что-нибудь своё. Правда, вы не найдёте там каких-то продвинутых погромистских методов.
👍13🔥4❤1
О красивом
(или как красивое оказалось оптимальным)
В 2016 выходит статья, где предлагается несколько симметричных алгоритмов матричного умножения. Авторы прямо в абстракте пишут
А потом в 2025 выходит работа, где тщательно оптимизировали численную устойчивость схем матричного умножения и пришли к той же самой симметричной схеме 2016 года! То есть, так получилось, что сначала скорее из соображений эстетики появившаяся схема, оказалась около оптимальной в плане численной устойчивости)
(или как красивое оказалось оптимальным)
В 2016 выходит статья, где предлагается несколько симметричных алгоритмов матричного умножения. Авторы прямо в абстракте пишут
Хотя эти новые алгоритмы не улучшают известные верхние границы (...), они красивы сами по себе
А потом в 2025 выходит работа, где тщательно оптимизировали численную устойчивость схем матричного умножения и пришли к той же самой симметричной схеме 2016 года! То есть, так получилось, что сначала скорее из соображений эстетики появившаяся схема, оказалась около оптимальной в плане численной устойчивости)
🔥26
О радугах
(наблюдение дисперсии в домашних условиях)
Если взять много небольших капелек (~ мм), то каждая из них будет работать и как линза, и как призма, создавая такой очаровательный ландшафт. Тут из-за влажности вот сконденсировались. Я удивился увидеть симметричные радуги [красный-фиолетовый-красный], по-моему никогда раньше такого не видел)
(наблюдение дисперсии в домашних условиях)
Если взять много небольших капелек (~ мм), то каждая из них будет работать и как линза, и как призма, создавая такой очаровательный ландшафт. Тут из-за влажности вот сконденсировались. Я удивился увидеть симметричные радуги [красный-фиолетовый-красный], по-моему никогда раньше такого не видел)
❤15🔥11
Графики каждый день (почти)
Как вы думаете, чему равна лучшая известная вычислительная сложность умножения двух n-bitных чисел?
Как вы думаете, какая вычислительная сложность у нахождения медианного значения в множестве из n чисел?
// медиана -- число, которое оказалось бы поседередине, после сортировки множества
// медиана -- число, которое оказалось бы поседередине, после сортировки множества
Anonymous Quiz
4%
O(n²)
44%
O(n log n)
42%
O(n)
9%
O(√n)
🔥5❤4
Forwarded from Мишанина
Thermodynamic computing
Сегодня хочу рассказать про статью компании Normal Computing о термодинамических вычислениях. Ребята делают ASIC(Application Specific Integrated Circuit), который может более быстро и энергоэффективно считать примитивы AI моделей. В статье представлен proof-of-concept такого чипа, демонстрируется выигрыш в скорости и энергоэффективности на порядок по сравнению с GPU Nvidia A6000. В будущем обещают улучшение энергоэффективности х1000
Авторы называют свою разработку physics-based ASIC, так как отказываются от цифровой логики в пользу более энергоэффективной и быстрой аналоговой логики. По сути делают классический симулятор: берут физическую систему, запускают её динамику, измеряют состояние, а потом по измеренным состояниям делают инверсию матрицы, считают детерминант или сэмплируют точки из нужного распределения (по сути алгоритм Метрополиса-Гастингса в железе). С точки зрения физики в демонстрационном чипе всё устроено просто: есть набор rlc-контуров(элементарные ячейки) с ёмкостной связью между ними. На rlc-контуры подаются токи i с некоторым шумом(пока от цифрового генератора), и динамика связанной системы контуров описывается системой стохастических дифференциальных уравнений Ланжевена. После установления равновесия можно измерить напряжения v и получить сэмплы из нужного нам нормального распределения.
Контроллируя силу связей(ёмкость конденсаторов), можно задавать матрицу ковариации нормального распределения для сэмплирования или матрицу, от которой хочется посчитать детерминант/обратную матрицу. Есть даже отдельная статья про термодинамическую линейную алгебру. В общем можно считать всё что душе угодно, что можно оценить как статистику от состояний системы
Things to consider
Interesting facts
Сегодня хочу рассказать про статью компании Normal Computing о термодинамических вычислениях. Ребята делают ASIC(Application Specific Integrated Circuit), который может более быстро и энергоэффективно считать примитивы AI моделей. В статье представлен proof-of-concept такого чипа, демонстрируется выигрыш в скорости и энергоэффективности на порядок по сравнению с GPU Nvidia A6000. В будущем обещают улучшение энергоэффективности х1000
Авторы называют свою разработку physics-based ASIC, так как отказываются от цифровой логики в пользу более энергоэффективной и быстрой аналоговой логики. По сути делают классический симулятор: берут физическую систему, запускают её динамику, измеряют состояние, а потом по измеренным состояниям делают инверсию матрицы, считают детерминант или сэмплируют точки из нужного распределения (по сути алгоритм Метрополиса-Гастингса в железе). С точки зрения физики в демонстрационном чипе всё устроено просто: есть набор rlc-контуров(элементарные ячейки) с ёмкостной связью между ними. На rlc-контуры подаются токи i с некоторым шумом(пока от цифрового генератора), и динамика связанной системы контуров описывается системой стохастических дифференциальных уравнений Ланжевена. После установления равновесия можно измерить напряжения v и получить сэмплы из нужного нам нормального распределения.
Контроллируя силу связей(ёмкость конденсаторов), можно задавать матрицу ковариации нормального распределения для сэмплирования или матрицу, от которой хочется посчитать детерминант/обратную матрицу. Есть даже отдельная статья про термодинамическую линейную алгебру. В общем можно считать всё что душе угодно, что можно оценить как статистику от состояний системы
Things to consider
💡 В текущей работе источником случайности является цифровой генератор, но можно подумать про сценарий, в котором случайность появляется за счёт дальнейшей миниатюризации компонент чипа. Например, при уменьшении транзистора увеличивается вероятность туннелирования электронов через gate, а также нагрев, что может делать процесс недетерминированным и ломать цифровую логику. Возможно, этот же эффект получится использовать для масштабирования термодинамических вычислений💡 Авторы отмечают, что использование нелинейности в виде транзистора может существенно расширить множество доступных задач. Например, появится возможность использовать методы оптимизации второго порядка вместо градиентного спуска при той же сложности для тренировки нейросеток❗️ Неидеальность электронных компонент и полносвязность архитектуры ограничивают масштабируемость и точность. Также сложность алгоритмов зависит от необходимой точности решения и времени установления равновесия в системе, которая определяется спектром матрицы связей(числом обусловленности)
Interesting facts
📌
Co-founder/CEO
Faris Sbahi
и chief scientist Normal Computing
Patrick Coles
также занимаются квантовыми вычислениями. У второго, например, есть
обзор по вариационным квантовым алгоритмам
почти на 4к цитирований
📌
Помимо Normal Computing термодинамические вычисления делают
Extropic.
У Lex Fridman есть
подкаст с
основателем Extropic Guillaume Verdon, который тоже кстати из квантовых вычислений пришёл
📌
Из чего-то похожего, но более зрелого есть стартап
Etched.
Они делают ASIC под архитектуру трансформера(T в названии ChatGPT). Утверждают, что один их чип Sohu заменяет 20 видеокарт H100. Разработка ASIC и их интеграция в существующую инфраструктуру обычно очень дорогая, интересно что из этого выйдет. Пока им дали 120М$, что, как будто, не очень много по меркам инвестиций в ИИ. Как я понял, сейчас основное ограничение чипа Etched в memory bandwidth, что делает его хуже карточек от Nvidia (скорость обработки данных у Etched выше, но сами данные подгружаются медленно)
📌
Оказывается, есть целый
журнал
от Nature про unconventional computing
📌
У Normal Computing есть библиотека
thermox
на JAX для моделирования термодинамического компьютера. Также они работают над
AI-решением
для ускорения разработки кастомных чипов
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥17
Графики каждый день (почти)
О том как перемножать матрицы n×n (I. или как метрополисом оптимально по графу на 2⁶⁴ вершин шагал) На компьютере хорошо складывать числа, а не умножать, поэтому если бы умножать матрицы 2х2 можно было бы не за 8 умножений, а за 7, то всё стало бы немного…
This media is not supported in your browser
VIEW IN TELEGRAM
О том как перемножать матрицы III
(canonical polyadic decomposition онлайн, без регистрации)
Выше писал, что умножать матрицы 2х2 можно не за 8 умножений, а за 7. И аналогично для 3х3 есть алгоритм Ладермана, делающий 23 умножения, вместо 27. Два любопытных факта:
1. Не доказано, является ли он оптимальным, сейчас нижняя граница это 19 (link).
2. Поиск алгоритма сводится к декомпозиции 3D тензора
Tᵢⱼₖ = Σ uᵢvⱼwₖ (NP hard),
что аналогично решению системы дискретных уравнений на 621 неизвестную.
И через случайные блуждания по флип графу система решается за секунду, прямо на телефоне! Можете попробовать сами с моей визуализацией: https://qdiag.xyz/cpd/
(canonical polyadic decomposition онлайн, без регистрации)
Выше писал, что умножать матрицы 2х2 можно не за 8 умножений, а за 7. И аналогично для 3х3 есть алгоритм Ладермана, делающий 23 умножения, вместо 27. Два любопытных факта:
1. Не доказано, является ли он оптимальным, сейчас нижняя граница это 19 (link).
2. Поиск алгоритма сводится к декомпозиции 3D тензора
Tᵢⱼₖ = Σ uᵢvⱼwₖ (NP hard),
что аналогично решению системы дискретных уравнений на 621 неизвестную.
И через случайные блуждания по флип графу система решается за секунду, прямо на телефоне! Можете попробовать сами с моей визуализацией: https://qdiag.xyz/cpd/
🔥13👍6❤4