Integer linear system#

hsnf.integer_system.solve_integer_linear_system(A: numpy.ndarray[Any, numpy.dtype[numpy.int64]], b: numpy.ndarray[Any, numpy.dtype[numpy.int64]])[source]#

For given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\), solve integer linear system \(\mathbf{Ax} = \mathbf{b}\) in \(\mathbf{x} \in \mathbb{Z}^{n}\). Let the rank of \(\mathbf{A}\) as \(r\). General solutions are written as

\[\{ \mathbf{x}_{\mathrm{special}} + \sum_{i=0}^{r-1} a_{i} \cdot \mathrm{basis[i]} \mid a_{i} \in \mathbb{Z} \}.\]

If no solution exists, return None.

Parameters

  • A (array, (m, n)) – Integer coefficient matrix

  • b (array, (m, )) – Integer offsets

Returns

  • basis (array, (m - rank, n)) – basis[i, :] is a solution of \(\mathbf{Ax}=\mathbf{0}\)

  • x_special (array, (n, )) – Special solution \(\mathbf{x}_{\mathrm{special}}\)

hsnf.integer_system.solve_frobenius_congruent(A: numpy.ndarray[Any, numpy.dtype[numpy.int64]], b: Optional[numpy.ndarray[Any, numpy.dtype[numpy.int64]]] = None, denominator: int = 1000000)[source]#

For given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\), solve Frobenius congruent \(\mathbf{Ax} \equiv \mathbf{b} \, (\mathrm{mod}\, \mathbb{R}/\mathbb{Z})\) for \(\mathbf{x} \in \mathbb{R}^{n}\). Let the rank of \(\mathbf{A}\) as \(r\). General solutions are written as

\[\{ \mathbf{x}_{\mathrm{special}} + \sum_{i=0}^{r-1} a_{i} \cdot \mathrm{basis\_Z[i]} + \sum_{j=0}^{n-r-1} c_{j} \cdot \mathrm{basis\_R[j]} \mid a_{i} \in \mathbb{Z}, c_{j} \in \mathbb{R} \}.\]

If no solution exists, return None.

Parameters

  • A (array, (m, n)) – Integer coefficient matrix

  • b ((Optional) array, (m, )) – Integer offsets

  • denominator – (Optional) If specified, taking modulus as fraction with up to specified denominator

Returns

  • basis_Z (array, (rank, n)) – basis_Z[i, :] is a solution of \(\mathbf{Ax} \equiv \mathbf{0} \, (\mathrm{mod} \, \mathbb{Z})\)

  • basis_R (array, (n - rank, n)) – basis_R[i, :] is a solution of \(\mathbf{Ax} \equiv \mathbf{0} \, (\mathrm{mod}\, \mathbb{R}/\mathbb{Z})\)

  • x_special (array, (n, )) – (Return if b is specified) Special solution \(\mathbf{x}_{\mathrm{special}}\)

hsnf.integer_system.solve_modular_integer_linear_system(A: numpy.ndarray[Any, numpy.dtype[numpy.int64]], b: numpy.ndarray[Any, numpy.dtype[numpy.int64]], q: int)[source]#

For given \(\mathbf{A} \in \mathbb{Z}^{m \times n}\) and \(\mathbf{b} \in \mathbb{Z}^{m}\), solve modular integer linear system \(\mathbf{Ax} \equiv \mathbf{b} \, (\mathrm{mod} \, q)\) in \(\mathbf{x} \in \mathbb{Z}^{n}\). General solutions are written as

\[\{ \mathbf{x}_{\mathrm{special}} + \sum_{i=0}^{r-1} a_{i} \cdot \mathrm{basis[i]} \mid a_{i} \in \mathbb{Z} \}.\]

If no solution exists, return None.

Parameters

  • A (array, (m, n)) – Integer coefficient matrix

  • b (array, (m, )) – Integer offsets

  • q (int) – Modulo

Returns

  • basis (array, (r, n)) – basis[i, :] is a solution of \(\mathbf{Ax} \equiv \mathbf{0} \, (\mathrm{mod} \, q)\)

  • x_special (array, (n, )) – Special solution \(\mathbf{x}_{\mathrm{special}}\)