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

Алгоритм Любачевского-Стиллинджера (сжатия) (алгоритм 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 ]}

Ссылки

^ Перейти обратно: ^а ^б Любачевский Борис Дмитриевич; Стиллингер, Фрэнк Х. (1990). «Геометрические свойства случайных дисковых упаковок» (PDF) . Журнал статистической физики . 60 (5–6): 561–583. Бибкод : 1990JSP....60..561L . дои : 10.1007/bf01025983 . S2CID 15485746 .
^ Стиллинджер, Фрэнк Х.; Любачевский, Борис Дмитриевич (1993). «Кристаллически-аморфные интерфейсные упаковки для дисков и сфер». Журнал статистической физики . 73 (3–4): 497–514. дои : 10.1007/bf01054337 . S2CID 59429012 .
^ Любачевский, Борис Дмитриевич (1991). «Как моделировать бильярд и подобные системы». Журнал вычислительной физики . 94 (2): 255–283. arXiv : cond-mat/0503627 . Бибкод : 1991JCoPh..94..255L . дои : 10.1016/0021-9991(91)90222-7 . S2CID 6215418 .
^ Стиллинджер, Фрэнк Х.; Любачевский, Борис Дмитриевич (1995). «Закономерности нарушения симметрии в кристалле жесткого диска, возмущенном примесями». Журнал статистической физики . 78 (3–4): 1011–1026. Бибкод : 1995JSP....78.1011S . дои : 10.1007/bf02183698 . S2CID 55943037 .
^ Любачевский Борис Дмитриевич; Стиллингер, Фрэнк Х. (2004). «Эпитаксиальное расстройство в наплавленных упаковках жестких дисков и сфер». Физический обзор E . 70 (4): 041604. arXiv : cond-mat/0405650 . Бибкод : 2004PhRvE..70d1604L . дои : 10.1103/physreve.70.041604 . ПМИД 15600418 . S2CID 1309789 .
^ Любачевский Борис Дмитриевич; Грэм, Рон Л.; Стиллинджер, Фрэнк Х. (1995). «Спонтанные закономерности в упаковках дисков» . Визуальная математика .
^ Кансал, Анурааг Р.; Торквато, Сальваторе; Стиллингер, Фрэнк Х. (2002). «Компьютерная генерация плотных полидисперсных сферических упаковок». Журнал химической физики . 117 (18): 8212–8218. Бибкод : 2002JChPh.117.8212K . дои : 10.1063/1.1511510 .
^ Донев, Александр; Стиллинджер, Фрэнк Х.; Чайкин, ПМ; Торквато, Сальваторе (2004). «Необычайно плотные кристаллические упаковки эллипсоидов». Письма о физических отзывах . 92 (25): 255506. arXiv : cond-mat/0403286 . Бибкод : 2004PhRvL..92y5506D . дои : 10.1103/physrevlett.92.255506 . ПМИД 15245027 . S2CID 7982407 .
^ Скоге, Моника; Донев, Александр; Стиллинджер, Фрэнк Х.; Торквато, Сальваторе (2006). «Упаковка гиперсфер в многомерные евклидовы пространства». Физический обзор E . 74 (4): 041127. arXiv : cond-mat/0608362 . Бибкод : 2006PhRvE..74d1127S . дои : 10.1103/physreve.74.041127 . ПМИД 17155042 . S2CID 18639889 .
^ Рапапорт, округ Колумбия (1980). «Проблема планирования событий в молекулярно-динамическом моделировании». Журнал вычислительной физики . 34 (2): 184–201. Бибкод : 1980JCoPh..34..184R . дои : 10.1016/0021-9991(80)90104-7 .
^ Макнамара, Шон; Янг, WR (1994). «Неупругий коллапс в двух измерениях». Физический обзор E . 50 (1): Р28–Р31. Бибкод : 1994PhRvE..50...28M . doi : 10.1103/physreve.50.r28 . ПМИД 9962022 .
^ Дрозд, Джон Дж. (2004). Компьютерное моделирование сыпучего вещества: исследование промышленной мельницы (PDF) (Диссертация). Канада: Univ. Западный Онтарио. Архивировано из оригинала (PDF) 18 августа 2011 г. Проверено 25 мая 2011 г.
^ Ф. Виланд и Д. Джефферсон, Тематические исследования последовательного и параллельного моделирования, Proc. Международная конференция 1989 г. Параллельная обработка, том III, Ф. Рис и М. Когге, ред., стр. 255-258.
^ П. Хонталес, Б. Бекман и др., Производительность моделирования сталкивающихся шайб в операционных системах Time Warp, Proc. 1989 Мультиконференция SCS, Серия моделирования, SCS, Vol. 21, № 2, стр. 3-7.
^ Любачевский, Б.Д. (1992). «Имитация бильярда: последовательно и параллельно». Международный журнал компьютерного моделирования . 2 : 373–411.

Внешние ссылки

[StillingerLubachevskyJStat-1] Перейти обратно: ^а ^б Любачевский Борис Дмитриевич; Стиллингер, Фрэнк Х. (1990). «Геометрические свойства случайных дисковых упаковок» (PDF) . Журнал статистической физики . 60 (5–6): 561–583. Бибкод : 1990JSP....60..561L . дои : 10.1007/bf01025983 . S2CID 15485746 .

[2] Стиллинджер, Фрэнк Х.; Любачевский, Борис Дмитриевич (1993). «Кристаллически-аморфные интерфейсные упаковки для дисков и сфер». Журнал статистической физики . 73 (3–4): 497–514. дои : 10.1007/bf01054337 . S2CID 59429012 .

[3] Любачевский, Борис Дмитриевич (1991). «Как моделировать бильярд и подобные системы». Журнал вычислительной физики . 94 (2): 255–283. arXiv : cond-mat/0503627 . Бибкод : 1991JCoPh..94..255L . дои : 10.1016/0021-9991(91)90222-7 . S2CID 6215418 .

[4] Стиллинджер, Фрэнк Х.; Любачевский, Борис Дмитриевич (1995). «Закономерности нарушения симметрии в кристалле жесткого диска, возмущенном примесями». Журнал статистической физики . 78 (3–4): 1011–1026. Бибкод : 1995JSP....78.1011S . дои : 10.1007/bf02183698 . S2CID 55943037 .

[5] Любачевский Борис Дмитриевич; Стиллингер, Фрэнк Х. (2004). «Эпитаксиальное расстройство в наплавленных упаковках жестких дисков и сфер». Физический обзор E . 70 (4): 041604. arXiv : cond-mat/0405650 . Бибкод : 2004PhRvE..70d1604L . дои : 10.1103/physreve.70.041604 . ПМИД 15600418 . S2CID 1309789 .

[6] Любачевский Борис Дмитриевич; Грэм, Рон Л.; Стиллинджер, Фрэнк Х. (1995). «Спонтанные закономерности в упаковках дисков» . Визуальная математика .

[7] Кансал, Анурааг Р.; Торквато, Сальваторе; Стиллингер, Фрэнк Х. (2002). «Компьютерная генерация плотных полидисперсных сферических упаковок». Журнал химической физики . 117 (18): 8212–8218. Бибкод : 2002JChPh.117.8212K . дои : 10.1063/1.1511510 .

[8] Донев, Александр; Стиллинджер, Фрэнк Х.; Чайкин, ПМ; Торквато, Сальваторе (2004). «Необычайно плотные кристаллические упаковки эллипсоидов». Письма о физических отзывах . 92 (25): 255506. arXiv : cond-mat/0403286 . Бибкод : 2004PhRvL..92y5506D . дои : 10.1103/physrevlett.92.255506 . ПМИД 15245027 . S2CID 7982407 .

[9] Скоге, Моника; Донев, Александр; Стиллинджер, Фрэнк Х.; Торквато, Сальваторе (2006). «Упаковка гиперсфер в многомерные евклидовы пространства». Физический обзор E . 74 (4): 041127. arXiv : cond-mat/0608362 . Бибкод : 2006PhRvE..74d1127S . дои : 10.1103/physreve.74.041127 . ПМИД 17155042 . S2CID 18639889 .

[10] Рапапорт, округ Колумбия (1980). «Проблема планирования событий в молекулярно-динамическом моделировании». Журнал вычислительной физики . 34 (2): 184–201. Бибкод : 1980JCoPh..34..184R . дои : 10.1016/0021-9991(80)90104-7 .

[11] Макнамара, Шон; Янг, WR (1994). «Неупругий коллапс в двух измерениях». Физический обзор E . 50 (1): Р28–Р31. Бибкод : 1994PhRvE..50...28M . doi : 10.1103/physreve.50.r28 . ПМИД 9962022 .

[12] Дрозд, Джон Дж. (2004). Компьютерное моделирование сыпучего вещества: исследование промышленной мельницы (PDF) (Диссертация). Канада: Univ. Западный Онтарио. Архивировано из оригинала (PDF) 18 августа 2011 г. Проверено 25 мая 2011 г.

[13] Ф. Виланд и Д. Джефферсон, Тематические исследования последовательного и параллельного моделирования, Proc. Международная конференция 1989 г. Параллельная обработка, том III, Ф. Рис и М. Когге, ред., стр. 255-258.

[14] П. Хонталес, Б. Бекман и др., Производительность моделирования сталкивающихся шайб в операционных системах Time Warp, Proc. 1989 Мультиконференция SCS, Серия моделирования, SCS, Vol. 21, № 2, стр. 3-7.

[15] Любачевский, Б.Д. (1992). «Имитация бильярда: последовательно и параллельно». Международный журнал компьютерного моделирования . 2 : 373–411.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]