Алгоритм Любачевского – Стиллинджера - Lubachevsky–Stillinger algorithm

Алгоритм Любачевского-Стиллинджера (сжатие) (Алгоритм LS, LSA или протокол LS) - это числовая процедура, предложенная Ф. Х. Стиллинджер и Б.Д. Любачевского, который моделирует или имитирует физический процесс сжатия совокупности твердых частиц.[1] Поскольку для LSA могут потребоваться тысячи арифметических операций даже для нескольких частиц, обычно он выполняется на компьютере.

Используя вариант алгоритма Любачевского-Стиллинджера, 1000 конгруэнтных равнобедренных треугольников случайным образом упаковываются сжатием в прямоугольник с периодической (циклической) границей. Показан прямоугольник, обозначающий период повторения рисунка в обоих направлениях. Плотность упаковки 0,8776

Феноменология

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

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

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

Использование LSA для сферических частиц разного размера и / или для заклинивания в контейнере неизмеримого размера оказалось полезным методом для создания и изучения микроструктур, образующихся в условиях кристаллографический дефект[4] или геометрическое разочарование[5][6] Следует добавить, что исходный протокол LS был разработан в первую очередь для сфер одинакового или разных размеров.[7]

Любое отклонение от сферической (или круглой в двух измерениях) формы, даже самого простого, когда сферы заменяются эллипсоидами (или эллипсами в двух измерениях),[8] вызывает существенное замедление модифицированного таким образом LSA, но пока форма имеет сферическую форму, LSA может обрабатывать сборки частиц размером от десятков до сотен тысяч по сегодняшнему стандарту (2011 г.) персональные компьютеры. Сообщалось только об очень ограниченном опыте[9]при использовании LSA в габаритах выше 3.

Выполнение

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

LSA эффективен в том смысле, что события обрабатываются в основном в событийный мода, а не управляемая временем мода. Это означает, что на вычисление или поддержание положений и скоростей частиц между столкновениями почти не тратится впустую. Среди событийный алгоритмы, предназначенные для той же задачи моделирования гранулированный поток, как, например, алгоритм D.C. Rapaport,[10] LSA отличается более простой структура данных и обработка данных.

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

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

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

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

История

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

Рекомендации

  1. ^ а б Любачевский, Борис Д .; Стиллинджер, Фрэнк Х. (1990). «Геометрические свойства случайных дисковых упаковок» (PDF). Журнал статистической физики. 60 (5–6): 561–583. Bibcode:1990JSP .... 60..561L. Дои:10.1007 / bf01025983.
  2. ^ Стиллинджер, Фрэнк Х .; Любачевский, Борис Д. (1993). «Кристаллические аморфные переходные насадки для дисков и сфер». Журнал статистической физики. 73 (3–4): 497–514. Дои:10.1007 / bf01054337.
  3. ^ Любачевский, Борис Д. (1991). «Как моделировать бильярд и подобные системы». Журнал вычислительной физики. 94 (2): 255–283. arXiv:cond-mat / 0503627. Bibcode:1991JCoPh..94..255L. Дои:10.1016/0021-9991(91)90222-7.
  4. ^ Стиллинджер, Фрэнк Х .; Любачевский, Борис Д. (1995). «Паттерны нарушенной симметрии в кристалле жесткого диска, возмущенного примесью». Журнал статистической физики. 78 (3–4): 1011–1026. Bibcode:1995JSP .... 78.1011S. Дои:10.1007 / bf02183698.
  5. ^ Любачевский, Борис Д .; Стиллинджер, Фрэнк Х. (2004). «Эпитаксиальные расстройства в наплавленных упаковках жестких дисков и сфер». Физический обзор E. 70 (4): 041604. arXiv:cond-mat / 0405650. Bibcode:2004PhRvE..70d1604L. Дои:10.1103 / Physreve.70.041604. PMID  15600418.
  6. ^ Любачевский, Борис Д .; Грэм, Рон Л .; Стиллинджер, Фрэнк Х. (1995). «Самопроизвольные паттерны в дисковых упаковках». Визуальная математика.
  7. ^ Kansal, Anuraag R .; Торквато, Сальваторе; Стиллинджер, Фрэнк Х. (2002). «Компьютерное создание плотных полидисперсных сферических упаковок». Журнал химической физики. 117 (18): 8212–8218. Bibcode:2002ЖЧФ.117.8212К. Дои:10.1063/1.1511510.
  8. ^ Донев, Александар; Стиллинджер, Фрэнк Х .; Чайкин, П. М .; Торквато, Сальваторе (2004). «Необычно плотные кристаллические упаковки эллипсоидов». Письма с физическими проверками. 92 (25): 255506. arXiv:cond-mat / 0403286. Bibcode:2004ПхРвЛ..92у5506Д. Дои:10.1103 / Physrevlett.92.255506. PMID  15245027.
  9. ^ Скоге, Моника; Донев, Александр; Стиллинджер, Фрэнк Х .; Торквато, Сальваторе (2006). «Упаковка гиперсфер в многомерных евклидовых пространствах». Физический обзор E. 74 (4): 041127. arXiv:cond-mat / 0608362. Bibcode:2006PhRvE..74d1127S. Дои:10.1103 / Physreve.74.041127. PMID  17155042.
  10. ^ Рапапорт, округ Колумбия (1980). «Проблема планирования событий в молекулярно-динамическом моделировании». Журнал вычислительной физики. 34 (2): 184–201. Bibcode:1980JCoPh..34..184R. Дои:10.1016/0021-9991(80)90104-7.
  11. ^ Макнамара, Шон; Янг, В. Р. (1994). «Неупругий коллапс в двух измерениях». Физический обзор E. 50 (1): R28 – R31. Bibcode:1994ФРвЭ..50 ... 28М. Дои:10.1103 / Physreve.50.r28. PMID  9962022.
  12. ^ Дрозд, Джон Дж. (2004). Компьютерное моделирование гранулированного материала: исследование промышленной мельницы (PDF) (Тезис). Канада: Univ. Западный Онтарио. Архивировано из оригинал (PDF) на 2011-08-18. Получено 2011-05-25.
  13. ^ Ф. Виланд и Д. Джефферсон, Примеры последовательного и параллельного моделирования, Proc. Международная конференция 1989 г. Parallel Processing, Vol.III, F. Ris, and M. Kogge, Eds., Pp. 255-258.
  14. ^ П. Хонталес, Б. Бекман и др., Проведение моделирования столкновения шайб в операционных системах Time Warp, Proc. 1989 SCS Multiconference, Серия моделирования, SCS, Vol. 21, No. 2, pp. 3-7.
  15. ^ Любачевский, Б. (1992). «Моделирование бильярда: последовательно и параллельно». Международный журнал компьютерного моделирования. 2: 373–411.

внешняя ссылка