我推荐ARPACK，它为广义特征值问题提供无矩阵例程，并在其文档中为此目的提供示例。此方法是使用最广泛的方法之一，特别是对于您只搜索几个特征值/向量（例如最小的，在您的情况下）的相对较大的问题。

此外，大小为的特征值问题并不是特别大，并且可能在任何现代工作站上都​​可以解决。但是，如果这个问题变得更大，黄金标准是SLEPc，它是一个包含许多特征值求解器的库，可以将您的问题分布在许多计算节点上。$10^4$

您是对的，为大型稀疏系统编写高效且强大的特征值求解器是一项艰巨的任务，只能作为最后的手段自己完成。Spencer 已经在他的回答中给出了主要参与者（用于单节点多线程计算的 ARPACK，它是 MATLAB 和 SciPy 的一部分，以及用于分布式计算的 SLEPc，可以通过slepc4py在 Python 中访问）。两者都解决了广义特征值问题，并且都可以采用计算矩阵向量乘积而不是矩阵的过程。

由于您对最小量级特征值感兴趣，您可能需要使用移位和反转策略（即，计算最小量级特征值$A^{-1}$. 当然，您永远不会真正计算逆矩阵。相反，每当您需要计算$A^{-1}v$对于一些向量$v$, 你解决$Aw=v$并使用$w$为了$A^{-1}v$. 有几种策略可以加速这一点，基于 ARPACK/SLEPc 也只需要一个提供逆向应用程序的过程（显而易见的那些应该已经在 ARPACK/SLEPc 中实现）：

1. 由于您需要重复求解线性系统，因此您需要计算矩阵的 LU 或 Cholesky 因式分解$A$提前并在迭代期间使用线性求解的（更快的）后向/前向替换部分。

2. 在您的情况下，您可能一开始就不想构建大张量积矩阵；在这种情况下，使用迭代求解器（例如 CG）来求解$Aw=v$以及（特别是如果你能提供一个好的预处理器）。这样，整个特征值求解器只需要一个过程来执行矩阵向量乘法。（您可能必须稍微调整一下公差才能获得好的结果。）

我完全同意到目前为止发布的答案。我想指出矩阵

$$A = (I \otimes A_1 + A_2 \otimes I)$$

永远不需要明确地形成。正如其他答案正确指出的那样，只需要与 A 或其倒数形成矩阵向量积 (matvecs)。形式的 Matvecs$Ax$可以使用身份完成

$$(B^T \otimes C)x = \text{vec}(CXB),$$

在哪里$\text{vec}(X) = x$. 所以，在你的情况下

$$Ax = \text{vec}(A_1X) + \text{vec}(XA_2^T).$$

要将逆运算符应用于向量（根据最小广义特征值的需要），您可以使用 Krylov 子空间方法。您可以对 matvecs 使用相同的技巧。