我有一个线性函数（n输入 - > n输出），并使用函数的特殊结构（一些类似DP的算法），我可以在O（n）时间内评估输出，而不是O（n ^ 2）时间。现在，给定一些输出值，我需要找到评估输出的输入。
我可以拼出矩阵组件（通过用n个基础输入评估线性函数）并使用一些算法，如LU分解，但这需要花费O（n ^ 3）时间来计算。是否有更快的算法，利用线性函数的结构？
（由于线性函数不对称，因此无法使用共轭梯度法。）
我需要精确的解决方案，其中n很小（n = 10~20），但我需要在一秒钟内进行数十万次这种计算。
从代码设计的角度来看，如果算法不需要转置线性函数会更好。 （虽然以更多代码和更多调试为代价，但可以提供具有O（n）时间复杂度的转置函数。）
你考虑过GMRES吗？您提到您正在寻找精确的解决方案，但是您可以合理地快速获得机器精度误差。
我可以在O（n）时间内评估输出，而不是O（n ^ 2）时间。
您可以使用线性运算符来利用这一点，例如使用GMRES in scipy implementation，A可以是LinearOperator。线性运算符只是一个评估Ax的函数，这是你的“评估输出”步骤。
否则，如果没有临时解决方案，我不熟悉可以使用线性运算符加速的任何精确方法，因此我需要了解更多关于您的问题的信息，例如您的矩阵被绑定了吗？