Apache Spark에서 대규모 선형 시스템을 해결합니다.

Question

저는 현재 대규모 선형 시스템 인 Ax = b를 Spark을 사용하여 풀고 자합니다. 솔루션을 찾기 위해 많은 검색을 수행했으며 this 링크가 A의 의사 역수를 계산하여 다음 단계로 역행렬을 곱하기 위해 찾은 유일한 해결책이었습니다. 간단히하기 위해 여기에 해결책을 복사합니다.

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이 있습니다.