Алгоритм «сжатия» Любачевского–Стилинжера (Lubachevsky-Stillinger compression algorithm, ЛСА, ЛС протокол) – вычислительная процедура, которая имитирует процесс механического сжатия набора твердых частиц [1].
Механическое сжимание обычно осуществляется стенкой сосуда, где находятся частицы, например, давящим на частицы поршнем. ЛСА способен моделировать такой процесс. Однако в первоначальной формулировке ЛСА не было твердых стенок сосуда, а частицы как бы «распухали», расширяясь в размере, но находясь в фиксированном и конечном виртуальном объеме с периодическими граничными условиями (рисунок 1). В то время как абсолютные размеры частиц увеличивались, их размеры в отношении друг к другу оставались неизменными. В общем случае, ЛСА может справиться и с внешним сжатием, и с внутренним расширением частиц, происходящими одновременно, и возможно, но не обязательно, сочетающимися с присутствующими твердыми стенками сосуда. К тому же эти стенки могут быть подвижными.
Рисунок 1 – Модель плотной упаковки сфер, построенная расширением размеров частиц в ограниченном объеме: до начала расширения (а), в окончательной стадии формирования модели (б)
В результирующем сжатом массиве могут найтись частицы так называемые «висячие частицы», которые «сжатыми» не будут, а, напротив, будут подвижны в пределах, ограниченных их сжатыми частицами-соседями и, возможно, твердыми стенками сосуда. Появление свободных частиц не является ни артефактом, ни заранее заданным явлением, которое ЛСА должен был бы продемонстрировать. Они действительно возникают в сжатом массиве твердых частиц, оказавшись даже некоторой неожиданностью для создателей ЛСА. Фрэнк Хенри Стилинжер предложил название «ратлер» (rattler – «погремушка») для подобной частицы, поскольку если потрясти сжатый массив твердых частиц, ратлеры будут «громыхать».
В начальной фазе «сжимания», когда плотность заполнения частицами доступного объема низка и когда все частицы подвижны, процессы внешнего сжатия и внутреннего расширения частиц могут быть остановлены. Продолжающий работать после такой остановки, ЛСА будет моделировать текущий поток, состоящий из частиц (granular flow). Промоделированы могут быть различные механизмы твердых столкновений, как то: идеально упругие или с только-частичным восстановлением, идеально скользящие и с трением. Разные массы частиц могут быть приняты во внимание при моделировании столкновений. Также порой оказывается полезным «разжижать» сжатую конфигурацию частиц, посредством уменьшения размера всех или некоторых частиц.
Первоначальный протокол ЛС предназначался, главным образом, для сфер одного или разных диаметров. Малейшее отклонение от формы сферы (или круга на плоскости), даже такое, как использование эллипсоидов (или, если на плоскости, то эллипсов) существенно замедляет вычисления. Но если форма всех частиц сферическая, ЛСА справляется с наборами в десятки и сотни тысяч частиц на стандартных сегодняшних персональных компьютерах.
Состояние сжатия достигается моделированием текущего потока частиц. Поток же, в свою очередь, представляется как последовательность дискретных событий, где событиями оказываются соударения частиц, а также столкновения частиц с твердыми стенками, если таковые присутствуют. Вычисления останавливаются, когда пробег всех частиц между столкновениями (исключая пробег ратлеров) становится меньше, чем некоторый малый порог, устанавливаемый явно или, чаще, неявно. Например, нет пользы продолжать вычисления, если пробег стал меньше ошибки округления.
Для любой частицы и на любой стадии вычислений ЛСА поддерживает запись только о двух событиях: о старом, уже просчитанном и совершившемся событии, и о новом, только еще намеченном к исполнению событии. Новое событие может и не совершиться по намеченному. Запись о событии состоит из: временной отметки события, из записи состояния частицы сразу после события (включая положение и скорость частицы), а также из идентификации «партнера» частицы по данному событию, если таковой оказывается. Партнером может быть другая частица, либо стенка сосуда. Максимум отметок времени совершившихся событий не может превзойти минимума отметок времени событий намеченных к исполнению.
Следующей частицей для просмотра выбирается частица с минимумом отметки времени среди событий намеченных к исполнению. При этом просмотре то, что прежде было новым событием, намеченным к исполнению для данной частицы, объявляется старым совершенным событием, и в то же время намечается следующее новое событие с его новой отметкой времени, новым состоянием и с новым партнером, если таковой окажется. При таком установлении следующего нового события для частицы некоторые соседние частицы могут пересчитать свои намеченные к исполнению события, принимая во внимание возникшую новую информацию.
По мере прогресса вычислений, частоты столкновений частиц в моделируемом времени могут возрастать и обычно возрастают в действительности. Тем не менее, система успешно приближается к итоговому сжатому состоянию, если только частоты столкновений разных частиц оказываются соизмеримыми между собой. (Исключая ратлеров. Последние испытывают устойчиво низкие частоты столкновений, и это свойство ратлеров позволяет их легко выявить). Однако возможно, что некоторое небольшое число частиц, даже одна единственная частица, будет испытывать чрезмерно высокую и все возрастающую по сравнению с остальными частицами частоту столкновений при приближении моделируемого времени к некоторой временной отметке. Если такое случается, процесс моделирования застревает на данной временной отметке, не будучи в состоянии достичь желаемого сжатия частиц [1, 2].
Библиографические ссылки:
[1] – Алгоритм Любачевского–Стилинжера [Электронный ресурс]: Материал из Википедии – свободной энциклопедии: Версия 53287476, сохраненная в 23:27 UTC 12 марта 2013 / Авторы Википедии // Википедия, свободная энциклопедия. – Электрон. дан. – Сан-Франциско: Фонд Викимедиа, 2013.
[2] – Аникеенко, А.В. Структурный анализ монодисперсных упаковок твердых сфер при разной плотности / А.В. Аникеенко, Н.Н. Медведев // Структура и динамика молекулярных систем, 2007 г., Выпуск №1. С.700-705.