루바체프스키-스틸링거 알고리즘

Lubachevsky–Stillinger algorithm

Lubachevsky-Stillinger(압축) 알고리즘(LS 알고리즘, LSA 또는 LS 프로토콜)은 F가 제시한 수치적 절차다. H. 스틸링거와 B.D.루바체프스키(Lubachevsky)는 단단한 입자 집단을 압축하는 물리적 과정을 시뮬레이션하거나 모방한다.[1]LSA는 몇 개의 입자라도 수천 개의 산술 연산이 필요할 수 있기 때문에 보통 컴퓨터로 수행된다.

루바체프스키-스틸링거 알고리즘의 변형을 사용하여 1000개의 응축 이소셀 삼각형이 주기적(와핑) 경계로 직사각형 안에 임의로 포장된다.양방향 패턴 반복 기간인 직사각형이 표시된다.포장 밀도는 0.8776이다.

현상학

압축의 물리적 과정은 종종 입자를 누르고 있는 피스톤과 같이 용기의 단단한 경계가 수축되는 것을 포함한다.LSA는 그러한 시나리오를 시뮬레이션할 수 있다.[2]그러나, LSA는 원래 가상 입자가 정기적인 경계 조건을 가진 고정되고 유한한 가상 볼륨에서 확장되거나 "흡수"되는 경계가[1][3] 없는 설정에서 도입되었다.입자의 절대 크기는 증가하고 있었지만 입자 대 입자 상대 크기는 일정하게 유지되었다.일반적으로 LSA는 외부 압축과 내부 입자 확장을 처리할 수 있는데, 이는 동시에 발생할 수 있고, 동시에 발생할 수 있지만 반드시 그렇지는 않다.게다가, 경계는 움직일 수 있다.

최종, 압축 또는 "걸림" 상태에서, 일부 입자는 걸리지 않으며 움직이지 않고 꽉 막힌 이웃과 단단한 경계로 형성된 "케이지" 내에서 움직일 수 있다.이러한 자유 이동 입자는 인공물이나 사전 설계 또는 LSA의 표적 기능이 아니라 실제 현상이다.시뮬레이션은 이러한 현상을 드러냈는데, LSA의 저자들에게는 다소 뜻밖이었다.프랭크 H. 스틸링거(Frank H. Stillinger)는 자유롭게 움직이는 입자들을 위해 "래틀러(rattler)"라는 용어를 만들었다. 왜냐하면 물리적으로 단단한 입자 뭉치를 흔들면 래틀러가 덜컹거릴 것이기 때문이다.

"사전 걸림" 모드에서 구성 밀도가 낮고 입자가 이동 중일 때는 압축과 팽창을 원하는 경우 중지할 수 있다.그러면 LSA는 사실상 세밀한 흐름을 시뮬레이션하고 있을 것이다.순간 충돌의 다양한 역학(예: 완전한 회복 여부, 접선 마찰 유무 또는 유무)은 시뮬레이션할 수 있다.입자 질량의 차이를 고려할 수 있다.또한 전체 또는 일부 입자의 크기를 줄임으로써 걸린 구성을 "유체화"하는 것이 쉽고 유용하다는 것을 입증한다.LSA의 또 다른 가능한 확장은 하드 충돌력 전위(입자 외부 0, 무한대 또는 내부)를 조각처럼 일정한 힘의 전위로 대체하는 것이다.따라서 수정된 LSA는 연속적인 단거리 입자-입자-입자간 힘 상호작용을 통해 분자역학을 대략적으로 시뮬레이션할 수 있다.각 입자의 충돌 운동이 간단한 한 단계 계산으로 표현될 수 있는 한 중력 같은 외부 힘 장도 도입할 수 있다.

다른 크기의 구상 입자 및/또는non-commeasureable 크기 용기에 전파 방해에 대해 LSA 사용 및 공부 micro-structures 결정 학적인 defect[4]이나 기하학적 frustration[5][6]의 원본 LS프로토콜 primaril 설계되었다 추가될 조건 아래 형성되는 것을 위해 유용한 기술임을 입증했다.구상 렌즈에 y크기가 같거나 다른 [7]eres

구를 타원형(또는 2차원의 타원형)으로 교체할 때 가장 단순한 구면(또는 2차원의 원형) 형상으로부터의 편차는 따라서 수정된 LSA가 상당히 느려지게 한다.[8]그러나 모양이 구형인 한 LSA는 오늘날(2011년) 표준 개인용 컴퓨터에서 수만에서 수십만 개의 입자 조립품을 처리할 수 있다.LSA를 3보다 높은 치수로 사용하는 것은 극히 제한적인 경험에[9] 불과했다.

실행

입자 방해 상태는 미세한 흐름을 시뮬레이션함으로써 달성된다.흐름은 입자-입자-입자-경계 충돌인 이산 이벤트 시뮬레이션으로 렌더링된다.이상적으로 계산은 무한정 정밀도로 수행되어야 한다.그렇다면 그 방해는 순식간에 일어났을 것이다.실제로 정밀도는 컴퓨터 메모리에서 실수를 나타낼 수 있는 해상도(예: 이중 정밀 분해능)로서 유한하다.실제 계산은 비 래틀러 입자의 충돌 런이 명시적으로 또는 암묵적으로 지정된 작은 임계값보다 작을 때 중지된다.예를 들어, 충돌 간 실행이 반올림 오차보다 작을 때 계산을 계속하는 것은 소용이 없다.

LSA는 이벤트가 본질적으로 시간 주도형 방식이 아닌 이벤트 중심 방식으로 처리된다는 점에서 효율적이다.이것은 충돌 사이의 입자의 위치와 속도를 계산하거나 유지하는 데 거의 어떤 계산도 낭비되지 않는다는 것을 의미한다.예를 들어, D.C의 알고리즘과 같은 세밀한 흐름을 시뮬레이션하는 동일한 작업을 위해 의도된 이벤트 기반 알고리즘 중에서.라파포트,[10] LSA는 더 단순한 데이터 구조와 데이터 처리로 구분된다.

계산 단계에서 모든 입자에 대해 LSA는 두 가지 이벤트만 기록한다. 즉, 커밋된 이벤트 타임스탬프, 입자 상태(위치 및 속도 포함), 그리고 다른 입자 또는 경계 식별이 될 수 있는 "파트너"가 그것이다.e는 과거에 충돌했고, 유사한 매개변수 집합을 가진 미래 처리를 위해 제안된 새로운 이벤트.그 새로운 사건은 커밋되지 않았다.커밋된 이전 이벤트 시간의 최대값은 커밋되지 않은 새 이벤트 시간의 최소값을 초과해서는 안 된다.

알고리즘에 의해 검사될 다음 입자는 현재 최소의 새 이벤트 시간을 가진다.선택된 입자를 검사할 때, 이전에 새로운 사건이었던 것은 이전 사건이고 실행될 것이라고 선언된다. 반면에 다음 새로운 사건은 새로운 타임 스탬프, 새로운 상태, 그리고 만약 있다면 새로운 파트너와 함께 예정되어 있다.입자에 대한 다음 새로운 이벤트가 설정되고 있을 때, 이웃한 입자 중 일부는 새로운 정보를 더 잘 설명하기 위해 커밋되지 않은 새로운 이벤트를 업데이트할 수 있다.

LSA의 계산이 진행됨에 따라 입자의 충돌 속도는 증가할 수 있고 보통 증가한다.그럼에도 불구하고 LSA는 래틀러를 제외한 모든 입자 중에서 그러한 비율이 비교 가능한 한 방해 상태에 성공적으로 접근한다. (래틀러는 지속적으로 낮은 충돌률을 경험한다.)이 속성은 쥐를 탐지할 수 있게 한다.)그러나, 단지 하나의 입자일지라도, 몇 개의 입자가 특정 시뮬레이션 시간에 대한 접근에 따라 매우 높은 충돌률을 경험하는 것은 가능하다.그 비율은 나머지 입자 앙상블의 충돌 속도에 비례하여 제한 없이 증가할 것이다.이렇게 되면 시뮬레이션이 제시간에 걸려서 방해 상태로 진행될 수 없게 된다.

시간 고정 실패는 입자 압축이나 팽창 없이 세밀한 흐름을 시뮬레이션할 때도 발생할 수 있다.이 고장 모드는 충돌 시 회복 계수가 낮을 때(즉, 비탄력적) 그러한 시뮬레이션에서 종종 발생하기 때문에 세분화된 흐름 시뮬레이션의 실무자들에 의해 "비탄성 붕괴"로 인식되었다.이 실패는 LSA 알고리즘에만 국한되지 않는다.실패를 피하기 위한 기법이 제안되었다.[12]

역사

LSA는 병렬 시뮬레이션에서 공정한 속도 향상을 찾으려는 시도의 부산물이었다.데이비드 제퍼슨에 의한 타임워프 병렬 시뮬레이션 알고리즘은 병렬 컴퓨터에서 전투부대의 비동기 공간 상호작용을 시뮬레이션하는 방법으로 발전되었다.[13]충돌 입자 모델은[14] 입자의 공간 상호작용과 유사한 시뮬레이션 작업을 제공했지만 시뮬레이션 기법을 노출하는 데 필수적이지 않은 세부 사항은 삭제했다.속도 상승은 동일한 병렬 시간 워프 알고리즘을 실행할 때 멀티프로세서에 대한 단일 프로세서 실행 시간의 비율로 제시되었다.보리스 D.Lubachevsky는 단일 프로세서에서 작업에 대한 병렬 알고리즘을 실행하는 것이 반드시 그러한 기계에서 작업을 수행하는 가장 빠른 방법은 아니기 때문에 그러한 속도 향상 평가가 결함이 있을 수 있다는 것을 알아챘다.LSA는 더 빠른 유니프로세서 시뮬레이션을 생성하여 병렬 속도 증가를 보다 공정하게 평가하기 위해 만들어졌다.나중에, 타임 워프와는 다른 병렬 시뮬레이션 알고리즘도 제안되었는데, 단프로세서로 실행하면 LSA로 감소한다.[15]

참조

  1. ^ a b Lubachevsky, Boris D.; Stillinger, Frank H. (1990). "Geometric properties of random disk packings" (PDF). Journal of Statistical Physics. 60 (5–6): 561–583. Bibcode:1990JSP....60..561L. doi:10.1007/bf01025983.
  2. ^ Stillinger, Frank H.; Lubachevsky, Boris D. (1993). "Crystalline-amorphous interface packings for disks and spheres". Journal of Statistical Physics. 73 (3–4): 497–514. doi:10.1007/bf01054337.
  3. ^ Lubachevsky, Boris D. (1991). "How to simulate billiards and similar systems". Journal of Computational Physics. 94 (2): 255–283. arXiv:cond-mat/0503627. Bibcode:1991JCoPh..94..255L. doi:10.1016/0021-9991(91)90222-7.
  4. ^ Stillinger, Frank H.; Lubachevsky, Boris D. (1995). "Patterns of broken symmetry in the impurity-perturbed rigid-disk crystal". Journal of Statistical Physics. 78 (3–4): 1011–1026. Bibcode:1995JSP....78.1011S. doi:10.1007/bf02183698.
  5. ^ Lubachevsky, Boris D.; Stillinger, Frank H. (2004). "Epitaxial frustration in deposited packings of rigid disks and spheres". Physical Review E. 70 (4): 041604. arXiv:cond-mat/0405650. Bibcode:2004PhRvE..70d1604L. doi:10.1103/physreve.70.041604. PMID 15600418.
  6. ^ Lubachevsky, Boris D.; Graham, Ron L.; Stillinger, Frank H. (1995). "Spontaneous Patterns in Disk Packings". Visual Mathematics.
  7. ^ Kansal, Anuraag R.; Torquato, Salvatore; Stillinger, Frank H. (2002). "Computer generation of dense polydisperse sphere packings". The Journal of Chemical Physics. 117 (18): 8212–8218. Bibcode:2002JChPh.117.8212K. doi:10.1063/1.1511510.
  8. ^ Donev, Aleksandar; Stillinger, Frank H.; Chaikin, P. M.; Torquato, Salvatore (2004). "Unusually Dense Crystal Packings of Ellipsoids". Physical Review Letters. 92 (25): 255506. arXiv:cond-mat/0403286. Bibcode:2004PhRvL..92y5506D. doi:10.1103/physrevlett.92.255506. PMID 15245027.
  9. ^ Skoge, Monica; Donev, Aleksandar; Stillinger, Frank H.; Torquato, Salvatore (2006). "Packing hyperspheres in high-dimensional Euclidean spaces". Physical Review E. 74 (4): 041127. arXiv:cond-mat/0608362. Bibcode:2006PhRvE..74d1127S. doi:10.1103/physreve.74.041127. PMID 17155042.
  10. ^ Rapaport, D.C (1980). "The event scheduling problem in molecular dynamic simulation". Journal of Computational Physics. 34 (2): 184–201. Bibcode:1980JCoPh..34..184R. doi:10.1016/0021-9991(80)90104-7.
  11. ^ McNamara, Sean; Young, W. R. (1994). "Inelastic collapse in two dimensions". Physical Review E. 50 (1): R28–R31. Bibcode:1994PhRvE..50...28M. doi:10.1103/physreve.50.r28. PMID 9962022.
  12. ^ Drozd, John J. (2004). Computer Simulation of Granular Matter: A Study of An Industrial Grinding Mill (PDF) (Thesis). Canada: Univ. Western Ontario. Archived from the original (PDF) on 2011-08-18. Retrieved 2011-05-25.
  13. ^ F. Wieland, 그리고 D.Jefferson, 직렬 및 병렬 시뮬레이션 사례 연구, Proc. 1989년 Int'l Conf.병렬 처리, Vol.III, F. Ris, M. Kogge, Eds, 페이지 255-258.
  14. ^ P. 혼탈레스, B.벡먼, 외 연구진, 타임 워프 운영 체제의 충돌 퍽 시뮬레이션 성능, Proc. 1989 SCS 멀티콘퍼런스, 시뮬레이션 시리즈, SCS, Vol. 21, No. 2, 페이지 3-7.
  15. ^ Lubachevsky, B.D. (1992). "Simulating Billiards: Serially and in Parallel". International Journal in Computer Simulation. 2: 373–411.

외부 링크