El problema proviene directamente de las matemáticas computacionales y puede ser declarado de la siguiente manera:
Dada una matriz regular , encuentre efectivamente todos los vectores modo que , donde \ n {Mv} sea el componente máximo de vector en módulo
A continuación doy un algoritmo, pero es muy ineficiente, ya que tiene muchos más pasos que el número de puntos de la cuadrícula. Todavía es soportable para en mi caso, pero falla completamente para , no tengo mucho tiempo; Además, me gustaría trabajar también en dimensiones superiores.
Mi algoritmo actual se basa en lo siguiente (descargo de responsabilidad: contiene más matemáticas): Primero, calcule . Luego, observamos que . Esto significa que podemos calcular y luego probar todos los vectores ; hay exactamente de ellos. (Y aquí radica el problema: si y , obtengo iteraciones, que es un orden de magnitud mayor que la cantidad de puntos que creo que hay).
Respuestas:
Aquí hay otra forma de ver el problema: tiene una red generada por las columnas deM . Utilice el algoritmo Lenstra – Lenstra – Lovász (LLL) para obtener una base reducida de esta red. Si reemplaza por una nueva matriz formada por la salida de LLL, las columnas de seguirán generando la misma red, pero los vectores de base estarán más cerca de ser ortogonales entre sí, y las entradas de debería tener una magnitud menor.M M M−1
A partir de ahí, también ayudaría vincular cada componente de separado: es decir, puede vincular el componentev i |vi| por. (Por cierto, el enlace no es correcto; necesitamos usar la suma de los elementos en cada fila, no el máximo).∑dj=1|(M−1)ij| ∥v∥∞≤∥M−1∥
Para valores de hasta aproximadamente 30, el algoritmo LLL terminará prácticamente al instante. Asintóticamente, toma , por lo que se ralentizará duranted O(d6) d , pero al mismo tiempo, el número de puntos que necesitamos verificar crece exponencialmente en , por lo que el tiempo de ejecución de la LLL no es realmente El cuello de botella. Por otro lado, los ahorros en la cantidad de puntos que deben verificarse pueden ser enormes. Escribí un código GAP para generar una matriz aleatoria regular (estocástica) y comparar los límites en los componentes ded M v que obtenemos utilizando la base original, en comparación con la base reducida de LLL (Por cierto, no necesitamos suponer que la matriz es regular; hice esta restricción solo porque este fue el caso en su solicitud):
El siguiente resultado (basado en la semilla aleatoria predeterminada, con ) no es atípico:d=8
Editar : Este problema es un caso especial del problema general de enumerar puntos reticulares en politopos convexos, lo que resulta que es un problema bien estudiado, y hay algoritmos más eficientes que el descrito anteriormente. Vea este este documento para una encuesta.
fuente