Cálculo exacto de la base del espacio nulo de una matriz entera

Question

Hola a todos,

Dejemos que $\mathbf{A} \in \mathbb{Z}^{M \times N}$ . Supongamos que $\mathbf{A} \cdot \vec{x} = \vec{0}$ , donde $\vec{x} \in \mathbb{N}^{N \times 1}$ . ¿Alguien sabe de un programa en C/C++/Java que pueda calcular exactamente el(los) vector(es) base del espacio nulo?

Answer 1

La pregunta parece referirse a los programas que pueden calcular exactamente el espacio nulo de una matriz entera. (Aunque parece que existe la restricción de que todas las entradas del vector solución sean positivo que voy a ignorar). El mejor software que podría utilizar podría depender del tamaño de sus matrices, que es una función de (1) los parámetros $M$ , $N$ (2) el número de bits de las entradas y (3) la escasez de la matriz.

• IML (Biblioteca de matrices enteras) -- esta es una biblioteca de C libre, pero lo que hace es calcular el racional núcleo de un sistema definido sobre los enteros, por lo que no es directamente útil para su problema. De todos modos, en mis benchmarks, esta es la biblioteca más rápida disponible para calcular el núcleo racional si tu matriz es grande (tanto $M$ y $N$ ), denso, y las entradas también son grandes. Cuando los tamaños de las entradas llegan a varios cientos de bits o más, IML me pareció en 2007 la biblioteca más rápida con diferencia (superando fácilmente a Mathematica, Magma, NTL, etc.). IML se utiliza como parte de Sage y se utiliza para la función del núcleo. Ponerse en marcha con IML de forma autónoma puede ser difícil (aunque yo contribuí con código hace unos años para hacerlo más fácil), pero si sólo quieres una biblioteca para enlazar con un programa C existente, definitivamente querrás mirar IML.

• PARI -- esta calculadora gratuita (que también se puede utilizar como biblioteca de C) es extremadamente buena para calcular núcleos de matrices pequeñas, por ejemplo, cuando las entradas no son demasiado grandes y el número de filas y columnas tampoco es demasiado grande (digamos, menos de 100). Está optimizado para este caso pequeño, ya que es lo que aparece en los cálculos de los grupos de clase, entre otras cosas. El comando a utilizar es matkerint, por ejemplo, "matkerint([1,2,3;4,5,6;7,8,9])".

• SAGE -- este software libre utiliza alguna combinación de IML, PARI, Linbox, NTL y un montón de código nuevo para calcular núcleos de matrices de enteros. En algunos casos (por ejemplo, matrices casi cuadradas) es muy bueno, y podría ser bueno en muchos más casos pero me dio pereza y no implementé algoritmos rápidos para todas las formas de matrices. Escribe "A = matrix(ZZ,3,3,[1..9])" para hacer una matriz entera de ejemplo; entonces "A.kernel()" encontrará el núcleo sobre ZZ (por defecto, al contrario de lo que afirma otra respuesta en esta página). Si escribes "A._k[pulsa la tecla de tabulación]" verás que puedes llamar directamente a otras dos rutinas para calcular núcleos, una de ellas con PARI, y la otra con $p$ -algoritmo de la adicción. Entre bastidores, realmente la forma normal de Hermite de la matriz se está calculando utilizando el algoritmo descrito aquí . El algoritmo HNF de Sage hace un uso fundamental de IML de varias maneras entre bastidores.

• Magma -- no es libre y es de código cerrado, pero tiene un algoritmo de forma normal de Hermite ajustado rápidamente, presumiblemente similar al de Sage, que para ciertos (no todos) rangos de entradas es el mejor disponible.

• Mathematica -- en mis benchmarks (de 2007), cuando las matrices se hacen muy grandes esto se vuelve totalmente inútil comparado con Magma o Sage, pero está bien para matrices pequeñas. Observaciones similares se aplican a Maple, al menos desde 2007.

Aquí hay un ejemplo potencialmente útil en Sage, que ilustra algunos de los cálculos discutidos aquí y en otros lugares, y explica cómo trabajar con algunas matrices y módulos en Sage:

sage: A = random_matrix(ZZ,5,2); B = random_matrix(ZZ,5,2)
sage: A.kernel()
Free module of degree 5 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1 60  0  1 30]
[ 0 66  0  1 33]
[ 0  0  1  0  0]
sage: A.kernel().intersection(B.kernel())
Free module of degree 5 and rank 1 over Integer Ring
Echelon basis matrix:
[  19 -378  -93   -4 -189]
sage: VA = A.change_ring(QQ).kernel(); VB = B.change_ring(QQ).kernel()
sage: W = VA.intersection(VB); W
Vector space of degree 5 and dimension 1 over Rational Field
Basis matrix:
[      1 -378/19  -93/19   -4/19 -189/19]
sage: W.intersection(ZZ^5)
Free module of degree 5 and rank 1 over Integer Ring
Echelon basis matrix:
[  19 -378  -93   -4 -189]

Answer 2

Las palabras mágicas son "forma normal de Smith"

Answer 3

Yo recomendaría utilizar la NTL (Number Theory Library). Su algoritmo LLL permite calcular el núcleo de una matriz sobre los enteros, además la base encontrada suele ser "corta" (en el sentido de que la longitud de los vectores base es corta).