El algoritmo Lubachevsky-Stillinger (compresión) (algoritmo LS, LSA o protocolo LS) es un procedimiento numérico sugerido por FH Stillinger y Boris D. Lubachevsky que simula o imita un proceso físico de compresión de un conjunto de partículas duras. [1] Como el LSA puede necesitar miles de operaciones aritméticas incluso para unas pocas partículas, normalmente se lleva a cabo en una computadora.
Un proceso físico de compresión a menudo implica una contracción dura del contenedor, como un pistón que presiona contra las partículas. La LSA es capaz de simular tal escenario. [2] Sin embargo, el LSA se introdujo originalmente en un entorno sin un límite estricto [1] [3] donde las partículas virtuales se "hinchaban" o expandían en un volumen virtual finito fijo con condiciones de límite periódicas . Los tamaños absolutos de las partículas estaban aumentando, pero los tamaños relativos entre partículas permanecían constantes. En general, el LSA puede manejar una compresión externa y una expansión interna de partículas, ambas ocurren simultáneamente y posiblemente, pero no necesariamente, combinadas con un límite estricto. Además, la frontera puede ser móvil.
En un estado final, comprimido o "atascado", algunas partículas no están atascadas, sino que pueden moverse dentro de "jaulas" formadas por sus vecinos inmóviles y atascados y el límite duro, si lo hay. Estas partículas que se mueven libremente no son un artefacto, ni una característica prediseñada o objetivo del LSA, sino más bien un fenómeno real. La simulación reveló este fenómeno, algo inesperado para los autores del LSA. Frank H. Stillinger acuñó el término "cascabeles" para las partículas que se mueven libremente, porque si uno sacude físicamente un montón comprimido de partículas duras, los cascabeles vibrarán.
En el modo "preatascado", cuando la densidad de la configuración es baja y cuando las partículas son móviles, se puede detener la compresión y expansión, si así se desea. Entonces el LSA, en efecto, estaría simulando un flujo granular . Se pueden simular diversas dinámicas de colisiones instantáneas como: con o sin restitución total, con o sin fricción tangencial. Se pueden tener en cuenta las diferencias de masas de las partículas. También es fácil y a veces resulta útil "fluidizar" una configuración atascada, disminuyendo el tamaño de todas o algunas de las partículas. Otra posible extensión del LSA es reemplazar el potencial de fuerza de colisión fuerte (cero fuera de la partícula, infinito en o dentro) con un potencial de fuerza constante por partes . El LSA así modificado simularía aproximadamente la dinámica molecular con una interacción continua de fuerza entre partículas de corto alcance. También se pueden introducir campos de fuerza externos , como la gravitación , siempre que el movimiento entre colisiones de cada partícula pueda representarse mediante un simple cálculo de un solo paso.
El uso de LSA para partículas esféricas de diferentes tamaños y/o para atascos en un recipiente de tamaño no conmensurable demostró ser una técnica útil para generar y estudiar microestructuras formadas en condiciones de un defecto cristalográfico [4] o una frustración geométrica [5]. [6] Cabe agregar que el protocolo LS original fue diseñado principalmente para esferas del mismo o diferente tamaño. [7]
Cualquier desviación de la forma esférica (o circular en dos dimensiones), incluso la más simple, cuando las esferas se reemplazan con elipsoides (o elipses en dos dimensiones), [8] hace que el LSA modificado se ralentice sustancialmente. Pero siempre que la forma sea esférica, el LSA es capaz de manejar conjuntos de partículas de decenas a cientos de miles en las computadoras personales estándar actuales (2011) . Sólo se informó una experiencia muy limitada [9] en el uso del LSA en dimensiones superiores a 3.
El estado de atasco de partículas se logra simulando un flujo granular . El flujo se representa como una simulación de eventos discretos , siendo los eventos colisiones entre partículas o entre partículas. Idealmente, los cálculos deberían haberse realizado con precisión infinita. Entonces la interferencia se habría producido hasta el infinito . En la práctica, la precisión es finita al igual que la resolución disponible para representar los números reales en la memoria de la computadora , por ejemplo, una resolución de doble precisión . Los cálculos reales se detienen cuando las carreras entre colisiones de las partículas que no son cascabel se vuelven más pequeñas que un pequeño umbral especificado explícita o implícitamente. Por ejemplo, es inútil continuar los cálculos cuando las carreras entre colisiones son menores que el error de redondeo.
El LSA es eficiente en el sentido de que los eventos se procesan esencialmente en función de los eventos , en lugar de hacerlo en función del tiempo. Esto significa que casi no se desperdicia ningún cálculo en calcular o mantener las posiciones y velocidades de las partículas entre las colisiones. Entre los algoritmos controlados por eventos destinados a la misma tarea de simular un flujo granular , como, por ejemplo, el algoritmo de DC Rapaport, [10] el LSA se distingue por una estructura y un manejo de datos más simples.
Para cualquier partícula en cualquier etapa de los cálculos, el LSA mantiene un registro de solo dos eventos: un evento comprometido antiguo, ya procesado, que comprende la marca de tiempo del evento comprometido , el estado de la partícula (incluidas la posición y la velocidad) y, tal vez, el "compañero". ", que podría ser otra partícula o identificación de límite, aquella con la que la partícula chocó en el pasado, y un nuevo evento propuesto para un procesamiento futuro con un conjunto similar de parámetros. El nuevo evento no está comprometido. El máximo de los tiempos de eventos antiguos comprometidos nunca debe exceder el mínimo de los tiempos de eventos nuevos no comprometidos.
La siguiente partícula que el algoritmo examinará tiene el mínimo actual de tiempos de nuevos eventos. Al examinar la partícula elegida, lo que anteriormente era el nuevo evento se declara como el antiguo y está comprometido, mientras que se programa el próximo nuevo evento, con su nueva marca de tiempo, nuevo estado y nuevo socio, si lo hubiera. A medida que se establece el próximo evento nuevo para una partícula, algunas de las partículas vecinas pueden actualizar sus nuevos eventos no comprometidos para explicar mejor la nueva información.
A medida que avanzan los cálculos del LSA, las tasas de colisión de partículas pueden aumentar, y normalmente lo hacen. Aún así, el LSA se acerca con éxito al estado de interferencia siempre que esas velocidades sigan siendo comparables entre todas las partículas, excepto las cascabeles. (Los cascabeles experimentan tasas de colisión consistentemente bajas. Esta propiedad permite detectar cascabeles). Sin embargo, es posible que unas pocas partículas, incluso una sola partícula, experimenten una tasa de colisión muy alta a lo largo del acercamiento a un cierto tiempo simulado. La tasa aumentará sin límite en proporción a las tasas de colisiones en el resto del conjunto de partículas. Si esto sucede, entonces la simulación se atascará en el tiempo y no podrá avanzar hacia el estado de interferencia.
La falla estancada en el tiempo también puede ocurrir al simular un flujo granular sin compresión o expansión de partículas. Este modo de falla fue reconocido por los practicantes de simulaciones de flujo granular como un "colapso inelástico" [11] porque a menudo ocurre en tales simulaciones cuando el coeficiente de restitución en las colisiones es bajo (es decir, inelástico). El error no es específico únicamente del algoritmo LSA. Se han propuesto técnicas para evitar el fallo. [12]
El LSA fue un subproducto de un intento de encontrar una medida justa de aceleración en simulaciones paralelas . El algoritmo de simulación paralela Time Warp de David Jefferson fue propuesto como un método para simular interacciones espaciales asincrónicas de unidades de combate en modelos de combate en una computadora paralela . [13] Los modelos de partículas en colisión [14] ofrecieron tareas de simulación similares con interacciones espaciales de partículas, pero sin detalles que no son esenciales para exponer las técnicas de simulación. La aceleración se presentó como la relación entre el tiempo de ejecución en un monoprocesador y en un multiprocesador , al ejecutar el mismo algoritmo Time Warp en paralelo. Boris D. Lubachevsky notó que tal evaluación de la velocidad podría ser defectuosa porque ejecutar un algoritmo paralelo para una tarea en un monoprocesador no es necesariamente la forma más rápida de realizar la tarea en dicha máquina. El LSA se creó en un intento de producir una simulación de uniprocesador más rápida y, por tanto, tener una evaluación más justa de la aceleración en paralelo . Posteriormente también se propuso un algoritmo de simulación paralelo, diferente al Time Warp, que, cuando se ejecuta en un monoprocesador, se reduce al LSA. [15]