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

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

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

Феноменологія (що моделюється)

Механічне стискання зазвичай здійснюється стінкою посудини, яка містить частинки, наприклад, поршнем. ЛСА здатний моделювати такий процес[1]. Однак, у початковому формулюванні ЛСА не було твердих стінок посудини, а частинки ніби «розпухали», збільшуючись у розмірі, але перебуваючи у фіксованому і скінченному віртуальному об'ємі з періодичними крайовими умовами[2][3]. Тоді як абсолютні розміри частинок збільшувалися, співвідношення їхніх розмірів залишалося незмінним. У загальному випадку, ЛСА може впоратися і з зовнішнім стисненням, і з внутрішнім розширенням частинок, що відбуваються одночасно і, можливо, але не обов'язково, поєднуються з присутніми твердими стінками посудини. До того ж ці стінки можуть бути рухомими.

В остаточному стиснутому масиві можуть знайтися частинки, які «стиснутими» не будуть, а, навпаки, будуть рухливі в межах, наданих їхніми стиснутими частинками-сусідами і, можливо, твердими стінками посудини. Поява вільних частинок не є ні артефактом, ні наперед заданим явищем, яке ЛСА мав би продемонструвати. Вони дійсно виникають у стиснутому масиві твердих частинок, ставши навіть деякою несподіванкою для творців ЛСА. Френк Генрі Стілінжер запропонував для подібної частинки назву «ратлер» (rattler — брязкальце), оскільки якщо потрясти стиснутий масив твердих частинок, ратлери будуть «бряжчати».

У початковій фазі «стискання», коли щільність заповнення частинками доступного об'єму низька і коли всі частинки рухливі, процеси зовнішнього стиснення і внутрішнього розширення частинок можна зупинити. ЛСА, що продовжує працювати після такої зупинки, буде моделювати сипуче тіло. Можна змоделювати різні механізми твердих зіткнень, такі як: ідеально пружні чи з тільки частковим відновленням, ідеально ковзні і з тертям. Мри моделюванні зіткнень можна взяти до уваги різні маси частинок. Також можливо і деколи виявляється корисним «розріджувати» всю конфігурацію частинок, зменшуючи розміри всіх або деяких частинок.

Інше можливе застосування ЛСА — це заміна силового потенціалу твердого зіткнення частинок (такий потенціал дорівнює нулю поза частинкою і стає нескінченністю на поверхні і всередині частинки) кусково-сталим потенціалом. Таким чином модифікований ЛСА апроксимує моделювання взаємодії джерел близькодійного силового поля. Зовнішні силові поля, такі як гравітаційне, також можна ввести остільки, оскільки проліт частинки між зіткненнями можна змоделювати простим однокроковим обчисленням.

Використання ЛСА для сферичних частинок різних розмірів і/або в контейнерах з «незручними» розмірами виявилося ефективним методом для отримання і демонстрації мікроструктурних порушень пов'язаних з дефектами кристалів[4] і з геометричною фрустрацією[5][6]. Можна додати, що початковий протокол ЛС призначався, головним чином, для сфер одного або різних діаметрів[7]. Найменше відхилення від форми сфери (кола на площині), навіть таке, як використання еліпсоїдів (або, якщо на площині, то еліпсів)[8], суттєво уповільнює обчислення. Але якщо форма всіх частинок сферична, ЛСА справляється з наборами з десятків і сотень тисяч частинок на звичайних сучасних (2011) персональних комп'ютерах. Є тільки незначний досвід використання ЛСА в розмірностях вищих від трьох[9].

Втілення

Стан стиснутості досягається моделюванням сипучого тіла. Сипучість, у свою чергу, подається як послідовність дискретних подій, де подіями виявляються зіткнення між частинками, а також зіткнення частинок з твердими стінками, якщо такі є. Ідеально, якби обчислення проводилися з нескінченною точністю, досягнення стану стиснутості вимагало б нескінченного числа обчислювальних кроків. Реально обчислення проводяться зі скінченною точністю, і також скінченною є роздільність подання дійсних чисел у пам'яті комп'ютера, наприклад, за подвійної точності. Реальні обчислення зупиняються, коли пробіг усіх частинок між зіткненнями (виключно з пробігом ратлерів) стає меншим, ніж деякий малий поріг, встановлений явно, або, частіше, неявно. Наприклад, немає сенсу продовжувати обчислення, якщо пробіг став меншим від похибки округлення.

ЛСА обчислювально ефективний у тому сенсі, що події опрацьовуються переважно в подійно-орієнтованому стилі, а не в реальному часі. Це означає, зокрема, що обчислення майже не витрачаються на перегляд та підтримання у порядку позицій і швидкостей частинок між зіткненнями. Серед подібних подійно-орієнтованих алгоритмів, також призначених для моделювання сипучих тіл, як, наприклад, алгоритм Д. Рапапорта (D. C. Rapaport)[10], ЛСА виділяється особливою простотою структури даних і способу керування цією структурою.

Для будь-якої частинки й на будь-якій стадії обчислень ЛСА зберігає запис лише про дві події: про прораховану, яка вже відбулася, і про нову, ще тільки намічену до виконання подію. Нова подія може і не відбутися, як намічено. Запис про подію складається з: часової мітки події, запису стану частинки відразу після події (включно з положенням і швидкістю частинки), а також ідентифікації «партнера» частинки за даною подією, якщо такий виявляється. Партнером може бути інша частинка, або стінка посудини. Максимум відміток часу здійснених подій не може перевершити мінімуму відміток часу подій, намічених до виконання.

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

В міру прогресу обчислень, частоти зіткнень частинок у модельованому часі можуть зростати і зазвичай справді зростають. Проте, система успішно наближається до підсумкового стиснутого стану, якщо тільки частоти зіткнень різних частинок виявляються порівнянними між собою. (Окрім ратлерів. Останні зазнають стійко низьких частот зіткнень, і ця властивість ратлерів дозволяє їх легко виявити). Однак можливо, що деяке невелике число частинок, навіть одна єдина частинка, буде зазнавати надмірно високої частоти зіткнень, яка зростає, порівняно з іншими частинками, при наближенні модельованого часу до деякої часової позначки. Якщо таке трапляється, процес моделювання застряє на цій часовій позначці, не в змозі досягти бажаного стиску частинок.

Подібне застрягання в модельованому часі може статися і в режимі простого моделювання сипучого тіла без стиснення або розширення частинок. Така відмова в роботі алгоритму відома серед тих, хто займається моделюванням сипучих тіл, під назвою «непружний колапс», оскільки його типова причина в неідеальній пружності зіткнень[11]. Цей вид відмови не специфічний тільки для ЛСА. Запропоновано методи уникнення непружного колапсу.

Історія створення алгоритму

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

Паралельним прискоренням вважалося відношення часу розрахунку за використання одного процесора паралельної машини до часу розрахунку за використання всіх процесорів, за умови застосування одного і того ж алгоритму. Борис Любачевський зауважив, що така оцінка паралельного прискорення може бути завищеною, оскільки виконання задачі на одному процесорі за допомогою паралельної програми — не обов'язково найшвидший метод обчислень, які можна організувати на цьому процесорі для розв'язування цієї задачі. ЛСА створено як спробу знайти швидший однопроцесорний метод моделювання і тим самим поліпшити якість оцінки паралельного прискорення. Згодом запропоновано і паралельний алгоритм моделювання, відмінний від алгоритму Згортання часу, який зводиться до ЛСА, якщо виконується на одному процесорі[14].

Примітки
  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. 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. 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.
  14. 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.