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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتمLubachevsky–Stillinger ، یکی از روشهای متعددی است که مرحله فیزیکی را محدود و یا تشبیه می سازد.مثلاً،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، ۲۰۰۴.

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. ۳۷۳-۴۱۱

پیوند به بیرون[ویرایش]