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

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

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

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

「事前ジャム」モードでは、構成の密度が低く、粒子が移動可能な場合、必要に応じて圧縮と膨張を停止できます。その場合、LSA は事実上、粒状の流れをシミュレートすることになります。瞬間衝突のさまざまなダイナミクスをシミュレートできます。たとえば、完全な復元の有無、接線摩擦の有無などです。粒子の質量の違いを考慮することができます。また、すべての粒子または一部の粒子のサイズを小さくすることで、ジャム構成を「流動化」することも簡単で、場合によっては便利です。LSA のもう 1 つの可能な拡張は、ハード衝突力 ポテンシャル(粒子の外側ではゼロ、粒子の内側では無限大) を区分的に一定の力 ポテンシャルに置き換えることです。このように変更された LSA は、連続した短距離の粒子間力相互作用を伴う分子動力学を近似的にシミュレートします。各粒子の衝突間の動きを簡単な 1 ステップの計算で表すことができる限り、重力などの外部力場も導入できます。

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

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

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

LSAは、イベントが時間駆動型ではなく、本質的にイベント駆動型で処理されるという意味で効率的です。つまり、衝突間の粒子の位置と速度を計算したり維持したりするために無駄な計算がほとんど行われません。たとえばDCラパポートのアルゴリズム^{[10]など、}粒子の流れをシミュレートするという同じタスクを目的としたイベント駆動型アルゴリズムの中で、LSAはより単純なデータ構造とデータ処理によって区別されます。

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

アルゴリズムによって検査される次の粒子には、新しいイベント時間の現在の最小値があります。選択された粒子を検査すると、以前の新しいイベントは古いイベントとして宣言され、コミットされますが、次の新しいイベントは、新しいタイムスタンプ、新しい状態、および新しいパートナー (存在する場合) とともにスケジュールされます。粒子の次の新しいイベントが設定されると、隣接する粒子の一部は、新しい情報をより適切に考慮するために、コミットされていない新しいイベントを更新する場合があります。

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

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

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

• LSA の動作。Alexander Donev によるアニメーション集
• 任意の次元での LSA バージョンのソース C++ コード
• LSAを用いて研究された粒状パックの体積変動分布
• 任意の形状の粒子に対して一般化されたLSA
• LSA は、充填された粒状材料におけるマイクロスケールの破損の代表的な体積を生成するために使用されます。