i具有线性函数（n输入 -> n输出），并使用该函数的特殊结构（一些DP类似算法），我可以评估O（n）中的输出时间，而不是o（n^2）时间。现在，给定一些输出值，我需要找到评估输出的输入。
i可以阐明矩阵组件（通过使用n个基本输入评估线性函数）并使用一些算法（例如LU分解），但这需要O（n^3）时间进行计算。是否有更快的算法，利用线性函数的结构？
（由于线性函数不是对称的，因此无法使用共轭梯度方法。）
我需要精确的解决方案，其中n很小（n = 10〜20），但是我需要在一秒钟内进行数十万次计算。
从代码设计的角度来看，如果算法不需要线性函数的转换，那会更好。（尽管以更多代码和更多调试为代价，但可以提供o（n）时间复杂性的转置功能。）
您是否考虑过GMRE？您提到您正在寻找确切的解决方案，但是您可以快速获得机器精确错误。
我可以在O（n）时间中评估输出，而不是O（n^2）时间。
您可以使用线性操作员来利用此优势，例如，对于Scipy实现的GMRE，A可以是线性操纵器。线性操作员只是评估Ax的函数，这是您的"评估输出"步骤。
否则，除了临时解决方案之外，我不熟悉任何可以加速线性操作员加速的方法，所以我需要更多地了解您的问题，例如您的矩阵是频段的吗？