我计划使用LUP-decomposition仅使用一个线程以整数形式求解标准形式Ax = b的 SLE。
A是一个大小约为 n 3 × 2n 3的矩阵，n ≈ 100（虽然越多越好）。矩阵非常稀疏 - 每列只有 4 个非零条目，它们都是 ±1，每列最多有 n 个非零条目。b也是一个只有 4 个条目等于 ±1 的列。
所以，我可以得到一个单一的解决方案，然后我可以将来自A的内核的向量的任何线性组合（带整数系数）添加到它以获得另一个解决方案（我也知道该内核的基础很容易从矩阵中读取）ü )。我想找到一个最大 c⋅n 非零条目的解决方案。我知道通常不暗示这种解决方案的存在（对于固定的系数 c），但就我而言，我认为应该有一个（而不仅仅是一个）。问题是：我如何找到它？
PS，如果有人愿意为 LUP 分解 + 求解部分的运行时间提供一些可靠的估计，或者还对L、U、L\b（Ly = b的解决方案，matlab 风格的解决方案）和 mb 甚至LU\b的密度估计-我也会非常感谢。或者，任何有关该主题的文献也会有所帮助。