无需明确拼出矩阵分量即可求解线性方程组的算法
Algorithm to solve linear equation system without explicitly spelling out the matrix components
我有一个线性函数（n 个输入 -> n 个输出），并使用函数的特殊结构（一些类似 DP 的算法），我可以在 O(n) 时间内评估输出，而不是 O( n^2) 次。现在，给定一些输出值，我需要找到对输出求值的输入。
我可以拼出矩阵分量（通过评估具有 n 个基本输入的线性函数）并使用一些算法，如 LU 分解，但这需要 O(n^3) 的时间来计算。是否有更快的算法，利用线性函数的结构？
（由于线性函数不对称，无法使用共轭梯度法。）
我需要精确解，其中n很小（n=10~20），但我需要在一秒钟内进行数十万次这种计算。
从代码设计的角度来看，如果算法不需要线性函数的转置会更好。 （虽然以更多的代码和更多的调试为代价，但可以提供时间复杂度为O(n)的转置函数。）
你考虑过GMRES吗？您提到您正在寻找精确的解决方案，但是您可以相当快地获得机器精度误差。
I can evaluate the output in O(n) time, rather than O(n^2) time.
您可以使用线性运算符来利用这一点，例如 GMRES in scipy implementation, A can be a LinearOperator。线性运算符只是一个计算 Ax 的函数，这是您的 "evaluate the output" 步骤。
否则，由于缺少临时解决方案，我不熟悉可以使用线性运算符加速的任何确切方法，因此我需要更多地了解您的问题，例如，您的矩阵是带状的吗？
我有一个线性函数（n 个输入 -> n 个输出），并使用函数的特殊结构（一些类似 DP 的算法），我可以在 O(n) 时间内评估输出，而不是 O( n^2) 次。现在，给定一些输出值，我需要找到对输出求值的输入。
我可以拼出矩阵分量（通过评估具有 n 个基本输入的线性函数）并使用一些算法，如 LU 分解，但这需要 O(n^3) 的时间来计算。是否有更快的算法，利用线性函数的结构？
（由于线性函数不对称，无法使用共轭梯度法。）
我需要精确解，其中n很小（n=10~20），但我需要在一秒钟内进行数十万次这种计算。
从代码设计的角度来看，如果算法不需要线性函数的转置会更好。 （虽然以更多的代码和更多的调试为代价，但可以提供时间复杂度为O(n)的转置函数。）
你考虑过GMRES吗？您提到您正在寻找精确的解决方案，但是您可以相当快地获得机器精度误差。
I can evaluate the output in O(n) time, rather than O(n^2) time.
您可以使用线性运算符来利用这一点，例如 GMRES in scipy implementation, A can be a LinearOperator。线性运算符只是一个计算 Ax 的函数，这是您的 "evaluate the output" 步骤。
否则，由于缺少临时解决方案，我不熟悉可以使用线性运算符加速的任何确切方法，因此我需要更多地了解您的问题，例如，您的矩阵是带状的吗？