ルバチェフスキー・スティリンガーアルゴリズム

ルバチェフスキー-スティリンガー（圧縮）アルゴリズム（LSアルゴリズム、LSA、またはLSプロトコル）は、FHスティリンガーとボリス・D・ルバチェフスキーによって提案された数値手順であり、硬い粒子の集合を圧縮する物理的プロセスをシミュレートまたは模倣する。[ 1 ] LSAは、数個の粒子に対しても数千の算術演算を必要とする場合があるため、通常はコンピュータ上で実行される。

ルバチェフスキー・スティリンガー法の変形を用いて、1000個の合同な二等辺三角形を、周期的な（ラップアラウンド）境界を持つ長方形にランダムに圧縮して詰め込む。この長方形は、両方向のパターン繰り返し周期に相当する。詰め込み密度は0.8776である。

現象学

圧縮という物理的なプロセスには、ピストンが粒子に押し付けられるなど、容器の収縮する硬い境界が伴うことが多い。LSAはこのようなシナリオをシミュレートすることができる。[ 2 ]しかし、LSAはもともと硬い境界のない設定で導入された[ 1 ] [ 3 ] 。つまり、仮想粒子は周期境界条件を持つ固定された有限の仮想体積内で「膨張」または膨張していた。粒子の絶対サイズは増加していたが、粒子間の相対サイズは一定であった。一般に、LSAは外部圧縮と粒子内部膨張の両方に対応でき、これらは同時に発生し、硬い境界と組み合わされる可能性もあるが、必ずしもそうである必要はない。さらに、境界は可動である可能性がある。

最終的な圧縮状態、つまり「ジャム状態」では、一部の粒子はジャム状態ではなく、動かないジャム状態の隣接粒子と、もしあればハード境界によって形成される「ケージ」内を移動できます。これらの自由に移動できる粒子は、LSAの人工物でも、事前に設計されたものでも、ターゲット特性でもなく、現実の現象です。シミュレーションによってこの現象が明らかになりましたが、これはLSAの作者にとってやや予想外のことでした。フランク・H・スティリンガーは、この自由に移動できる粒子を「ラトラー（rattlers）」と名付けました。圧縮されたハード粒子の束を物理的に振ると、ラトラーがガラガラと音を立てるからです。

「プレジャム」モードでは、構成の密度が低く、粒子が移動可能な場合、必要に応じて圧縮と膨張を停止できます。この場合、LSAは実質的に粒状流をシミュレートすることになります。瞬間衝突の様々なダイナミクスをシミュレートできます。例えば、完全な復元の有無、接線摩擦の有無などです。粒子の質量差も考慮に入れることができます。また、粒子の全部または一部のサイズを小さくすることで、ジャム構成を「流動化」することも容易であり、場合によっては有用であることが証明されています。LSAのもう一つの拡張として、硬い衝突力ポテンシャル（粒子の外側ではゼロ、粒子の内側では無限大）を区分的に一定の力ポテンシャルに置き換えることが挙げられます。このように修正されたLSAは、連続的な短距離粒子間力相互作用を伴う分子動力学を近似的にシミュレートします。各粒子の衝突間運動を単純なワンステップ計算で表現できる限り、 重力などの外力場も導入できます。

異なるサイズの球状粒子や測定不可能なサイズの容器に詰まった球状粒子にLSAを使用することは、結晶学的欠陥[ 4 ]や幾何学的フラストレーション[ 5 ]の条件下で形成される微細構造を生成および研究するための有用な手法であることが証明されました[ 6 ]。元のLSプロトコルは、主に同じサイズまたは異なるサイズの球状粒子用に設計されたことを付け加えておく必要があります。[ 7 ]

球面（または2次元では円）の形状から少しでも逸脱すると、たとえ球面を楕円体（または2次元では楕円）に置き換えた場合でも、その形状は極めて単純であり、 LSAの速度は大幅に低下します。 [ 8 ]しかし、形状が球面である限り、LSAは今日（2011年）の標準的なパーソナルコンピュータで数万から数十万の粒子集合体を処理できます。3 次元を超える高次元でのLSAの使用については、 非常に限られた事例しか報告されていません[ 9 ] 。

実装

粒子の詰まりの状態は、粒状流をシミュレートすることで実現されます。この流れは、粒子間衝突または粒子境界衝突という離散イベントシミュレーションとしてレンダリングされます。理想的には、計算は無限精度で実行されるべきです。そうすれば、詰まりは無限に発生します。実際には、精度は有限であり、コンピュータメモリ内で実数を表現できる解像度（倍精度解像度など）も有限です。実際の計算は、ラトラー粒子以外の粒子の衝突間ランが、明示的または暗黙的に指定された小さなしきい値よりも小さくなったときに停止します。たとえば、衝突間ランが丸め誤差よりも小さい場合、計算を続行しても無駄です。

LSAは、イベントが時間駆動型ではなく、本質的にイベント駆動型で処理されるという点で効率的です。つまり、衝突間の粒子の位置と速度の計算や維持に無駄な計算はほとんど発生しません。例えばDC Rapaportのアルゴリズム[ 10 ]のように、粉体流のシミュレーションという同じタスクを目的としたイベント駆動型アルゴリズムの中で、 LSAはよりシンプルなデータ構造とデータ処理によって際立っています。

LSAは、計算のどの段階においても、どの粒子に対しても、2つのイベントのみを記録します。1つは既に処理済みのコミット済みイベントで、コミット済みイベントのタイムスタンプ、粒子の状態（位置と速度を含む）、そして場合によっては「パートナー」（過去に粒子が衝突した別の粒子または境界の識別子）で構成されます。もう1つは、同様のパラメータセットを用いて将来の処理のために提案される新しいイベントです。新しいイベントはコミットされません。コミット済みの古いイベント時間の最大値は、コミットされていない新しいイベント時間の最小値を超えてはなりません。

アルゴリズムによって次に検査される粒子は、新規イベント時刻の最小値を持つ粒子です。選択された粒子を検査する際に、以前の新規イベントは古いイベントとして宣言され、コミットされます。一方、次の新規イベントは、新しいタイムスタンプ、新しい状態、そして新しいパートナー（存在する場合）と共にスケジュールされます。粒子の次の新規イベントが設定されると、隣接する粒子の一部は、新しい情報をより適切に反映するために、コミットされていない新規イベントを更新する場合があります。

LSAの計算が進むにつれて、粒子の衝突率は増加する可能性があり、通常は実際に増加します。それでも、ラトラを除くすべての粒子の衝突率が同程度である限り、LSAはジャミング状態にうまく近づきます。（ラトラの衝突率は一貫して低いです。この特性により、ラトラを検出できます。）しかし、シミュレーションされた特定の時間に近づくにつれて、少数の粒子、たとえ1つの粒子であっても、非常に高い衝突率を経験する可能性があります。衝突率は、残りの粒子集団の衝突率に比例して、無制限に増加します。このような状況が発生すると、シミュレーションは時間的に行き詰まり、ジャミング状態に進むことができなくなります。

粒子の圧縮や膨張を伴わない粉体流のシミュレーションにおいても、スタックインタイムの失敗が発生することがあります。この失敗モードは、粉体流シミュレーションの専門家によって「非弾性崩壊」[ 11 ]として認識されています。これは、衝突における反発係数が低い（すなわち非弾性である）場合に、このようなシミュレーションで頻繁に発生するためです。この失敗はLSAアルゴリズムに特有のものではありません。この失敗を回避する手法が提案されています。[ 12 ]

歴史

LSA は、並列シミュレーションでスピードアップを公平に評価する試みの副産物でした。David Jefferson によるTime Warp並列シミュレーション アルゴリズムは、並列コンピュータ上の戦闘モデルで戦闘ユニットの非同期の空間的相互作用をシミュレートする方法として開発されました。[ 13 ]衝突粒子モデル[ 14 ]は、粒子の空間的相互作用を伴う同様のシミュレーション タスクを提供しましたが、シミュレーション手法を明らかにするために重要でない詳細は除かれていました。スピードアップは、同じ並列 Time Warp アルゴリズムを実行したときの、ユニプロセッサとマルチプロセッサの実行時間の比として提示されました。Boris D. Lubachevsky は、タスクの並列アルゴリズムをユニプロセッサで実行することが、必ずしもそのマシンでタスクを実行する最速の方法ではないため、このようなスピードアップの評価には誤りがある可能性があることに気付きました。LSA は、より高速なユニプロセッサ シミュレーションを作成し、それによって並列スピードアップをより公平に評価することを目的として作成されました。その後、タイムワープとは異なる並列シミュレーションアルゴリズムも提案され、これは単一プロセッサ上で実行するとLSAに縮小される。[ 15 ]

参考文献

  1. ^ a b Lubachevsky, Boris D.; Stillinger, Frank H. (1990). 「ランダムディスクパッキングの幾何学的性質」(PDF) . Journal of Statistical Physics . 60 ( 5–6 ): 561– 583. Bibcode : 1990JSP....60..561L . doi : 10.1007/bf01025983 . S2CID  15485746 .
  2. ^ Stillinger, Frank H.; Lubachevsky, Boris D. (1993). 「ディスクおよび球体における結晶-アモルファス界面充填」. Journal of Statistical Physics . 73 ( 3–4 ): 497– 514. doi : 10.1007/bf01054337 . S2CID 59429012 . 
  3. ^ Lubachevsky, Boris D. (1991). 「ビリヤードおよび類似システムのシミュレーション方法」. Journal of Computational Physics . 94 (2): 255– 283. arXiv : cond-mat/0503627 . Bibcode : 1991JCoPh..94..255L . doi : 10.1016/0021-9991(91)90222-7 . S2CID 6215418 . 
  4. ^ Stillinger, Frank H.; Lubachevsky, Boris D. (1995). 「不純物摂動を受けた剛体円盤結晶における対称性の破れのパターン」. Journal of Statistical Physics . 78 ( 3–4 ): 1011– 1026. Bibcode : 1995JSP....78.1011S . doi : 10.1007/bf02183698 . S2CID 55943037 . 
  5. ^ Lubachevsky, Boris D.; Stillinger, Frank H. (2004). 「剛体円板および球体の堆積パッキングにおけるエピタキシャルフラストレーション」. Physical Review E. 70 ( 4) 041604. arXiv : cond-mat/0405650 . Bibcode : 2004PhRvE..70d1604L . doi : 10.1103 /physreve.70.041604 . PMID 15600418. S2CID 1309789 .  
  6. ^ Lubachevsky, Boris D.; Graham, Ron L.; Stillinger, Frank H. (1995). 「円板パッキングにおける自発的パターン」 Visual Mathematics .
  7. ^ Kansal, Anuraag R.; Torquato, Salvatore; Stillinger, Frank H. (2002). 「高密度多分散球充填物のコンピュータ生成」. 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, PM; Torquato, Salvatore (2004). 「楕円体の異常に高密度な結晶充填」. Physical Review Letters . 92 (25) 255506. arXiv : cond-mat/0403286 . Bibcode : 2004PhRvL..92y5506D . doi : 10.1103/physrevlett.92.255506 . PMID 15245027 . S2CID 7982407 .  
  9. ^ Skoge, Monica; Donev, Aleksandar; Stillinger, Frank H.; Torquato, Salvatore (2006). 「高次元ユークリッド空間における超球のパッキング」. Physical Review E. 74 ( 4) 041127. arXiv : cond-mat/0608362 . Bibcode : 2006PhRvE..74d1127S . doi : 10.1103 / physreve.74.041127 . PMID 17155042. S2CID 18639889 .  
  10. ^ Rapaport, DC (1980). 「分子動力学シミュレーションにおけるイベントスケジューリング問題」. Journal of Computational Physics . 34 (2): 184– 201. Bibcode : 1980JCoPh..34..184R . doi : 10.1016/0021-9991(80)90104-7 .
  11. ^ McNamara, Sean; Young, WR (1994). 「2次元における非弾性崩壊」. Physical Review E. 50 ( 1): R28– R31. Bibcode : 1994PhRvE..50...28M . doi : 10.1103/physreve.50.r28 . PMID 9962022 . 
  12. ^ Drozd, John J. (2004).粒状物質のコンピュータシミュレーション：工業用粉砕機の研究(PDF) (論文). カナダ：ウェスタンオンタリオ大学.オリジナル(PDF)から2011年8月18日にアーカイブ。 2011年5月25日閲覧。
  13. ^ F. Wieland、D. Jefferson、「シリアルおよび並列シミュレーションのケーススタディ」、Proc. 1989 Int'l Conf. Parallel Processing、Vol.III、F. Ris、M. Kogge 編、pp. 255-258。
  14. ^ P. Hontales、B. Beckman、他「Time Warp オペレーティング システムの衝突パックのシミュレーションのパフォーマンス」、Proc. 1989 SCS Multiconference、シミュレーション シリーズ、SCS、Vol. 21、No. 2、pp. 3-7。
  15. ^ Lubachevsky, BD (1992). 「ビリヤードのシミュレーション：逐次および並列」.国際コンピュータシミュレーションジャーナル. 2 : 373–411 .
「 https://en.wikipedia.org/w/index.php?title=Lubachevsky–Stillinger_algorithm&oldid=1317529705」より取得