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

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

Одна тысяча конгруэнтных равнобедренных треугольников хаотически упакованы в прямоугольнике с периодическими граничными условиями. Плотность упаковки (покрытие площади частицами) составляет 0,8776. Внутренний прямоугольник показывает период образованной структуры.

Описание

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

История

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

Примечания
  1. F. H. Stillinger and B. D. Lubachevsky, Crystalline-Amorphous Interface Packings for Disks and Spheres, J. Stat. Phys. 73, 497—514 (1993)
  2. B. D. Lubachevsky and F. H. Stillinger, Geometric properties of random disk packings, J. Statistical Physics 60 (1990), 561—583
  3. B. D. Lubachevsky, How to Simulate Billiards and Similar Systems, Journal of Computational Physics Volume 94 Issue 2, May 1991
  4. F. H. Stillinger and B. D. Lubachevsky. Patterns of Broken Symmetry in the Impurity-Perturbed Rigid Disk Crystal, J. Stat. Phys. 78, 1011—1026 (1995)
  5. Boris D. Lubachevsky and Frank H. Stillinger, Epitaxial frustration in deposited packings of rigid disks and spheres. Physical Review E 70:44, 41604 (2004).
  6. Boris D. Lubachevsky, Ron L. Graham, and Frank H. Stillinger, Spontaneous Patterns in Disk Packings. Visual Mathematics, 1995.
  7. A. R. Kansal, S. Torquato, and F. H. Stillinger, Computer Generation of Dense Polydisperse Sphere Packings, J. Chem. Phys. 117, 8212-8218 (2002)
  8. A. Donev, F. H. Stillinger, P. M. Chaikin, and S. Torquato, Unusually Dense Crystal Packings of Ellipsoids, Phys. Rev. Letters 92, 255506 (2004)
  9. D. C. Rapaport, The Event Scheduling Problem in Molecular Dynamic Simulation, Journal of Computational Physics Volume 34 Issue 2, 1980
  10. S. McNamara, and W. R. Young, Inelastic collapse in two dimensions, Physical Review E 50: pp. R28-R31, 1994
  11. John J. Drozd, Computer Simulation of Granular Matter: A Study of An Industrial Grinding Mill Архивировано 18 августа 2011 года., Thesis, Univ. Western Ontario, Canada, 2004.
  12. F. Wieland, and D. Jefferson, Case studies in serial and parallel simulations, Proc. 1989 Int’l Conf. Parallel Processing, Vol.III, F. Ris, and M. Kogge, Eds., pp. 255—258.
  13. B. D. Lubachevsky, Simulating Billiards: Serially and in Parallel, Int.J. in Computer Simulation, Vol. 2 (1992), pp. 373—411.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.