optimization - 整数上的线性代数包

Question

我最近遇到了以下问题。给定一个包含整数条目的向量列表(这里我的意思是元组)，是否有一个包(语言不是太大的问题，越快越好，所以我猜是 C)可以非常快速地确定另一个整数向量何时在原始列表的跨度？我需要对整数进行此算术运算(无除法)。我敢肯定有一个，但想绕过冗长的文献回顾。

Answer 1

您可以使用 mathnf PARI中的函数计算 Hermite normal form包含您的跨越向量作为列的矩阵。 HNF 矩阵的列跨越相同的格，检查向量是否在该格中是很简单的。还有更多的库能够计算 HNF——谷歌是你的 friend 。