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

Описание

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

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

В результирующем состоянии, некоторые частицы могут сохранить подвижность в пределах, ограниченных их соседями и стенками сосуда. Появление таких частиц стало неожиданным для авторов алгоритма — предложил название «ратлер» (погремушка) для подобной частицы, так как ратлеры будут «громыхать» если потрясти сжатый массив твёрдых частиц.

Внешнее сжатие и внутреннее расширение частиц можно остановить в предсжатом состоянии, когда плотность заполнения частицами низка и частицы подвижны. Работающий в таком режиме LSA будет моделировать поток частиц как сыпучей среды . LSA также может моделировать различные механизмы столкновений частиц или учитывать их массу.

Использование LSA для сферических частиц или в контейнерах с «неудобными» размерами оказалось эффективным для воспроизведения и демонстрации микроструктурных нарушений связанных с дефектами кристалла или геометрической фрустрацией . Изначально, LSA предназначался для решения задачи упаковки шаров . LSA может справиться с наборами в десятки и сотни тысяч шаров на персональных компьютерах, однако отклонение от сферической формы (или круглой на плоскости), такое как использование эллипсоидов (эллипсов на плоскости), существенно замедляет вычисления .

Алгоритм

Для сжатия используется дискретно-событийное моделирование сыпучей среды, где событиями оказываются соударения частиц между собой и с твердыми стенками, если таковые присутствуют. Вычисления останавливаются, когда перемещения между столкновениями всех частиц, кроме ратлеров, становится меньше, чем явно или неявно заданный малый порог, который может определяться, например, ошибками округления.

LSA вычислительно эффективен, в том смысле, что его прогресс определяется событиями (столкновениями), а не прошедшими между ними промежутками времени. В связи с этим, промежуточные характеристики частиц в период между солкновениями, как правило, не вычисляются. По сравнению с другими алгоритмами со схожей моделью вычислений, такими как алгоритм Д. Рапапорта , LSA выделяется простотой в структурировании и обработке данных.

Для любой частицы и на любой стадии вычислений, LSA поддерживает запись только о двух событиях: о старом, уже обработанном событии, и о новом, намеченном к обработке. Запись о событии состоит из временной метки события, состояния частицы сразу после события (включая положение и скорость частицы), а также указания на «партнёра» частицы по данному событию (другая частица, либо стенка сосуда), если таковой имеется. Максимум меток среди обработанных событий не должен превышать минимума меток необработанных событий.

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

По мере вычислений, частоты столкновений частиц, как правило, возрастают. Однако, система успешно приближается к сжатому состоянию, если частоты столкновений разных частиц, не являющихся ратлерами, оказываются соизмеримыми. Ратлеры, в свою очередь, сохраняют устойчиво низкие частоты столкновений, что позволяет их выявить.

В то же время, возможно, что частоты столкновений небольшого числа частиц, или даже одной частицы, будут значительно превышать частоту столкновений остальных частиц, что, в свою очередь, может существенно замедлить алгоритм. Такое состояние в моделировании сыпучих сред принято называть «неупругий коллапс» (« inelastic collapse »), поскольку его типичной причиной является низкий моделируемых частиц . Такая ситуация не уникальна для LSA, был разработан ряд методов её решения .

История

LSA появился как побочный продукт попытки установить адекватную меру параллельного моделирования. Изначально, было предложено использовать параллельный алгоритм Time Warp — ускорение определялось как отношение времени исполнения на многопроцессорной и однопроцессорной системах. Борис Дмитриевич Любачевский обратил внимание, что такая оценка может быть завышенной, так как выполнение задачи на одном процессоре с помощью параллельной программы может быть неоптимальным для решения поставленной задачи. LSA был создан как попытка найти более быстрый однопроцессорный метод моделирования и тем самым улучшить качество оценки параллельного ускорения. Впоследствии был также предложен параллельный алгоритм моделирования, который, при исполнении на однопроцессорной системе, идентичен LSA .

Примечания

Ссылки