apache-spark - 在 Apache Spark 中求解大型线性系统

Question

我目前正在寻找使用 Spark 求解大型线性系统 Ax=b 的方法。我做了很多搜索以找到解决方案和 this link 是我找到的唯一解决方案，用于计算 A 的伪逆，以便在下一步将其求逆并乘以 b。为简单起见，我将在此处复制解决方案。

import org.apache.spark.mllib.linalg.{Vectors,Vector,Matrix,SingularValueDecomposition,DenseMatrix,DenseVector}
import org.apache.spark.mllib.linalg.distributed.RowMatrix

def computeInverse(X: RowMatrix): DenseMatrix = {
  val nCoef = X.numCols.toInt
  val svd = X.computeSVD(nCoef, computeU = true)
  if (svd.s.size < nCoef) {
    sys.error(s"RowMatrix.computeInverse called on singular matrix.")
  }

  // Create the inv diagonal matrix from S 
  val invS = DenseMatrix.diag(new DenseVector(svd.s.toArray.map(x => math.pow(x,-1))))

  // U cannot be a RowMatrix
  val U = new DenseMatrix(svd.U.numRows().toInt,svd.U.numCols().toInt,svd.U.rows.collect.flatMap(x => x.toArray))

  // If you could make V distributed, then this may be better. However its alreadly local...so maybe this is fine.
  val V = svd.V
  // inv(X) = V*inv(S)*transpose(U)  --- the U is already transposed.
  (V.multiply(invS)).multiply(U)
  }

但是这个解决方案的问题是，最终我们必须将 U 设为局部 DenseMatrix，我认为这对于大型矩阵是不可能的。我将不胜感激任何帮助和想法来解决这个问题。

Answer 1

您可以尝试其中一种迭代算法 ( e.g. PCG )。不是直接求解 Ax=b，而是搜索使 f(x)=0.5x^tAx -x^tb 最小的 x

使用并行 PCG，实际迭代是串行完成的；这是您的工作人员共享的简单乘法和其他操作。但这允许您在集群中分布稀疏矩阵。

不幸的是，Spark 的线性代数库还在开发中，我没有示例代码可以向您展示。对于您的问题，可能有比 PCG 更好的方法，我们只需要在 Spark 中实现它们。不确定您的背景是什么，但您可以从研究如何并行求解线性方程组开始。

编辑:还有一些讨论 here和 here .