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