{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/43610366","id":43610366,"diff_hunk":"@@ -402,4 +441,474 @@ class BlockMatrix @Since(\"1.3.0\") (\n         s\"A.colsPerBlock: $colsPerBlock, B.rowsPerBlock: ${other.rowsPerBlock}\")\n     }\n   }\n+\n+  /**\n+   * Schur Complement of a BlockMatrix.  For a matrix that is in 4 partitions:\n+   *  A=[a11, a12; a21; a22], the Schur Complement S is S = a22 - (a21 * a11^-1 * a12).\n+   * The Schur Complement is always (n-1) x (n-1), which is the size of a22. a11 is expected\n+   * to fit into memory so that Breeze inversions can be computed.\n+   *\n+   * @return BlockMatrix Schur Complement as BlockMatrix\n+   * @since 1.6.0\n+   */\n+  private[mllib] def SchurComplement: BlockMatrix = {\n+    require(this.numRowBlocks == this.numColBlocks, \"Block Matrix must be square.\")\n+    require(this.numRowBlocks > 1, \"Block Matrix must be larger than one block.\")\n+    val topRange = (0, 0); val botRange = (1, this.numColBlocks - 1)\n+    val a11 = this.subBlock(topRange, topRange)\n+    val a12 = this.subBlock(topRange, botRange)\n+    val a21 = this.subBlock(botRange, topRange)\n+    val a22 = this.subBlock(botRange, botRange)\n+\n+    val a11Brz = inv(a11.toBreeze) // note that intermediate a11 calcs derive from inv(a11)\n+    val a11Mtx = Matrices.dense(a11.numRows.toInt, a11.numCols.toInt, a11Brz.toArray)\n+    val a11RDD = this.blocks.sparkContext.parallelize(Seq(((0, 0), a11Mtx)))\n+    val a11Inv = new BlockMatrix(a11RDD, this.rowsPerBlock, this.colsPerBlock)\n+\n+    val S = a22.subtract(a21.multiply(a11Inv.multiply(a12)))\n+    S\n+  }\n+\n+  /**\n+   * Returns a rectangular (sub)BlockMatrix with block ranges as specified.  Block Ranges\n+   * refer to a range of blocks that each contain a matrix.  The returned BlockMatrix\n+   * is numbered so that the upper left block is indexed as (0,0).\n+   *\n+   *\n+   * @param blockRowRange The lower and upper row range of blocks, as (Int,Int)\n+   * @param blockColRange The lower and upper col range of blocks, as (Int, Int)\n+   * @return a BlockMatrix with (0,0) as the upper leftmost block index\n+   * @since 1.6.0\n+   */\n+  private [mllib] def subBlock(blockRowRange: (Int, Int), blockColRange: (Int, Int)):\n+          BlockMatrix = {\n+    //  Extracts BlockMatrix elements from a specified range of block indices\n+    //  Creating a Sub BlockMatrix of rectangular shape.\n+    //  Also reindexes so that the upper left block is always (0, 0)\n+\n+    // TODO: add a require statement ...rowMax<=size..\n+    val rowMin = blockRowRange._1;    val rowMax = blockRowRange._2\n+    val colMin = blockColRange._1 ;   val colMax = blockColRange._2\n+    val extractedSeq = this.blocks.filter{ case((x, y), matrix) =>\n+      x >= rowMin && x<= rowMax &&         // finding blocks\n+        y >= colMin && y<= colMax }.map {   // shifting indices\n+      case(((x, y), matrix) ) => ((x-rowMin, y-colMin), matrix)\n+    }\n+    new BlockMatrix(extractedSeq, rowsPerBlock, colsPerBlock)\n+  }\n+\n+  /**\n+   * Computes the LU decomposition of a Single Block from BlockMatrix using the\n+   * Breeze LU method.  The method (as written) operates -only- on the upper\n+   * left (0,0) corner of the BlockMatrix.\n+   *\n+   * @return List[BDM[Double]] of Breeze Matrices (BDM) (P,L,U) for blockLU method.\n+   * @since 1.6.0\n+   */\n+  private [mllib] def singleBlockPLU: List[BDM[Double]] = {\n+    // returns PA = LU factorization from Breeze\n+    val PLU = LU(this.subBlock((0, 0), (0, 0)).toBreeze)\n+    val k = PLU._1.cols\n+    val L = lowerTriangular(PLU._1) - diag(diag(PLU._1)) + diag(DenseVector.fill(k){1.0})\n+    val U = upperTriangular(PLU._1);\n+    var P = diag(DenseVector.fill(k){1.0})\n+    var Pi = diag(DenseVector.fill(k){1.0})\n+    // size of square matrix\n+    // populating permutation matrix\n+    var i = 0\n+    while (i < k) {\n+      val I = {\n+        if (i == 0){k - 1}\n+        else {i - 1}\n+      }\n+      val J = PLU._2(i) -1\n+      if (i != J) {\n+        Pi(i, J) += 1.0\n+        Pi(J, i) += 1.0\n+        Pi(i, i) -= 1.0\n+        Pi(J, J) -= 1.0\n+      }\n+      P = Pi * P  // constructor Pi*P for PA=LU\n+      // resetting Pi for next iteration\n+      if (i != J) {\n+        Pi(i, J) -= 1.0\n+        Pi(J, i) -= 1.0\n+        Pi(i, i) += 1.0\n+        Pi(J, J) += 1.0\n+      }\n+      i += 1\n+    }\n+    List(P, L, U)\n+  }\n+\n+\n+  /**\n+   * This method reassigns 'absolute' index locations (i,j), to sequences.  This is\n+   * designed to reconsitute the orignal block locations that were lost in the\n+   * subBlock method.\n+   *\n+   * @param rowMin The new lowest row value\n+   * @param colMin The new lowest column value\n+   * @return an RDD of Sequences with new block indexing\n+   * @since 1.6.0\n+   *\n+   */\n+  private [mllib] def shiftIndices(rowMin: Int, colMin: Int): RDD[((Int, Int), Matrix)] = {\n+    // This routine recovers the absolute indexing of the block matrices for reassembly\n+    val extractedSeq = this.blocks.map {   // shifting indices\n+      case(((x, y), matrix)) => ((x + rowMin, y + colMin), matrix)\n+    }\n+    extractedSeq\n+  }\n+\n+  /**\n+   * A class that contains the 3 main BlockMatrix items to be returned\n+   * when calling blockLU.\n+   *\n+   * @param p The Permutation BlockMatrix\n+   * @param l Lower Diagonal BlockMatrix\n+   * @param u Upper Diagonal BlockMatrix\n+   *\n+   */\n+\n+  private [mllib] class PLU(p: BlockMatrix, l: BlockMatrix, u: BlockMatrix ){\n+    val P = p\n+    val L = l\n+    val U = u\n+  }\n+\n+  /**\n+   * Extends the base class PLU with additional matrices that are used\n+   * int he solve method.\n+   *\n+   * @param p The Permutation BlockMatrix\n+   * @param l Lower Diagonal BlockMatrix\n+   * @param u Upper Diagonal BlockMatrix\n+   *\n+   * @param lInv The inverse of the lower diagaonal matrices (in (i,i)th\n+   *             cells only).\n+   * @param uInv The inverse of the upper diagaonal matrices (in (i,i)th\n+   *             cells only).\n+   */\n+  private [mllib] class PLUandInverses(p: BlockMatrix, l: BlockMatrix, u: BlockMatrix,\n+\n+                       lInv: BlockMatrix, uInv: BlockMatrix) extends PLU(p, l, u) {\n+    val dLi = lInv\n+    val dUi = uInv\n+  }\n+\n+  /**\n+   * Computes the LU Decomposition of a Square Matrix.  For a matrix A of size (n x n)\n+   * LU decomposition computes the Lower Triangular Matrix L, the Upper Triangular\n+   * Matrix U, along with a Permutation Matrix P, such that PA=LU.  The Permutation\n+   * Matrix addresses cases where zero entries prevent forward substitution\n+   * solution of L or U.\n+   *\n+   * The BlockMatrix version takes a BlockMatrix as an input and returns a Tuple\n+   * of 5 BlockMatrix objects:\n+   * P, L, U (in that order), such that P.multiply(A)-L.multiply(U) = 0\n+   * and Li, Ui, which are the inverse of the block diagonal terms for L and U.\n+   *\n+   * The blockLU method will return only P,L, and U, but blockLUtoSolver will return\n+   * the extra Li and Ui matrices, which will be used by the solve method\n+   * so that it does not need to recompute these values.\n+   *\n+   * The method follows a procedure similar to the method used in ScaLAPACK, but\n+   * places more emphasis on preparing BlockMatrix objects as inputs to large\n+   * BlockMatrix.multiply operations.\n+   *\n+   *\n+   * @return  PLUandInverses(P,L,U,Li,Ui) as a Tuple of BlockMatrix\n+   * @since 1.6.0","path":"mllib/src/main/scala/org/apache/spark/mllib/linalg/distributed/BlockMatrix.scala","position":267,"original_position":267,"commit_id":"0909197b87e62d04049839e573f09aa9066625a5","original_commit_id":"0909197b87e62d04049839e573f09aa9066625a5","user":{"login":"yu-iskw","id":1523515,"avatar_url":"https://avatars.githubusercontent.com/u/1523515?v=3","gravatar_id":"","url":"https://api.github.com/users/yu-iskw","html_url":"https://github.com/yu-iskw","followers_url":"https://api.github.com/users/yu-iskw/followers","following_url":"https://api.github.com/users/yu-iskw/following{/other_user}","gists_url":"https://api.github.com/users/yu-iskw/gists{/gist_id}","starred_url":"https://api.github.com/users/yu-iskw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yu-iskw/subscriptions","organizations_url":"https://api.github.com/users/yu-iskw/orgs","repos_url":"https://api.github.com/users/yu-iskw/repos","events_url":"https://api.github.com/users/yu-iskw/events{/privacy}","received_events_url":"https://api.github.com/users/yu-iskw/received_events","type":"User","site_admin":false},"body":"move @since to outside of the comment","created_at":"2015-11-02T09:40:30Z","updated_at":"2015-11-02T09:40:30Z","html_url":"https://github.com/apache/spark/pull/8563#discussion_r43610366","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/8563","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/43610366"},"html":{"href":"https://github.com/apache/spark/pull/8563#discussion_r43610366"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/8563"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/8563","id":43955310,"html_url":"https://github.com/apache/spark/pull/8563","diff_url":"https://github.com/apache/spark/pull/8563.diff","patch_url":"https://github.com/apache/spark/pull/8563.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/8563","number":8563,"state":"open","locked":false,"title":"[SPARK-8514] LU factorization on BlockMatrix","user":{"login":"nilmeier","id":7935455,"avatar_url":"https://avatars.githubusercontent.com/u/7935455?v=3","gravatar_id":"","url":"https://api.github.com/users/nilmeier","html_url":"https://github.com/nilmeier","followers_url":"https://api.github.com/users/nilmeier/followers","following_url":"https://api.github.com/users/nilmeier/following{/other_user}","gists_url":"https://api.github.com/users/nilmeier/gists{/gist_id}","starred_url":"https://api.github.com/users/nilmeier/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nilmeier/subscriptions","organizations_url":"https://api.github.com/users/nilmeier/orgs","repos_url":"https://api.github.com/users/nilmeier/repos","events_url":"https://api.github.com/users/nilmeier/events{/privacy}","received_events_url":"https://api.github.com/users/nilmeier/received_events","type":"User","site_admin":false},"body":"@mengxr and/or @shivaram may be reviewing.","created_at":"2015-09-02T05:33:11Z","updated_at":"2015-11-02T09:40:30Z","closed_at":null,"merged_at":null,"merge_commit_sha":"07e0f7a3617b916cc351d51279e9df2015f69e16","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/8563/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/8563/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/8563/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/0909197b87e62d04049839e573f09aa9066625a5","head":{"label":"nilmeier:SPARK-8514_LU_factorization","ref":"SPARK-8514_LU_factorization","sha":"0909197b87e62d04049839e573f09aa9066625a5","user":{"login":"nilmeier","id":7935455,"avatar_url":"https://avatars.githubusercontent.com/u/7935455?v=3","gravatar_id":"","url":"https://api.github.com/users/nilmeier","html_url":"https://github.com/nilmeier","followers_url":"https://api.github.com/users/nilmeier/followers","following_url":"https://api.github.com/users/nilmeier/following{/other_user}","gists_url":"https://api.github.com/users/nilmeier/gists{/gist_id}","starred_url":"https://api.github.com/users/nilmeier/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nilmeier/subscriptions","organizations_url":"https://api.github.com/users/nilmeier/orgs","repos_url":"https://api.github.com/users/nilmeier/repos","events_url":"https://api.github.com/users/nilmeier/events{/privacy}","received_events_url":"https://api.github.com/users/nilmeier/received_events","type":"User","site_admin":false},"repo":{"id":36460656,"name":"spark","full_name":"nilmeier/spark","owner":{"login":"nilmeier","id":7935455,"avatar_url":"https://avatars.githubusercontent.com/u/7935455?v=3","gravatar_id":"","url":"https://api.github.com/users/nilmeier","html_url":"https://github.com/nilmeier","followers_url":"https://api.github.com/users/nilmeier/followers","following_url":"https://api.github.com/users/nilmeier/following{/other_user}","gists_url":"https://api.github.com/users/nilmeier/gists{/gist_id}","starred_url":"https://api.github.com/users/nilmeier/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nilmeier/subscriptions","organizations_url":"https://api.github.com/users/nilmeier/orgs","repos_url":"https://api.github.com/users/nilmeier/repos","events_url":"https://api.github.com/users/nilmeier/events{/privacy}","received_events_url":"https://api.github.com/users/nilmeier/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/nilmeier/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/nilmeier/spark","forks_url":"https://api.github.com/repos/nilmeier/spark/forks","keys_url":"https://api.github.com/repos/nilmeier/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nilmeier/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nilmeier/spark/teams","hooks_url":"https://api.github.com/repos/nilmeier/spark/hooks","issue_events_url":"https://api.github.com/repos/nilmeier/spark/issues/events{/number}","events_url":"https://api.github.com/repos/nilmeier/spark/events","assignees_url":"https://api.github.com/repos/nilmeier/spark/assignees{/user}","branches_url":"https://api.github.com/repos/nilmeier/spark/branches{/branch}","tags_url":"https://api.github.com/repos/nilmeier/spark/tags","blobs_url":"https://api.github.com/repos/nilmeier/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nilmeier/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nilmeier/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/nilmeier/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nilmeier/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/nilmeier/spark/languages","stargazers_url":"https://api.github.com/repos/nilmeier/spark/stargazers","contributors_url":"https://api.github.com/repos/nilmeier/spark/contributors","subscribers_url":"https://api.github.com/repos/nilmeier/spark/subscribers","subscription_url":"https://api.github.com/repos/nilmeier/spark/subscription","commits_url":"https://api.github.com/repos/nilmeier/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/nilmeier/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/nilmeier/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/nilmeier/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/nilmeier/spark/contents/{+path}","compare_url":"https://api.github.com/repos/nilmeier/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nilmeier/spark/merges","archive_url":"https://api.github.com/repos/nilmeier/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nilmeier/spark/downloads","issues_url":"https://api.github.com/repos/nilmeier/spark/issues{/number}","pulls_url":"https://api.github.com/repos/nilmeier/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/nilmeier/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/nilmeier/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nilmeier/spark/labels{/name}","releases_url":"https://api.github.com/repos/nilmeier/spark/releases{/id}","created_at":"2015-05-28T19:19:10Z","updated_at":"2015-05-28T19:19:31Z","pushed_at":"2015-10-11T20:43:05Z","git_url":"git://github.com/nilmeier/spark.git","ssh_url":"git@github.com:nilmeier/spark.git","clone_url":"https://github.com/nilmeier/spark.git","svn_url":"https://github.com/nilmeier/spark","homepage":null,"size":171492,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"a16396df76cc27099011bfb96b28cbdd7f964ca8","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","created_at":"2014-02-25T08:00:08Z","updated_at":"2015-11-02T09:01:09Z","pushed_at":"2015-11-02T08:59:54Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":1651367,"stargazers_count":5982,"watchers_count":5982,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":5566,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":372,"forks":5566,"open_issues":372,"watchers":5982,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/8563"},"html":{"href":"https://github.com/apache/spark/pull/8563"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/8563"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/8563/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/8563/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/8563/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/0909197b87e62d04049839e573f09aa9066625a5"}}}}