无需明确拼出矩阵分量即可求解线性方程组的算法

Question

我有一个线性函数(n 个输入 -> n 个输出)，并使用函数的特殊结构(一些类似 DP 的算法)，我可以在 O(n) 时间内评估输出，而不是 O(n^ 2)时间。现在，给定一些输出值，我需要找到对输出求值的输入。

我可以拼出矩阵分量(通过评估具有 n 个基本输入的线性函数)并使用一些算法，如 LU 分解，但这需要 O(n^3) 时间来计算。有没有更快的算法，利用线性函数的结构？

(由于线性函数不对称，无法使用共轭梯度法。)

我需要精确解，其中 n 很小(n=10~20)，但我需要在一秒钟内进行数十万次这种计算。

从代码设计的角度来看，如果算法不需要线性函数的转置会更好。 (虽然以更多的代码和更多的调试为代价，可以提供时间复杂度为O(n)的转置函数。)

Answer 1

你有没有考虑过GMRES ？您提到您正在寻找精确的解决方案，但是您可以相当快地获得机器精度误差。

I can evaluate the output in O(n) time, rather than O(n^2) time.

您可以使用线性运算符来利用这一点，例如 GMRES in scipy implementation , A 可以是 LinearOperator .线性运算符只是一个计算 Ax 的函数，这是您的“计算输出”步骤。

否则，由于缺少临时解决方案，我不熟悉可以使用线性运算符加速的任何确切方法，因此我需要更多地了解您的问题，例如您的矩阵是否带状？