Ученые из США и Великобритании заявили о крупнейшем по объему занятой компьютерной памяти доказательстве в истории математики. Препринт с исследованием опубликован на сайте arXiv.org, кратко о нем сообщает издание Nature.
Для решения булевой проблемы пифагоровых троек специалисты использовали суперкомпьютер Stampede Техасского университета в Остине (США). Его расчеты заняли 200 терабайт памяти, что равно всей оцифрованной крупнейшей библиотеке мира (Библиотека Конгресса).
В использованном учеными подходе проблема является переформулированной теоремой Шура для площадей, доказательство которой предполагает два предписания. Первое из них включает нахождение ответа на вопрос, может ли множество натуральных чисел (1, 2, 3 и так далее) быть разделено на две части таким образом, чтобы ни одна из них не содержала бы пифагоровых троек (то есть чисел a, b и c таких, что a2 + b2 = c2). Второе предписание говорит о необходимости разделения чисел при помощи булевых переменных.
Полученное учеными решение булевой проблемы пифагоровых троек заключается в следующем: натуральные числа из замкнутого интервала [1;7824] можно разбить на две части так, что они не содержат пифагоровой тройки. Для натуральных чисел из замкнутого интервала [1;7825] это невозможно.
Ученым удалось при помощи идей симметрии и методов теории чисел оптимизировать использованный для решения проблемы алгоритм. Это позволило снизить количество возможностей, перебираемых Stampede с более чем 102300 способов до менее 1012. Суперкомпьютер с 800 ядрами работал в течение двух суток.
Математическая задача была решена путем прямого перебора имеющихся возможностей. Кроме полного решения, ученые представили его краткий вариант, который занял 68 гигабайт памяти. Для его проверки обычному компьютеру потребовалось бы около 30 тысяч часов непрерывной работы. При этом человек, скорее всего, в полной мере самостоятельно не смог бы воспроизвести использованный Stampede алгоритм. Доказательное вычисление было проверено на двух алгоритмах, позволяющих решить проблему.
https://lenta.ru/news/2016/05/27/triple/
The TACC Stampede* system is a 10 PFLOPS (PF) Dell Linux Cluster based on 6400+ Dell PowerEdge server nodes, each outfitted with 2 Intel Xeon E5 (Sandy Bridge) processors and an Intel Xeon Phi Coprocessor (MIC Architecture). The aggregate peak performance of the Xeon E5 processors is 2+PF, while the Xeon Phi processors deliver an additional aggregate peak performance of 7+PF. The system also includes a set of login nodes, large-memory nodes, graphics nodes (for both remote visualization and computation), and dual-coprocessor nodes. Additional nodes (not directly accessible to users) provide management and file system services. A Compute node consists of a Dell C8220z double-wide sled in a 4 rack-unit chassis with 3 other sleds. Each node runs CentOS 6.3 with the 2.6.32 x86_64 Linux kernel. Each node contains two Xeon Intel 8-Core 64-bit E5-processors (16 cores in all) on a single board, as an SMP unit. The core frequency is 2.7GHz and supports 8 floating-point operations per clock period with a peak performance of 21.6 GFLOPS/core or 346 GFLOPS/node. Each node contains 32GB of memory (2GB/core). The memory subsystem has 4 channels from each processor's memory controller to 4 DDR3 ECC DIMMS, each rated at 1600 MT/s (51.2GB/s for all four channels in a socket). The processor interconnect, QPI, runs at 8.0 GT/s between sockets. The Intel Xeon Phi is a special production model with 61 1.1 GHz cores with a peak performance of 16.2 DP GFLOPS/core or 1.0 DP TFLOPS/Phi. Each coprocessor contains 8GB of GDDR5 memory, with 8 dual-channel controllers, with a peak memory performance of 320GB/s.
