Genera algorítmicamente todos los puntos de la cuadrícula dentro de un hipercubo

8

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óduloMETRORre×revZreMETROv1METROv

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 re=5 5 en mi caso, pero falla completamente para re=6 6 , 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 METRO-1 . Luego, observamos que vM1MvM1 . Esto significa que podemos calcular L=floorM1 y luego probar todos los vectores v{L,L+1,,L1,L}d ; hay exactamente (2L+1)d de ellos. (Y aquí radica el problema: si d=6 y L=18 , obtengo 2.5E9 iteraciones, que es un orden de magnitud mayor que la cantidad de puntos que creo que hay).

yo'
fuente
1
¿Ha considerado formular su problema como un programa lineal entero y luego contar soluciones? Creo que hay métodos disponibles en los solucionadores de IP (por ejemplo, CPLEX) para hacer esto, pero no sé qué tan rápido son en la práctica. Un método para hacerlo se conoce como Algoritmo de Barvinok.
Cornelius Brand
@ C.Brand Gracias, lo investigaré (sin embargo, han pasado años desde la última vez que vi un LP / IP). Por casualidad, ¿tienes una idea de si esto está presente en SageMath?
yo '
En cuanto a sus preocupaciones, la formulación original del problema ya es (casi) un programa entero; lo único que tendrá que cuidar es el uso de (no lineal) -norm. Pero no tengo idea si un algoritmo para contar soluciones IP está disponible en SageMath.
Marca Cornelius

Respuestas:

3

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.MMM1

A partir de ahí, también ayudaría vincular cada componente de separado: es decir, puede vincular el componentevi|vi|por. (Por cierto, el enlace no es correcto; necesitamos usar la suma de los elementos en cada fila, no el máximo).j=1d|(M1)ij|vM1

Para valores de hasta aproximadamente 30, el algoritmo LLL terminará prácticamente al instante. Asintóticamente, toma , por lo que se ralentizará durantedO(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 dedMv 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):

d: = 8;
M: = IdentityMat (d);
para i en [1..d] do
  para j en [1..d] do
    M [i] [j]: = Aleatorio ([- 10 ^ 8..10 ^ 8]);
  sobredosis;
  M [i]: = M [i] / Suma (M [i]);
sobredosis;
L: = LLLReducedBasis (M) .basis;
MM: = M ^ -1 * 1.0;
LL: = L ^ -1 * 1.0;
para i en [1..d] do
  para j en [1..d] do
    MM [i] [j]: = MM [i] [j] * SignFloat (MM [i] [j]);
    LL [i] [j]: = LL [i] [j] * SignFloat (LL [i] [j]);
  sobredosis;
sobredosis;

Imprimir ("Límites para la base original:");
unos: = [1..d] * 0 + 1;
v: = MM * unos;
para i en [1..d] do
  v [i]: = Int (Piso (v [i]));
  Imprimir (v [i]);
  Impresión(" ");
sobredosis;
Imprimir ("\ n (");
Imprimir (Producto (v * 2 + 1));
Imprimir ("puntos para verificar) \ n");

Imprimir ("Límites para LLL:");
v: = LL * unos;
para i en [1..d] do
  v [i]: = Int (Piso (v [i]));
  Imprimir (v [i]);
  Impresión(" ");
sobredosis;
Imprimir ("\ n (");
Imprimir (Producto (v * 2 + 1));
Imprimir ("puntos para verificar) \ n");

El siguiente resultado (basado en la semilla aleatoria predeterminada, con ) no es atípico:d=8

Límites para la base original: 9 23 24 4 23 16 23 4 
(258370076349 puntos para verificar)
Límites para LLL: 3 3 2 2 3 4 2 3 
(2701125 puntos para verificar)

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.

Brent Kerby
fuente
Pensé en obtener una buena base de la cuadrícula primero, pero no estoy seguro de cuán eficiente es en grandes dimensiones. (Nota: El problema actualmente no está interesante para mí, ya hemos conseguido que alrededor de ella por completo, pero voy a tratar de mantener un ojo sobre esta cuestión sigue.)
yo'
Agregué algo más a mi respuesta, con información sobre la eficiencia de LLL, así como código de ejemplo y salida.
Brent Kerby