El algoritmo de Lubachevsky-Stillinger ( LSA ) es un procedimiento computacional que simula el proceso de compresión mecánica de un conjunto de partículas sólidas .
La compresión mecánica suele ser realizada por la pared del recipiente donde se encuentran las partículas, por ejemplo, por un pistón que presiona sobre las partículas . LSA le permite modelar este proceso [1] .
En la formulación original, LSA no supuso un límite rígido: las partículas simuladas se expandieron mientras se encontraban en un volumen virtual fijo y finito con condiciones de límite periódicas [2] [3] . Los tamaños absolutos de las partículas aumentaron, pero sus tamaños relativos permanecieron sin cambios. LSA también puede simular la compresión externa con la expansión interna simultánea de partículas.
En el estado resultante, algunas partículas pueden retener la movilidad dentro de los límites de sus vecinos y las paredes del recipiente. La aparición de tales partículas fue inesperada para los autores del algoritmo: Frank Stillinger propuso el nombre "ratler" (traqueteo) para tal partícula, ya que los ratlers "retumbarán" si sacudes una matriz comprimida de partículas sólidas.
La contracción externa y la expansión interna de las partículas se pueden detener en el estado precomprimido cuando la densidad de llenado de partículas es baja y las partículas son móviles. Operando en este modo, el LSA simulará el flujo de partículas como un medio granular . LSA también puede modelar varios mecanismos de colisión de partículas o tener en cuenta su masa.
El uso de LSA para partículas esféricas o en contenedores con tamaños "incómodos" ha demostrado ser efectivo para reproducir y demostrar alteraciones microestructurales asociadas con defectos de cristal [4] o frustración geométrica [5] [6] . Inicialmente, LSA estaba destinado a resolver el problema del empaquetamiento de bolas [7] . LSA puede manejar conjuntos de decenas y cientos de miles de bolas en computadoras personales, sin embargo, la desviación de la forma esférica (o redonda en el plano), como el uso de elipsoides (elipses en el plano), ralentiza significativamente los cálculos [ 8] .
Para la compresión se utiliza el modelado de eventos discretos de un medio granular, donde los eventos son las colisiones de partículas entre sí y con paredes sólidas, si las hay. Los cálculos se detienen cuando los desplazamientos entre colisiones de todas las partículas, excepto ratlers, se vuelven menores que un pequeño umbral especificado explícita o implícitamente, que puede determinarse, por ejemplo, mediante errores de redondeo.
El LSA es computacionalmente eficiente, en el sentido de que su progreso está determinado por eventos (colisiones) más que por la cantidad de tiempo transcurrido entre ellos. En este sentido, las características intermedias de las partículas en el período entre colisiones solares, por regla general, no se calculan. Comparado con otros algoritmos con un modelo de cálculo similar, como el algoritmo de D. Rapaport [9] , LSA destaca por su sencillez en la estructuración y procesamiento de datos.
Para cualquier partícula y en cualquier etapa del cálculo, LSA mantiene un registro de solo dos eventos: un evento antiguo que ya ha sido procesado y uno nuevo que está programado para su procesamiento. Un registro de evento consta de la marca de tiempo del evento, el estado de la partícula inmediatamente después del evento (incluida la posición y la velocidad de la partícula) y una indicación del "compañero" de la partícula en este evento (otra partícula o pared del recipiente). ), Si alguna. Las etiquetas máximas entre los eventos manejados no deben exceder las etiquetas mínimas de los eventos no manejados.
La siguiente partícula que se procesará es la partícula con la marca de tiempo más pequeña entre los eventos sin procesar. El evento asociado a esta partícula se declara procesado y, al mismo tiempo, se programa el siguiente evento para él con una nueva marca de tiempo, un nuevo estado y un nuevo socio, si lo hubiera. Al mismo tiempo, los eventos brutos esperados para algunos vecinos más cercanos de esta partícula pueden cambiar.
A medida que avanzan los cálculos, las tasas de colisión de partículas tienden a aumentar. Sin embargo, el sistema se acerca con éxito al estado comprimido si las frecuencias de colisión de diferentes partículas, que no son ratlers, resultan ser comparables. Las serpientes de cascabel, a su vez, mantienen una tasa de colisión constantemente baja, lo que les permite ser detectadas.
Al mismo tiempo, es posible que las frecuencias de colisión de un pequeño número de partículas, o incluso de una partícula, excedan significativamente la frecuencia de colisión del resto de las partículas, lo que, a su vez, puede ralentizar significativamente el algoritmo. Este estado en la simulación de medios granulares suele denominarse "colapso inelástico" porque su causa típica es el bajo coeficiente de restitución de las partículas simuladas [10] . Esta situación no es exclusiva de LSA, y se han desarrollado una serie de métodos para tratarla [11] .
LSA surgió como un subproducto de un intento de establecer una medida adecuada de la aceleración la simulación paralela . Inicialmente, se propuso utilizar el algoritmo paralelo Time Warp [12] : la aceleración se definió como la relación del tiempo de ejecución en sistemas multiprocesador y monoprocesador. Boris Dmitrievich Lyubachevsky señaló que tal estimación puede estar sobreestimada, ya que la ejecución de una tarea en un procesador usando un programa paralelo puede no ser óptima para resolver la tarea. LSA se creó como un intento de encontrar un método de simulación de monoprocesador más rápido y, por lo tanto, mejorar la calidad de la estimación de aceleración paralela. Posteriormente, también se propuso un algoritmo de simulación en paralelo que, cuando se ejecuta en un sistema de un solo procesador, es idéntico a LSA [13] .