您可能会查找“完全无分数分解”方法。论文“具有核提取的奇异系统的广义无分数 LU 分解”包含伪代码。

我们有线性系统$\rm A x = b$， 在哪里$\mathrm A \in \mathbb Z^{n \times n}$和$\mathrm b \in \mathbb Z^n$. 我们希望找到合理的解决方案$\mathrm x \in \mathbb Q^n$. 计算矩阵的史密斯范式$\rm A$在MATLAB中：

[U, V, S] = smithForm(A) 

我们得到单模矩阵$\rm U$和$\rm V$（即具有整数逆的整数矩阵）和对角矩阵$\rm S = U A V$. 因此，$\rm A x = b$可以改写为$\rm S V^{-1} x = U b$. 让$\rm y := V^{-1} x$. 然后我们得到线性系统$\rm S y = U b$，这很容易解决，因为$\rm S$是对角线。由于两者$\rm S$和$\rm U b$是整数值，解决方案将是一个有理向量。最后，我们计算$\rm x = V y$，这也是一个有理向量，因为$\rm V$也是整数值。

该问题可以使用 Matlab 符号工具箱来解决：

N = 100; %Dimensionality
A = randi(1000, [N, N]);
assert(rank(A) == N);
B = randi(1000, [N, 1]);

As = sym(A);
Bs = sym(B);

tic
xs = linsolve(As, Bs); % is a rational number
toc

disp(xs);

xs表示为有理数的向量。linsolvei5 上的调用运行时间约为 9 秒。