Алгоритм (сжатия) Любачевского — Стилинжера

Алгоритм (сжатия) Любачевского — Стилинжера (Lubachevsky-Stillinger compression algorithm, ЛС алгоритм, ЛСА, ЛС протокол), вычислительная процедура, которая имитирует процесс механического сжатия набора твёрдых частиц.

Механическое сжимание обычно осуществляется стенкой сосуда, где находятся частицы, например, давящим на частицы поршнем. ЛСА способен моделировать такой процесс.  Однако, в первоначальной формулировке ЛСА не было твёрдых стенок сосуда, а частицы как бы «распухали», расширяясь в размере, но находясь в фиксированном и конечном виртуальном объёме с периодическими граничными условиями (periodic boundary conditions).  В то время, как абсолютные размеры частиц увеличивались, их размеры в отношении друг к другу оставались неизменными. В общем случае, ЛСА может справиться и с внешним сжатием, и с внутренним расширением частиц, происходящими одновременно, и возможно, но не обязательно, сочетающимися с присутствующими твёрдыми стенками сосуда. К тому же эти стенки могут быть подвижными (mobile).

В результирующем сжатом массиве могут найтись частицы, которые «сжатыми» не будут, а, напротив, будут подвижны в пределах, ограниченных их сжатыми частицами-соседями и, возможно, твёрдыми стенками сосуда. Появление свободных частиц не является ни артефактом, ни заранее заданным явлением, которое ЛСА должен был бы продемонстрировать. Они действительно возникают в сжатом массиве твёрдых частиц, оказавшись даже некоторой неожиданностью для создателей ЛСА. Фрэнк Хенри Стилинжер (Frank Henry Stillinger) предложил название «ратлер» (rattler-погремушка) для подобной частицы, поскольку если потрясти сжатый массив твёрдых частиц, ратлеры будут «громыхать».

В начальной фазе «сжимания», когда плотность заполнения частицами доступного объёма низка и когда все частицы подвижны (mobile), процессы внешнего сжатия и внутреннего расширения частиц могут быть остановлены. Продолжающий работать после такой остановки, ЛСА будет моделировать текущий поток, состоящий из частиц (granular flow). Промоделированы могут быть различные механизмы твёрдых столкновений, как то: идеально упругие или с только-частичным восстановлением, идеально скользящие и с трением. Разные массы частиц могут быть приняты во внимание при моделировании столкновений. Также возможно и порой оказывается полезным «разжижать» сжатую конфигурацию частиц, посредством уменьшения размера всех или некоторых частиц.

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

Использование ЛСА для сферических частиц разных размеров и/или в контейнерах с «неудобными» размерами оказалось эффективным методом для получения и демонстрации микроструктурных нарушений связанных с атомарной неоднородностью (crystal impurity) и с «усталостью» материала (frustration). Можно добавить, что первоначальный протокол ЛС предназначался, главным образом, для сфер одного или разных диаметров. Малейшее отклонение от формы сферы (или круга на плоскости), даже такое, как использование эллипсоидов (или, если на плоскости, то эллипсов) существенно замедляет вычисления. Но если форма всех частиц сферическая, ЛСА справляется с наборами в десятки и сотни тысяч частиц на стандартных сегодняшних (2011) персональных компьютерах. Только очень небольшой опыт имеется в использовании ЛСА в размерностях выше трёх. 

Состояние сжатия достигается моделированием текущего потока частиц (granular flow). Поток же, в свою очередь, представляется как последовательность дискретных событий (discrete events), где событиями оказываются соударения частиц, а также столкновения частиц с твердыми стенками, если таковые присутствуют. Идеально, если бы вычисления производились с бесконечной точностью, достижение состояния сжатия требовало бы бесконечного числа вычислительных шагов. Реально вычисления производятся с конечной точностью, и также конечна разрешающая способность представления действительных чисел в памяти вычислителя, например, двойная точность (double precision). Реальные вычисления останавливаются когда пробег всех частиц между столкновениями (исключая пробег ратлеров) становится меньше, чем некоторый малый порог, устанавливаемый явно или, чаще, неявно. Например, нет пользы продолжать вычисления, если пробег стал меньше ошибки округления.

ЛСА вычислительно эффективен (efficient) в том смысле, что события просматриваются (processed), главным образом, на базе запланированных прежде событий (event driven fashion), а не на базе продвижения во времени (time driven fashion). Это означает, в частности, что вычисления почти не тратятся на просмотр и поддержание в порядке позиций и скоростей частиц между столкновениями. Среди подобных алгоритмов, просмотр событий в которых также основывается на запланированных прежде событиях (event driven) и которые также предназначены для моделирования текущего потока частиц (granular flow), как, например, алгоритм Д. Рапапорта (D. C. Rapaport),  ЛСА выделяется особой простотой структуры данных и способа поддержки этой структуры (data structure and data handling).

Для любой частицы и на любой стадии вычислений ЛСА поддерживает запись только о двух событиях (keeps record of only two events): о старом, уже просчитанном и совершившемся событии (committed event), и о новом, только ещё намеченном к исполнению событии. Новое событие может и не совершиться по намеченному (non-committed event). Запись о событии состоит из: временной отметки события (event time stamp), из записи состояния частицы сразу после события (включая положение и скорость частицы), а также из идентификации «партнёра» частицы по данному событию, если таковой оказывается. Партнёром может быть другая частица, либо стенка сосуда. Максимум отметок времени совершившихся событий не может превзойти минимума отметок времени событий намеченных к исполнению.

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

По мере прогресса вычислений, частоты столкновений частиц в моделируемом времени могут возрастать и обычно возрастают в действительности. Тем не менее, система успешно приближается к итоговому сжатому состоянию, если только частоты столкновений разных частиц оказываются соизмеримыми между собой. (Исключая ратлеров. Последние испытывают устойчиво низкие частоты столкновений, и это свойство ратлеров позволяет их легко выявить). Однако возможно, что некоторое небольшое число частиц, даже одна единственная частица, будет испытывать чрезмерно высокую и всё возрастающую по сравнению с остальными частицами частоту столкновений при приближении моделируемого времени к некоторой временной отметке. Если такое случается, процесс моделирования застревает на данной временной отметке, не будучи в состоянии достичь желаемого сжатия частиц.

Подобное застревание в моделируемом времени может произойти и в режиме простого моделирования потока частиц (granular flow) без сжатия или расширения частиц. Такой отказ в работе алгоритма известен среди тех, кто занимается моделированием текущего потока частиц (among practitioners of granular flow simulations), под названием «неупругий коллапс» («inelastic collapse»), поскольку его типичная причина в неидеальной упругости столкновений.  Этот вид отказа не специфичен только для ЛСА. Предложены методы избежать неупругого коллапса.

ЛСА появился как побочный продукт попытки уточнить оценку ускорения параллельного моделирования по сравнению с последовательным моделированием. Было предложено использовать параллельный алгоритм Давида Джеферсона (David Jefferson) под названием Свёрнутое Время (Time Warp, Тайм Ворп), чтобы моделировать на параллельной вычислительной машине асинхронные взаимодействия противоборствующих участников (fighting units) в пространстве, возникающие в моделях военных сражений (combat models). Модели со сталкивающимися твердыми частицами  были подобны моделям сражений в том, что в них также присутствовали асинхронные взаимодействия в пространстве, но обладали преимуществом отсутствия многих деталей, несущественных для экспозиции работы алгоритма моделирования.

Параллельным ускорением считалось отношение времени счёта при использовании только одного процессора параллельной машины ко времени счёта при использовании всех процессоров, с условием применения одного и того же алгоритма Свёрнутое Время в обоих случаях. Борис Дмитриевич Любачевский (Boris Dmitrievich Lubachevsky) замечал, что такая оценка параллельного ускорения может быть завышенной, поскольку выполнение задачи на одном процессоре с помощью параллельной программы это не обязательно самый быстрый метод вычислений, которые можно организовать на этом процессоре для решения этой задачи. ЛСА был создан как попытка найти более быстрый однопроцессорный метод моделирования и тем самым улучшить качество оценки параллельного ускорения. Впоследствии и параллельный алгоритм моделирования, отличный от алгоритма Свёрнутое Время, был предложен, который сводится к ЛСА, если его выполнять на одном процессоре.