Решение крупномасштабной линейной системы в Apache Spark

В настоящее время я пытаюсь решить крупномасштабную линейную систему Ax=b с помощью Spark. Я много искал, чтобы найти решение, и this была единственным решением, которое я нашел для вычисления псевдоинверсии 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, и я думаю, что это будет невозможно для больших матриц. Я был бы признателен за любую помощь и мысли, чтобы решить эту проблему.


person EdgeRover    schedule 11.09.2016    source источник


Ответы (1)


Вы можете попробовать один из итерационных алгоритмов (например, PCG). Вместо того, чтобы решать Ax=b напрямую, вы ищете x, который минимизирует f(x)=0,5x^tAx -x^tb

При параллельном PCG фактическая итерация выполняется последовательно; это простое умножение и другие операции, которые используются вашими работниками. Но это позволяет вам распределять разреженную матрицу по кластеру.

К сожалению, библиотека линейной алгебры Spark находится в стадии разработки, и у меня нет примера кода, чтобы показать вам. Вероятно, для вашей проблемы есть лучшие методы, чем PCG, нам просто нужно реализовать их в Spark. Не уверен, каков ваш фон, но вы могли бы начать с изучения того, как можно решать системы линейных уравнений параллельно.

Изменить: есть еще обсуждение здесь и здесь.

person Graham S    schedule 13.09.2016
comment
Я нашел реализацию алгоритма LSQR на Python здесь. - person Graham S; 11.10.2016