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

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

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

Феноменология (что моделируется)

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

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

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

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

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

Воплощение (как осуществляются вычисления)

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

ЛСА вычислительно эффективен (efficient) в том смысле, что события просматриваются (processed), главным образом, на базе запланированных прежде событий (event driven fashion), а не на базе продвижения во времени (time driven fashion). Это означает, в частности, что вычисления почти не тратятся на просмотр и поддержание в порядке позиций и скоростей частиц между столкновениями. Среди подобных алгоритмов, просмотр событий в которых также основывается на запланированных прежде событиях (event driven) и которые также предназначены для моделирования текущего потока частиц (granular flow), как, например, алгоритм Д. Рапапорта (D. C. Rapaport),^[10], ЛСА выделяется особой простотой структуры данных и способа поддержки этой структуры (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»), поскольку его типичная причина в неидеальной упругости столкновений.^[11] Этот вид отказа не специфичен только для ЛСА. Предложены методы избежать неупругого коллапса.^[12]

История создания алгоритма

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

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

Примечания

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. ↑ M. Skoge, A. Donev, F. H. Stillinger, and S. Torquato, Packing Hyperspheres in High-Dimensional Euclidean Spaces, Phys. Rev. E 74, 041127 (2006)
10. ↑ D. C. Rapaport, The Event Scheduling Problem in Molecular Dynamic Simulation, Journal of Computational Physics Volume 34 Issue 2, 1980
11. ↑ S. McNamara, and W. R. Young, Inelastic collapse in two dimensions, Physical Review E 50: pp. R28-R31, 1994
12. ↑ John J. Drozd, Computer Simulation of Granular Matter: A Study of An Industrial Grinding Mill, Thesis, Univ. Western Ontario, Canada, 2004.
13. ↑ 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.
14. ↑ P. Hontales, B. Beckman, et al., Performnce of the colliding pucks simulation of the Time Warp operating systems, Proc. 1989 SCS Multiconference, Simulation Series, SCS, Vol. 21, No. 2, pp. 3-7.
15. ↑ B. D. Lubachevsky, Simulating Billiards: Serially and in Parallel, Int.J. in Computer Simulation, Vol. 2 (1992), pp. 373—411.

Ссылки

• ЛСА в действии. Собрание анимаций, сделанных Александром Доневым (Alexander Donev)
• Исходные C++ программы (source codes) версии ЛСА, предназначенной для работы в высших измерениях
• Распределение флюктуаций объёма (volume fluctuation distribution) в упаковках частиц, полученных с помощью ЛСА
• Обобщение ЛСА для частиц произвольной формы
• Использование ЛСА для генерации представительных объёмов микроструктурных нарушений (representative volumes of microscale failures) в упакованных сыпучих материалах (packed granular materials)

В этой статье установлены общие категории. Вы можете помочь проекту, уточнив их.