如何求解稀疏矩阵的线性方程 AX=b

Question

我有稀疏矩阵 A(120,000*120,000) 和向量 b(120,000)，我想使用 Eigen 库求解线性方程组 AX=b。我试图按照文档进行操作，但总是出现错误。我还尝试将矩阵更改为密集矩阵并求解系统

    Eigen::MatrixXd H(N,N);
    HH =Eigen:: MatrixXd(A);
    Eigen::ColPivHouseholderQR<Eigen::MatrixXd> dec(H);
    Eigen::VectorXd RR = dec.solve(b);

但是我遇到了内存错误。请帮我找到解决这个问题的方法。

Answer 1

对于稀疏系统，我们一般采用迭代的方法。一个原因是 LU、QR 等直接求解器...因式分解会填充您的初始矩阵（填充初始零分量被非零分量替换的意义）。在大多数情况下，生成的 密集矩阵 不再适合内存（-> 您的内存错误 ）。简而言之，迭代求解器不会改变您的稀疏模式，因为它们只涉及矩阵向量乘积（无填充）。

也就是说，您必须首先知道您的系统是否是 对称正定（又名 SPD），在这种情况下您可以使用 conjugate gradient method. Otherwise you must use methods for unsymmetric systems like BiCGSTAB or GMRES.

您必须知道，大多数时候我们使用 preconditioner，尤其是当您的系统状况不佳时。

查看我发现的 Eigen 文档（没有预处理器 afaik 的示例）：

  int n = 10000;
  VectorXd x(n), b(n);
  SparseMatrix<double> A(n,n);
  /* ... fill A and b ... */ 
  BiCGSTAB<SparseMatrix<double> > solver;
  solver.compute(A);
  x = solver.solve(b);
  std::cout << "#iterations:     " << solver.iterations() << std::endl;
  std::cout << "estimated error: " << solver.error()      << std::endl;

这可能是一个好的开始（如果您的矩阵是 SPD，请使用共轭梯度法）。请注意，这里没有预处理器，因此收敛速度肯定会很慢。

回顾：大矩阵 -> 迭代法 + 预条件子。

这确实是第一个"basic/naive"解释，您可以在Saad's book: Iterative Methods for Sparse Linear Systems中找到有关该理论的更多信息。同样，这个主题很大，您可以找到很多关于这个主题的其他书籍。

我不是 Eigen 用户，但是有 precondtioners here。 -> Incomplete LU (unsymmetric systems) or Incomplete Cholesky (SPD systems) 一般都是很好的通用预条件子，先来测试一下。

如何求解稀疏矩阵的线性方程 AX=b

How can I solve linear equation AX=b for sparse matrix

c++

eigen