Gere algoritmicamente todos os pontos da grade dentro de um hipercubo

$\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty}$ O problema vem diretamente da matemática computacional e pode ser indicado da seguinte forma:

Dada uma matriz regular , encontre efetivamente todos os vetores modo que \ n {Mv} \ leq1 , em que \ n {Mv} seja o componente máximo do vetor em módulo.$M\in\R^{d\times d}$$v\in\Z^d$$\n{Mv}\leq1$$\n{Mv}$

Dou um algoritmo abaixo, mas é muito ineficiente, pois possui muito mais etapas do que o número de pontos da grade. Ainda é suportável para $d=5$ no meu caso, mas falha completamente para $d=6$ , não tenho muito tempo; além disso, eu gostaria de fazer algum trabalho em dimensões mais altas também.

Meu algoritmo atual é baseado no seguinte (aviso: contém mais contas matemáticas): Primeiro, calcule $\n{M^{-1}}$ . Então, observamos que $\n{v}\leq\n{M^{-1}}\n{Mv}\leq\n{M^{-1}}$ . Isso significa que podemos calcular $L=\operatorname{floor} \n{M^{-1}}$ e tentar todos os vetores $v\in\lbrace-L,-L+1,\dots,L-1,L\}^d$ ; há exatamente $(2L+1)^d$ deles. (E aqui está o problema: se $d=6$ e $L=18$ , eu recebo $2.5{\rm\small E}9$ iterações, que são ordens de magnitude maiores que o número de pontos que acho que existem.)

Aqui está uma outra maneira de olhar para o problema: Você tem uma rede gerado pelas colunas de . Use o algoritmo Lenstra-Lenstra-Lovász (LLL) para obter uma base reduzida dessa estrutura. Se você substituir por uma nova matriz formada pela saída de LLL, as colunas de ainda gerarão a mesma rede, mas os vetores de base estarão mais próximos de serem ortogonais entre si e as entradas de deve ter magnitude menor.$M$$M$$M$$M^{-1}$

De lá, também ajudaria a obrigados cada componente do separadamente: ou seja, você pode obrigado a th componentepor. (A propósito, o limite não está correto; precisamos usar a soma dos elementos em cada linha, não o máximo.)$v$$i$$|v_i|$$\sum_{j=1}^d |(M^{-1})_{ij}|$$\|v\|_\infty \leq \|M^{-1}\|$

Para valores de até cerca de 30, o algoritmo LLL terminará praticamente instantaneamente. Assintoticamente, é preciso , então ele diminui a velocidade para muito grande , mas, ao mesmo tempo, o número de pontos que precisamos verificar cresce exponencialmente em , portanto o tempo de execução da LLL não é realmente o gargalo. Por outro lado, a economia no número de pontos que precisam ser verificados pode ser enorme. Escrevi um código GAP para gerar uma matriz regular aleatória (estocástica) e comparar os limites nos componentes de$d$$O(d^6)$$d$$d$$M$$v$ que obtemos usando a base original, em comparação com a base reduzida de LLL (a propósito, não precisamos assumir que a matriz é regular; eu fiz essa restrição apenas porque esse era o caso em sua aplicação):

d: = 8;
M: = IdentityMat (d);
para i em [1..d] faça
  para j em [1..d] faça
    M [i] [j]: = Aleatório ([- 10 ^ 8..10 ^ 8]);
  od;
  M [i]: = M [i] / Soma (M [i]);
od;
L: = LLLReducedBasis (M) .base;
MM: = M ^ -1 * 1,0;
LL = L ^ -1 * 1,0;
para i em [1..d] faça
  para j em [1..d] faça
    MM [i] [j]: = MM [i] [j] * SignFloat (MM [i] [j]);
    LL [i] [j]: = LL [i] [j] * SignFloat (LL [i] [j]);
  od;
od;

Imprimir ("Limites para a base original:");
ones: = [1..d] * 0 + 1;
v: = MM * uns;
para i em [1..d] faça
  v [i]: = Int (Piso (v [i]));
  Imprimir (v [i]);
  Impressão(" ");
od;
Imprimir ("\ n ("));
Imprimir (Produto (v * 2 + 1));
Imprimir ("aponta para verificar) \ n");

Print ("Limites para LLL:");
v: = LL * uns;
para i em [1..d] faça
  v [i]: = Int (Piso (v [i]));
  Imprimir (v [i]);
  Impressão(" ");
od;
Imprimir ("\ n ("));
Imprimir (Produto (v * 2 + 1));
Imprimir ("aponta para verificar) \ n");

A saída a seguir (com base na semente aleatória padrão, com ) não é atípica:$d=8$

Limites para a base original: 9 23 24 4 23 16 23 4 
(258370076349 pontos para verificar)
Limites para a base de LLL: 3 3 2 2 3 4 2 3 
(2701125 pontos para verificar)

Edit : Este problema é um caso especial do problema geral de enumerar pontos de treliça em politopos convexos, o que resulta ser um problema bem estudado, e existem algoritmos mais eficientes do que o descrito acima. Veja este artigo para uma pesquisa.