الگوریتم لوباچفسکی-ستلینگر

بندانگشتی|با استفاده از گونه‌ای از الگوریتم لوباچفسکی-ستلینگر، تعداد ۱۰۰۰ مثلث متساوی‌الساقین متجانس، به‌طور تصادفی با فشرده‌سازی در یک مستطیل با مرز تناوبی (در اطراف) بسته‌بندی می‌شوند. مستطیلی‌که دورهٔ تکرار الگو در هر دوجهت است، قابل مشاهده است. چگالی بسته‌بندی ۰,۸۷۷۶ است.
** الگوریتم لوباچفسکی-ستلینگر** یکی از روش‌های متعددی است که مرحله فیزیکی را محدود یا تشبیه می‌سازد. مانند LSA ممکن است نیاز به هزاران عمل‌کننده علم حساب داشته باشد حتی برای محدودی از اجزاء، آن معمولاً روی یکی از کامپیوترهای دیجیتال مطرح شده‌است.

## پدیده‌شناسی (چه چیزی شبیه‌سازی شود؟)
کاربرد الگوریتم‌های گوناگون Lubachevsky-stillinger، هزاران مثلث مجزا به‌طور مرتب توسط تراکم در یک مربع با مرز دوره‌ای بسته بندی نشوند. این مستطیل دوره‌ای از تکرار الگو در هر دو مسیری است که نشان داده نشده‌است. شدت بسته‌بندی برابر ۰٫۸۷۷۶، شدت اصلاح ساخته نشده به محتویات جهت یافته مثلثی بستگی دارد.
یکی از مراحل تراکم فیزیکی اغلب شامل کنتراکت مرز دشوارظرفی می‌شود مثل پیستونی که بر خلاف اجزایی فشار وارد می‌کند.LSA همچنین قادر است تا چنین سناریوهایی را شبیه‌سازی کند. اما،LSA اصولاً در محیطی بدون مرز دشواری تولید شده که اجزاء جزئی «متورم» ویا به‌طور ثابتی گسترده می‌شوند یا حجم مجازی را با شرایط مرزو محدودیت دوره‌ای محدود می‌سازند.

اندازه‌های مطلق اجزاء در حال افزایش بودند اما اندازه‌ای مرتبط جزء به جزء پایدار باقی‌ماندند. در کل ،LSA می‌تواند تراکم خروجی یا تراکم جز ورودی را نگهداری کند که هر دو به‌طور هم‌زمان و احتمالی رخ می‌دهند اما ضروری نیست که با محدودیت دشواری ترکیب شوند به علاوه، محدودیت می‌تواند حرکت کند. در نهایت، متراکم نشده یا حالت «جامد» و بعضی اجزاء غیر جامدند، آن‌ها قادرند تا بین «قفسی‌هایی» که توسط همسایگی جامد، غیر حرکت نشان یا محدودیت دشواری که تشکیل شدند جابه جا شوند. اگر هیچ چیزی نباشد این اجزاء آزاد برای حرکت یک طراحی از قبل تعیین شده، مصنوعی یا ویژگی مقصد LSA نیست اما نسبتاً یک پدیده واقعی است. این شبیه‌سازی پدیده‌ای را آشکار کرد، مقدار کمی به‌طور غیرمفروضی برا نویسندگان LSA می‌باشند.

فرانک، ایچ بخش "Rattlers" را برای اجزاء آزاد جست حرکت را مطرح ساخت زیرا اگر یکی به‌طور فیزیکی دسته‌ای از اجزاء دشواری و متراکم نشده‌ای را تکان دهد Rattlersها خیلی تند خواهند شد. در حالت" از قبل تعیین نشده ماده جامد" که شدت تغییر شکل پایین است، وقتی این اجزاء حرکت کنند تراکم و گستردگی می‌توانند متوقف شوند اگر خیلی مطلوب نباشد. سپس LSA مؤثرا یک جریان دانه‌ای را شبیه نمی‌سازند. دینامیک‌های گوناگونی از تصادم‌ها یا برخوردهای هم‌زمان می‌توانند شبیه مبهم شوند مثلاً؛ با یا بدون جبران کامل، با یا بدون تناسب مماسی، اختلافات در توده‌های اجزاء که می‌توانند محاسبه شوند. آن همچنین آسان است، بعضی اوقات برای" تبدیل به مایع" تغییر شکل جامدی با کاهش اندازه تمامی یا بعضی از اجزاء اثبات می‌شود. گسترش ممکن دیگری از LSA تصادم دشوار نیروی نهفته‌ای را با نیروی نهفته پایدار قطعه جابه جا می‌سازد؛ لذا LSA اصلاح نشده تقریباً محرک‌های مولکولی را با واکنش نیروی جزء به جزء ردیف کوتاه مداوم شبیه می‌سازد. زمینه‌های نیروی خروجی مثل گرانش می‌توانند ایجاد شوند و گاهی وقتها جنبش تصادف درونی هر جزء می‌تواند توسط محاسبه یک مرحله‌ای ساده نشان داده شود. کاربرد LSA برای اجزایی از اندازه‌های مختلف یا برای ماده جامد در ظرف اندازه غیرقابل تجارت اثبات شده یک فن مفیدی برای تنظیم و بررسی ساختارهای کوچکی دارد که تحت شرایط دفاع نمودار کریستالی تشکیل شده یا شامل ساختار هندسی می‌شود. باید اضافه کرد که پروتکل LS اصلی اصولاً برای سپرهای همان یا سایزهای مختلفی طراحی شده‌است. هر مشتق از شکل سپرمانند حتی یکی ساده‌ترین با شکل بیضوی جابه جا شده که موجب می‌شود بنابراین LSA را با کند شدن به سمت رو به پایین اصلاح کرده‌است. گاهی وقتها این شکل دارای سپر می‌شود.LSA قادر به نگهداری شباهت‌های جزئی در دهها به صدها وهزاران کامپیوتر شخصی استاندارد امروزی می‌شوند تنها یکی از تجربیات محدود در کاربرد LSa در بعدهای بیشتر از سه گزارش داده شده بود.

## استنباط
حالت اجزاء جامد از طریق یک جریان دانه‌ای شبیه‌ساز انجام شده‌است. این جریان به عنوان یکی از شبیه‌سازهای حادثه مجزا انتقال داده شده‌است، این حوادث تصادمات محدودیت اجزاء یا جزء به جزء می‌شود. عقیدتا، محاسبات باید با دقت محدودی تشکیل شود. سپس جامد بودن به‌طور نامحدودی رخ خواهد داد. در این روش، این صراحت به عنوان راه حل موجودی از تعداد واقعی که در حافظه کامپیوتری نشان داده می‌شود محدود می‌شود به عنوان مثال، مثل یکی از راه حل‌های مشکوک- دقیق محاسبات واقعی متوقف می‌شوند وقتی که تصادف درونی از اجزاء بدون Rattlers جابه جا شود که بیشتر از آستانه کوچک خاص دقیق و غیر دقیقی می‌شود. به عنوان مثال، برای ادامه محاسبات فرمانی ادامه می‌یابد و مفید است که جریانات تصادف داخلی کوچکتر از خطای خاموش بی خرده‌ای شوند.

LSA در جهتی کافی می‌شود که حوادث اساساً در سبک حادثه محرک نسبتاً در یک سبک زمان گرداننده برنامه‌ریزی شوند. این تقریباً به معنای هیچ محاسبه‌ای نیست که روی محاسبه تا نگهداری وضعیت در بردارهای اجزاء بین تصادمات اتلاف شود. میان الگوریتم‌های حادثه مشتق شده که برای همان وظیفه جریان دانه‌ای شبیه‌ساز جهت یافته شده به عنوان مثال الگوریتم .D.C وLSA توسط ساختار داده‌های ساده‌ترونگهداری داده‌ها شناسایی شده‌است. برای هر اجزاء در هر مرحله محاسبات LSA گزارشی از دو حادثه را نگه می‌دارند یک حادثه برنامه‌ریزی شده یا قدیمی که زمان حادثه و حالت اجزاء را توجیه کرده شاید «شریک» بتواند با سایر اجزاء یا ویژگی محدودی و یکی با اجزائی در بخشی مطرح شود و یک حادثه جدید برای پردازش آینده با مجموعه مشابهی از پارامترها برنامه‌ریزی شده‌است این حادثه جدید انجام نشده‌است. حداقل توجیه زمان حادثه قدیمی مینیمم حادثه زمان جدیدی را نباید ترقی دهد. اجزای دیگری که توسط الگوریتم تحت آزمایش قرار گرفته حداقل جریانی از زمان حادثه جدیدی دارد. این نسبت بدون محدودیتی در تناسب نسبت تصادمات در مجموعه اجزاء افزایش خواهد یافت. اگر این عمل اتفاق بیفتد آنگاه شبیه‌سازی در زمانی وقفه ایجاد خواهد کرد، و آن قادر به پیشرفت به سمت حالت جامد نخواهد شد.

شکست وضعیت خطا در زمان همچنین زمانی می‌تواند اتفاق بیفتد که جریان دانه‌ای بدون تراکم جزئی یا گسترش شبیه‌ساز می‌شود. مدل شکست توسط شرکت کنندگان جریان دانه‌ای تحت شناسایی قرار گرفته که به عنوان «سقوط غیرقابل انعطاف» شبیه می‌شود زیرا اغلب در چنین تشبیه‌هایی وقتی رخ می‌دهد که ضریب جبران در تصادف پایین است. این شکست نه تنها در الگوریتم LSA خاص نیست بلکه روش‌هایی از نقص اجتناب می‌کنند که برنامه‌ریزی شده‌اند.

## تاریخچه
LSA با ایجاد تلاش مقیاس نسبی سرعت بالا در شباهت‌های موازی را می‌یابد. الگوریتم شبیه‌ساز موازی انحراف زمان توسط دیوید جفرسون به عنوان روشی پیشرفت کرده تا واکنش‌های خاص همزمانی از بخش‌های جنگیدن را در مدل‌های رزمی روی یک کامپیوتر موازی شبیه‌ساز شوند. مدل‌های اجزاء در حال تصادم وظایف شبیه‌ساز مشابهی را با واکنش‌های خاصی از اجزاء پیشنهاد کردند اما وضوح این جزئیات برای فن‌های مشابه غیر اصولی است.

سرعت بالا به عنوان معیاری از زمان اجرا روی پردازشگر و چند مرحله‌ای نشان داده شده وقتی همان الگوریتم موازی زمان اجرا شوند. Boris D به این نکته توجه کرد که چنین ارزیابی سرعت بالا ممکن است دارای الگوریتم موازی برای وظیفه غیر پردازشگر شود که ضرورتاً روش سریعتری نیست تا عمل چنین دستگاه‌هایی را تشکیل دهد.LSA در تلاشی ایجاد شده تا شبیه بدون پردازشگر سریعتری را ایجاد کند از آنجایی که ارزیابی نسبی تری از سرعت بالای موازی را داراست. بعداً الگوریتم شبیه‌ساز موازی و مختلفی از زمان انحراف برنامه‌ریزی شده وقتی یک غیر فرایند جابه جا شود یا موجب کاهش LSA شود.

## منابع


F. H. Stillinger and B. D. Lubachevsky، Crystalline-Amorphous Interface Packings for Disks and Spheres، J. Stat. Phys. ۷۳، ۴۹۷–۵۱۴ (۱۹۹۳)
B. D. Lubachevsky and F. H. Stillinger، Geometric properties of random disk packings، J. Statistical Physics ۶۰ (۱۹۹۰)، ۵۶۱–۵۸۳ http://www.princeton.edu/~fhs/geodisk/geodisk.pdf
F. H. Stillinger and B. D. Lubachevsky. Patterns of Broken Symmetry in the Impurity-Perturbed Rigid Disk Crystal، J. Stat. Phys. ۷۸، ۱۰۱۱–۱۰۲۶ (۱۹۹۵)
Boris D. Lubachevsky and Frank H. Stillinger، Epitaxial frustration in deposited packings of rigid disks and spheres. Physical Review E ۷۰:۴۴، ۴۱۶۰۴ (۲۰۰۴) http://arxiv.org/PS_cache/cond-mat/pdf/0405/0405650v5.pdf
Boris D. Lubachevsky، Ron L. Graham، and Frank H. Stillinger، Spontaneous Patterns in Disk Packings
Visual Mathematics، ۱۹۹۵.
http://vismath5.tripod.com/lub/
A.R. Kansal، S. Torquato، and F.H. Stillinger، Computer Generation of Dense Polydisperse Sphere Packings، J. Chem. Phys. ۱۱۷، ۸۲۱۲–۸۲۱۸ (۲۰۰۲) http://cat.inist.fr/?aModele=afficheN&cpsidt=13990882
A. Donev، F.H. Stillinger، P.M. Chaikin، and S. Torquato، Unusually Dense Crystal Packings of Ellipsoids، Phys. Rev. Letters ۹۲، ۲۵۵۵۰۶ (۲۰۰۴)
M. Skoge، A. Donev، F.H. Stillinger، and S. Torquato، Packing Hyperspheres in High-Dimensional Euclidean Spaces، Phys. Rev. E ۷۴، ۰۴۱۱۲۷ (۲۰۰۶)
D.C. Rapaport،
The Event Scheduling Problem in Molecular Dynamic Simulation،
Journal of Computational Physics
Volume ۳۴ Issue ۲، ۱۹۸۰

S. McNamara، and W.R. Young، Inelastic collapse in two dimensions، Physical
Review E ۵۰: pp. R۲۸-R۳۱، ۱۹۹۴

John J. Drozd، Computer Simulation of Granular Matter:
A Study of An Industrial Grinding Mill،
Thesis، Univ. Western Ontario، Canada، ۲۰۰۴.

https://web.archive.org/web/20110818102135/http://imaging.robarts.ca/~jdrozd/thesisjd.pdf
B.D. Lubachevsky، How to Simulate Billiards and Similar Systems،
Journal of Computational Physics
Volume ۹۴ Issue ۲، May ۱۹۹۱
http://arxiv.org/PS_cache/cond-mat/pdf/0503/0503627v2.pdf

F. Wieland، and D. Jefferson،
Case studies in serial and parallel simulations،
Proc. ۱۹۸۹ Int'l Conf. Parallel Processing،
Vol.III، F. Ris، and M. Kogge، Eds. ، pp. ۲۵۵–۲۵۸.

P. Hontales، B. Beckman، et al. ، Performnce of the colliding pucks simulation of the Time Warp operating systems، Proc. ۱۹۸۹ SCS Multiconference، Simulation Series، SCS، Vol. ۲۱، No. ۲، pp. ۳–۷.

B.D. Lubachevsky، Simulating Billiards: Serially and in Parallel، Int.J. in Computer Simulation، Vol. ۲ (۱۹۹۲)، pp. ۳۷۳–۴۱۱



## پیوند به بیرون

* LSA in action. A collection of animations by Alexander Donev
* Source C++ codes of a version of the LSA in arbitrary dimensions
* Volume fluctuation distribution in granular packs studied using the LSA
* LSA generalized for particles of arbitrary shape
* LSA used for production of representative

رده:الگوریتم‌ها
رده:فیزیک محاسباتی
رده:مدل‌سازی علمی
رده:دانه‌بندی مواد
رده:شبیه‌سازی