[Spark] Breeze CSCMatrix * DenseMatrix 분석

Breeze canMulM_DM

• Breeze의 canMulM_DM 함수는 CSCMatrix * DenseMatrix를 지원합니다.
• 즉, Sparse Matrix와 Dense Matirx 간 곱셈을 지원하는 함수입니다.
• github
  • https://github.com/scalanlp/breeze/blob/b965a1c36e955a87fdffa1b9f5b3f44e3a5f191c/math/src/main/codegen/breeze/linalg/operators/CSCMatrixOps.scala#L647

알고리즘 순서

• 우측행렬 컬럼 기준으로 좌측행렬 컬럼이 이중포문을 이루며 곱해집니다.
• 우측행렬 컬럼은 Dense하게 모든 요소를 곱셈에 사용하지만, 좌측행렬 컬럼은 존재하는 요소만 곱셈에 사용합니다.
• 곱셈 결과값은 아래와 같은 형태로 결과 행렬 좌표에 삽입됩니다.
  • 결과행렬(좌측행렬 요소값의 행번호, 우측행렬의 열번호) += (우측행렬 요소값 * 좌측행렬 요소값)

Code

@expand
@expand.valify
implicit def canMulM_DM[@expand.args(Int, Float, Double, Long) T]
  : breeze.linalg.operators.OpMulMatrix.Impl2[CSCMatrix[T], DenseMatrix[T], DenseMatrix[T]] =
  new breeze.linalg.operators.OpMulMatrix.Impl2[CSCMatrix[T], DenseMatrix[T], DenseMatrix[T]] {
    def apply(a: CSCMatrix[T], b: DenseMatrix[T]) = {

      if (a.cols != b.rows) throw new RuntimeException("Dimension Mismatch!")

        // 결과 DenseMatrix 생성
        val res = new DenseMatrix[T](a.rows, b.cols)

        // 우측 행렬의 col index 
        var i = 0

        // 우측 행렬의 col 순서대로 진행
        while (i < b.cols) {

            // 좌측 행렬의 col index
            var j = 0

            // 좌측 행렬의 col 순서대로 진행
            while (j < a.cols) {

                // v = 우측행렬(좌측행렬의 j번째 col, 우측행렬의 i번째 col)
                // 즉, 우측 행렬의 i번째 col에 있는 모든 요소에 접근하게 된다.
                val v = b(j, i)

                // k = 좌측 행렬의 j번째 col에 있는 요소의 행과 값을 가져오기 위한 index
                // 즉, 좌측 행렬의 j번째 col에 존재하는 요소에만 접근하게 된다.
                var k = a.colPtrs(j)

                while (k < a.colPtrs(j + 1)) {

                    // 결과행렬(좌측행렬 요소값의 행번호, 우측행렬의 열번호) += (우측행렬 요소값 * 좌측행렬 요소값)
                    res(a.rowIndices(k), i) += v * a.data(k)
                    k += 1
                  }
                  j += 1
            }
            i += 1
      }
      // 결과 DenseMatrix 반환
      res
    }
    implicitly[BinaryRegistry[Matrix[T], Matrix[T], OpMulMatrix.type, Matrix[T]]].register(this)
  }