Обнаружено девятое число Дедекинда - давно известная проблема в математике

То, что начиналось как магистерский дипломный проект Леннарта Ван Хиртума, в то время студента факультета компьютерных наук в Лёвенском католическом университете, а теперь научного сотрудника Университета Падерборна, стало огромным успехом. Ученые присоединяются к прославленной группе со своей работой. Более ранние числа в серии были найдены самим математиком Ричардом Дедекиндом, когда он определил проблему в 1897 году, а затем великими ранними компьютерными науками, такими как Рэндольф Черч и Морган Уорд. «В течение 32 лет вычисление D (9) было открытым вызовом, и было сомнительно, удастся ли вообще когда-либо вычислить это число», — говорит Ван Хиртум.

Предыдущее число в последовательности Дедекинда, 8-е число Дедекинда, было найдено в 1991 году с помощью Cray 2, самого мощного суперкомпьютера в то время. «Поэтому нам казалось возможным, что к настоящему времени можно будет вычислить 9-е число на большом суперкомпьютере», — говорит Ван Хиртум, описывая мотивацию амбициозного проекта, который он первоначально реализовал совместно с руководителями своей магистерской диссертации в Лёвенском католическом университете.

Unsplash / CC0 Общественное достояние

Рис, шахматы и суперкомпьютеры

Основной темой чисел Дедекинда являются так называемые монотонные булевы функции. Ван Хиртум объясняет: «В принципе, вы можете думать о монотонной булевой функции в двух, трех и бесконечных измерениях как об игре с n-мерным кубом. Вы балансируете куб на одном углу, а затем раскрашиваете каждый из оставшихся углов в белый или красный цвет. Есть только одно правило: никогда нельзя ставить белый угол над красным. Это создает своеобразное вертикальное красно-белое пересечение.

«Цель игры состоит в том, чтобы подсчитать, сколько существует различных разрезов. Их число определяется как число Дедекинда. Даже если кажется, что это не так, цифры быстро становятся гигантскими в процессе: 8-е число Дедекинда уже имеет 23 цифры.

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

«Количество рисовых зерен на всей доске будет иметь 20 цифр — невообразимое количество, но все же меньше, чем D (8). Когда вы осознаете эти порядки, становится очевидным, что для нахождения D (9) потребуются как эффективный вычислительный метод, так и очень быстрый компьютер», — сказал Ван Хиртум.

Веха: годы превращаются в месяцы

Для расчета D (9) ученые использовали методику, разработанную научным руководителем магистерской диссертации Патриком Де Космакером, известную как формула P-коэффициента. Он дает возможность вычислять числа Дедекинда не по счету, а по очень большой сумме. Это позволяет декодировать D(8) всего за восемь минут на обычном ноутбуке. Но «то, что занимает восемь минут для D(8), становится сотнями тысяч лет для D(9). Даже если бы вы использовали большой суперкомпьютер исключительно для этой задачи, все равно потребовалось бы много лет, чтобы завершить расчет», — отмечает Ван Хиртум.

Основная проблема заключается в том, что количество слагаемых в этой формуле растет невероятно быстро. «В нашем случае, используя симметрии в формуле, мы смогли уменьшить количество членов до «всего» 5,5x10^18— огромная сумма. Для сравнения, количество песчинок на Земле составляет около 7,5х10^18”

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

Решение: специализированное оборудование, использующее узкоспециализированные и параллельные арифметические блоки — так называемые FPGA (программируемые вентильные матрицы). Ван Хиртум разработал первоначальный прототип аппаратного ускорителя и начал искать суперкомпьютер с необходимыми картами FPGA. В процессе он узнал о компьютере Noctua 2 в «Падерборнском центре параллельных вычислений (PC2)» в Университете Падерборна, который имеет одну из самых мощных в мире систем FPGA.

Решение сложных комбинаторных задач с помощью FPGA является перспективной областью применения, и Noctua 2 является одним из немногих суперкомпьютеров в мире, с которыми эксперимент вообще возможен. Чрезвычайные требования к надежности и стабильности также представляют собой вызов и испытание для нашей инфраструктуры. Экспертно-консультационная группа FPGA тесно сотрудничала с Lennart, чтобы адаптировать и оптимизировать приложение для нашей среды».

После нескольких лет разработки программа работала на суперкомпьютере около пяти месяцев. И вот пришло время: 8 марта ученые нашли 9-е число Дедекинда: 286386577668298411128469151667598498812366.

Сегодня, спустя три года после начала проекта «Дедекинд», Ван Хиртум работает научным сотрудником Высшей школы NHR в Центре параллельных вычислений Падерборна над разработкой аппаратных инструментов следующего поколения в своей докторской диссертации.

Предоставлено Университет Падерборна