El algoritmo de compresión de Lubachevsky-Stillinger (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, generalmente se lleva a cabo en una computadora.
Un proceso físico de compresión a menudo implica un límite duro que se contrae del contenedor, como un pistón que presiona contra las partículas. El LSA puede simular un escenario de este tipo. [2] Sin embargo, el LSA se introdujo originalmente en el entorno sin un límite duro [1] [3] donde las partículas virtuales se estaban "hinchando" o expandiendo en un volumen virtual finito fijo con condiciones de límite periódicas . Los tamaños absolutos de las partículas aumentaban, pero los tamaños relativos de partícula a partícula permanecían constantes. En general, el LSA puede manejar una compresión externa y una expansión interna de partículas, ambas ocurriendo simultáneamente y posiblemente, pero no necesariamente, combinadas con un límite duro. Además, el límite 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 vecinas inmóviles y atascadas y el límite duro, si lo hay. Estas partículas libres de movimiento no son un artefacto, ni una característica prediseñada o deseada del LSA, sino 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 "rattlers" para las partículas libres de movimiento, porque si uno sacude físicamente un grupo comprimido de partículas duras, los rattlers vibrarán.
En el modo "pre-bloqueado", cuando la densidad de la configuración es baja y las partículas son móviles, la compresión y expansión se pueden detener, si así se desea. Entonces, el LSA, en efecto, estaría simulando un flujo granular . Se pueden simular varias dinámicas de las colisiones instantáneas, como: con o sin una restitución completa, con o sin fricción tangencial. Se pueden tener en cuenta las diferencias en las masas de las partículas. También es fácil y a veces resulta útil "fluidizar" una configuración bloqueada, disminuyendo los tamaños de todas o algunas de las partículas. Otra posible extensión del LSA es reemplazar el potencial de fuerza de colisión dura (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 interacción de fuerza partícula-partícula continua 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 se pueda representar 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 atascamiento en un contenedor de tamaño no mensurable resultó 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 diferentes tamaños. [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 mientras la forma sea esférica, el LSA puede manejar conjuntos de partículas de decenas a cientos de miles en las computadoras personales estándar actuales (2011) . Solo se informó una experiencia muy limitada [9] en el uso del LSA en dimensiones superiores a 3.
El estado de bloqueo de partículas se logra mediante la simulación de un flujo granular . El flujo se representa como una simulación de evento discreto , siendo los eventos colisiones entre partículas o entre partículas y límites. Idealmente, los cálculos deberían haberse realizado con precisión infinita. Entonces, el bloqueo 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 ejecuciones entre colisiones de las partículas que no son de cascabel se vuelven más pequeñas que un umbral pequeño especificado explícita o implícitamente. Por ejemplo, es inútil continuar los cálculos cuando las ejecuciones entre colisiones son más pequeñas que el error de redondeo.
El LSA es eficiente en el sentido de que los eventos se procesan esencialmente de una manera impulsada por eventos , en lugar de hacerlo en función del tiempo. Esto significa que casi no se desperdician cálculos en calcular o mantener las posiciones y velocidades de las partículas entre las colisiones. Entre los algoritmos impulsados por eventos destinados a la misma tarea de simular flujo granular , como, por ejemplo, el algoritmo de DC Rapaport, [10] el LSA se distingue por una estructura de datos y un manejo de datos más simples.
Para cualquier partícula en cualquier etapa de los cálculos, el LSA mantiene el registro de sólo dos eventos: un evento comprometido antiguo, ya procesado, que comprende la marca de tiempo del evento comprometido , el estado de la partícula (incluida la posición y la velocidad) y, tal vez, el "socio" que podría ser otra partícula o identificación de límite, aquella con la que la partícula colisionó 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 los eventos antiguos comprometidos nunca debe superar el mínimo de los tiempos de los eventos nuevos no comprometidos.
La siguiente partícula que examinará el algoritmo tiene el mínimo actual de tiempos de eventos nuevos. Al examinar la partícula elegida, lo que anteriormente era el evento nuevo se declara como el anterior y se confirma, mientras que el próximo evento nuevo se programa, con su nueva marca de tiempo, nuevo estado y nuevo socio, si lo hay. 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 confirmados para tener mejor en cuenta 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 bloqueo siempre que esas tasas se mantengan comparables entre todas las partículas, excepto las serpientes de cascabel. (Las serpientes de cascabel experimentan tasas de colisión consistentemente bajas. Esta propiedad permite detectarlas). 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 de la aproximación 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 bloqueo.
La falla por atascamiento en el tiempo también puede ocurrir cuando se simula un flujo granular sin compresión o expansión de partículas. Este modo de falla fue reconocido por los profesionales de las 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). La falla no es específica solo del algoritmo LSA. Se han propuesto técnicas para evitar la falla. [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 avanzado 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 libres de los 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 sobre el de un multiprocesador , al ejecutar el mismo algoritmo Time Warp paralelo. Boris D. Lubachevsky notó que tal evaluación de aceleración 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 monoprocesador más rápida y, por lo tanto, tener una evaluación más justa de la aceleración paralela . Más tarde, también se propuso un algoritmo de simulación paralela, diferente del Time Warp, que, al ejecutarse en un monoprocesador, se reduce al LSA. [15]