payload: {"action":"created","comment":{"url":"https://api.github.com/repos/wo80/CSparse.NET/pulls/comments/315463504","pull_request_review_id":276877318,"id":315463504,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDMxNTQ2MzUwNA==","diff_hunk":"@@ -420,6 +421,131 @@ public override CompressedColumnStorage<double> Multiply(CompressedColumnStorage\n             return result; // success\r\n         }\r\n \r\n+        public override CompressedColumnStorage<double> ParallelMultiply(CompressedColumnStorage<double> other)\r\n+        {\r\n+            int m = this.rowCount;\r\n+            int n = other.ColumnCount;\r\n+            int block_size = 16;\r\n+            if (n <= block_size)\r\n+            {\r\n+                return Multiply(other);\r\n+            }\r\n+\r\n+            int anz = this.NonZerosCount;\r\n+            int bnz = other.NonZerosCount;\r\n+\r\n+            // Check inputs\r\n+            if (other == null)\r\n+            {\r\n+                throw new ArgumentNullException(\"other\");\r\n+            }\r\n+\r\n+            if (this.ColumnCount != other.RowCount)\r\n+            {\r\n+                throw new ArgumentException(Resources.MatrixDimensions);\r\n+            }\r\n+\r\n+            if ((m > 0 && this.ColumnCount == 0) || (other.RowCount == 0 && n > 0))\r\n+            {\r\n+                throw new Exception(Resources.InvalidDimensions);\r\n+            }\r\n+\r\n+            var bp = other.ColumnPointers;\r\n+            var bi = other.RowIndices;\r\n+            var bx = other.Values;\r\n+\r\n+            var nblocks = (n + block_size - 1) / block_size;\r\n+            block_size = (n + nblocks - 1) / nblocks;\r\n+            var results = new SparseMatrix[nblocks];\r\n+            var indices = new int[nblocks];\r\n+            var nresults = 0;\r\n+            for (var j = 0; j < nblocks; j++)\r\n+            {\r\n+                var start = j * block_size;\r\n+                var end = Math.Min(n, (j + 1) * block_size);\r\n+                var bnz2 = bp[end] - bp[start];\r\n+                if (bnz2 != 0)\r\n+                {\r\n+                    indices[nresults] = start;\r\n+                    results[nresults++] = new SparseMatrix(m, end - start, anz + bnz2);\r\n+                }\r\n+            }\r\n+            Parallel.For(0, nresults,\r\n+                index =>\r\n+                {\r\n+                    var result = results[index];\r\n+                    var rnz = 0;\r\n+\r\n+                    // Workspace\r\n+                    var w = new int[m];\r\n+                    var x = new double[m];\r\n+\r\n+                    var rcp = result.ColumnPointers;\r\n+                    var nc = result.ColumnCount;\r\n+                    for (var j = 0; j < nc; j++)\r\n+                    {\r\n+                        if (rnz + m > result.Values.Length)\r\n+                        {\r\n+                            // Might throw out of memory exception.\r\n+                            result.Resize(2 * (result.Values.Length) + m);\r\n+                        }\r\n+                        var ci = result.RowIndices;\r\n+                        var cx = result.Values; // C.i and C.x may be reallocated\r\n+                        rcp[j] = rnz; // column j of C starts here\r\n+                        var j2 = j + indices[index];\r\n+                        for (var p = bp[j2]; p < bp[j2 + 1]; p++)\r\n+                        {\r\n+                            rnz = this.Scatter(bi[p], bx[p], w, x, j + 1, result, rnz);\r\n+                        }\r\n+\r\n+                        for (var p = rcp[j]; p < rnz; p++)\r\n+                        {\r\n+                            cx[p] = x[ci[p]];\r\n+                        }\r\n+                    }\r\n+\r\n+                    rcp[nc] = rnz; // finalize the last column of C\r\n+                    result.Resize(0); // remove extra space from C\r","path":"CSparse/Double/SparseMatrix.cs","position":96,"original_position":96,"commit_id":"4e401e9de95e7640ad5ade1d639d562bf01aca9b","original_commit_id":"4e401e9de95e7640ad5ade1d639d562bf01aca9b","user":{"login":"andreasg123","id":15636985,"node_id":"MDQ6VXNlcjE1NjM2OTg1","avatar_url":"https://avatars2.githubusercontent.com/u/15636985?v=4","gravatar_id":"","url":"https://api.github.com/users/andreasg123","html_url":"https://github.com/andreasg123","followers_url":"https://api.github.com/users/andreasg123/followers","following_url":"https://api.github.com/users/andreasg123/following{/other_user}","gists_url":"https://api.github.com/users/andreasg123/gists{/gist_id}","starred_url":"https://api.github.com/users/andreasg123/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andreasg123/subscriptions","organizations_url":"https://api.github.com/users/andreasg123/orgs","repos_url":"https://api.github.com/users/andreasg123/repos","events_url":"https://api.github.com/users/andreasg123/events{/privacy}","received_events_url":"https://api.github.com/users/andreasg123/received_events","type":"User","site_admin":false},"body":"I truncated the partial results to reduce the memory footprint before allocating the combined matrix. However, I'm happy to remove it if you want to emphasize number of memory reallocations over maximum memory allocation.","created_at":"2019-08-20T00:20:20Z","updated_at":"2019-08-20T00:20:20Z","html_url":"https://github.com/wo80/CSparse.NET/pull/18#discussion_r315463504","pull_request_url":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18","author_association":"NONE","_links":{"self":{"href":"https://api.github.com/repos/wo80/CSparse.NET/pulls/comments/315463504"},"html":{"href":"https://github.com/wo80/CSparse.NET/pull/18#discussion_r315463504"},"pull_request":{"href":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18"}},"in_reply_to_id":315122180},"pull_request":{"url":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18","id":308323821,"node_id":"MDExOlB1bGxSZXF1ZXN0MzA4MzIzODIx","html_url":"https://github.com/wo80/CSparse.NET/pull/18","diff_url":"https://github.com/wo80/CSparse.NET/pull/18.diff","patch_url":"https://github.com/wo80/CSparse.NET/pull/18.patch","issue_url":"https://api.github.com/repos/wo80/CSparse.NET/issues/18","number":18,"state":"open","locked":false,"title":"Parallel multiplication of sparse matrices","user":{"login":"andreasg123","id":15636985,"node_id":"MDQ6VXNlcjE1NjM2OTg1","avatar_url":"https://avatars2.githubusercontent.com/u/15636985?v=4","gravatar_id":"","url":"https://api.github.com/users/andreasg123","html_url":"https://github.com/andreasg123","followers_url":"https://api.github.com/users/andreasg123/followers","following_url":"https://api.github.com/users/andreasg123/following{/other_user}","gists_url":"https://api.github.com/users/andreasg123/gists{/gist_id}","starred_url":"https://api.github.com/users/andreasg123/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andreasg123/subscriptions","organizations_url":"https://api.github.com/users/andreasg123/orgs","repos_url":"https://api.github.com/users/andreasg123/repos","events_url":"https://api.github.com/users/andreasg123/events{/privacy}","received_events_url":"https://api.github.com/users/andreasg123/received_events","type":"User","site_admin":false},"body":"The method `ParallelMultiply` uses [`Parallel.For`](https://docs.microsoft.com/en-us/dotnet/api/system.threading.tasks.parallel.for?view=netframework-4.8) to speed up matrix multiplication by using multiple CPU cores.\r\n\r\nI tested it by multiplying randomly initialized 800x600 and 600x800 matrices with different fractions of non zeros. With a non-zero fraction of 0.5 and above, the parallel approach is about 6 times faster. The total CPU time overhead is about 60% at 0.7 (about 10 parallel threads) and goes up for smaller non-zero fractions, e.g., 95% at 0.4. The break-even point is at a non-zero fraction of 0.03 where both approaches take the same time. With a non-zero fraction of 0.01, the parallel approach takes about 4 times longer.\r\n\r\nAs the speed-up is larger with less sparse matrices, this would probably also benefit dense matrices.","created_at":"2019-08-17T22:59:31Z","updated_at":"2019-08-20T00:20:20Z","closed_at":null,"merged_at":null,"merge_commit_sha":"e6e30b122252c9de47b9acc5166b4bbff12afa0a","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[{"id":221780113,"node_id":"MDU6TGFiZWwyMjE3ODAxMTM=","url":"https://api.github.com/repos/wo80/CSparse.NET/labels/enhancement","name":"enhancement","color":"84b6eb","default":true}],"milestone":null,"commits_url":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18/commits","review_comments_url":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18/comments","review_comment_url":"https://api.github.com/repos/wo80/CSparse.NET/pulls/comments{/number}","comments_url":"https://api.github.com/repos/wo80/CSparse.NET/issues/18/comments","statuses_url":"https://api.github.com/repos/wo80/CSparse.NET/statuses/4e401e9de95e7640ad5ade1d639d562bf01aca9b","head":{"label":"andreasg123:parallel-multiply","ref":"parallel-multiply","sha":"4e401e9de95e7640ad5ade1d639d562bf01aca9b","user":{"login":"andreasg123","id":15636985,"node_id":"MDQ6VXNlcjE1NjM2OTg1","avatar_url":"https://avatars2.githubusercontent.com/u/15636985?v=4","gravatar_id":"","url":"https://api.github.com/users/andreasg123","html_url":"https://github.com/andreasg123","followers_url":"https://api.github.com/users/andreasg123/followers","following_url":"https://api.github.com/users/andreasg123/following{/other_user}","gists_url":"https://api.github.com/users/andreasg123/gists{/gist_id}","starred_url":"https://api.github.com/users/andreasg123/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andreasg123/subscriptions","organizations_url":"https://api.github.com/users/andreasg123/orgs","repos_url":"https://api.github.com/users/andreasg123/repos","events_url":"https://api.github.com/users/andreasg123/events{/privacy}","received_events_url":"https://api.github.com/users/andreasg123/received_events","type":"User","site_admin":false},"repo":{"id":202937075,"node_id":"MDEwOlJlcG9zaXRvcnkyMDI5MzcwNzU=","name":"CSparse.NET","full_name":"andreasg123/CSparse.NET","private":false,"owner":{"login":"andreasg123","id":15636985,"node_id":"MDQ6VXNlcjE1NjM2OTg1","avatar_url":"https://avatars2.githubusercontent.com/u/15636985?v=4","gravatar_id":"","url":"https://api.github.com/users/andreasg123","html_url":"https://github.com/andreasg123","followers_url":"https://api.github.com/users/andreasg123/followers","following_url":"https://api.github.com/users/andreasg123/following{/other_user}","gists_url":"https://api.github.com/users/andreasg123/gists{/gist_id}","starred_url":"https://api.github.com/users/andreasg123/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andreasg123/subscriptions","organizations_url":"https://api.github.com/users/andreasg123/orgs","repos_url":"https://api.github.com/users/andreasg123/repos","events_url":"https://api.github.com/users/andreasg123/events{/privacy}","received_events_url":"https://api.github.com/users/andreasg123/received_events","type":"User","site_admin":false},"html_url":"https://github.com/andreasg123/CSparse.NET","description":"A concise library for solving sparse linear systems with direct methods.","fork":true,"url":"https://api.github.com/repos/andreasg123/CSparse.NET","forks_url":"https://api.github.com/repos/andreasg123/CSparse.NET/forks","keys_url":"https://api.github.com/repos/andreasg123/CSparse.NET/keys{/key_id}","collaborators_url":"https://api.github.com/repos/andreasg123/CSparse.NET/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/andreasg123/CSparse.NET/teams","hooks_url":"https://api.github.com/repos/andreasg123/CSparse.NET/hooks","issue_events_url":"https://api.github.com/repos/andreasg123/CSparse.NET/issues/events{/number}","events_url":"https://api.github.com/repos/andreasg123/CSparse.NET/events","assignees_url":"https://api.github.com/repos/andreasg123/CSparse.NET/assignees{/user}","branches_url":"https://api.github.com/repos/andreasg123/CSparse.NET/branches{/branch}","tags_url":"https://api.github.com/repos/andreasg123/CSparse.NET/tags","blobs_url":"https://api.github.com/repos/andreasg123/CSparse.NET/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/andreasg123/CSparse.NET/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/andreasg123/CSparse.NET/git/refs{/sha}","trees_url":"https://api.github.com/repos/andreasg123/CSparse.NET/git/trees{/sha}","statuses_url":"https://api.github.com/repos/andreasg123/CSparse.NET/statuses/{sha}","languages_url":"https://api.github.com/repos/andreasg123/CSparse.NET/languages","stargazers_url":"https://api.github.com/repos/andreasg123/CSparse.NET/stargazers","contributors_url":"https://api.github.com/repos/andreasg123/CSparse.NET/contributors","subscribers_url":"https://api.github.com/repos/andreasg123/CSparse.NET/subscribers","subscription_url":"https://api.github.com/repos/andreasg123/CSparse.NET/subscription","commits_url":"https://api.github.com/repos/andreasg123/CSparse.NET/commits{/sha}","git_commits_url":"https://api.github.com/repos/andreasg123/CSparse.NET/git/commits{/sha}","comments_url":"https://api.github.com/repos/andreasg123/CSparse.NET/comments{/number}","issue_comment_url":"https://api.github.com/repos/andreasg123/CSparse.NET/issues/comments{/number}","contents_url":"https://api.github.com/repos/andreasg123/CSparse.NET/contents/{+path}","compare_url":"https://api.github.com/repos/andreasg123/CSparse.NET/compare/{base}...{head}","merges_url":"https://api.github.com/repos/andreasg123/CSparse.NET/merges","archive_url":"https://api.github.com/repos/andreasg123/CSparse.NET/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/andreasg123/CSparse.NET/downloads","issues_url":"https://api.github.com/repos/andreasg123/CSparse.NET/issues{/number}","pulls_url":"https://api.github.com/repos/andreasg123/CSparse.NET/pulls{/number}","milestones_url":"https://api.github.com/repos/andreasg123/CSparse.NET/milestones{/number}","notifications_url":"https://api.github.com/repos/andreasg123/CSparse.NET/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/andreasg123/CSparse.NET/labels{/name}","releases_url":"https://api.github.com/repos/andreasg123/CSparse.NET/releases{/id}","deployments_url":"https://api.github.com/repos/andreasg123/CSparse.NET/deployments","created_at":"2019-08-17T22:35:07Z","updated_at":"2019-08-17T22:35:09Z","pushed_at":"2019-08-18T19:47:13Z","git_url":"git://github.com/andreasg123/CSparse.NET.git","ssh_url":"git@github.com:andreasg123/CSparse.NET.git","clone_url":"https://github.com/andreasg123/CSparse.NET.git","svn_url":"https://github.com/andreasg123/CSparse.NET","homepage":null,"size":268,"stargazers_count":0,"watchers_count":0,"language":"C#","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"disabled":false,"open_issues_count":0,"license":{"key":"lgpl-2.1","name":"GNU Lesser General Public License v2.1","spdx_id":"LGPL-2.1","url":"https://api.github.com/licenses/lgpl-2.1","node_id":"MDc6TGljZW5zZTEx"},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"wo80:master","ref":"master","sha":"6777851b4c771c0dfc99b9c13d26c507a3a90da4","user":{"login":"wo80","id":1840402,"node_id":"MDQ6VXNlcjE4NDA0MDI=","avatar_url":"https://avatars0.githubusercontent.com/u/1840402?v=4","gravatar_id":"","url":"https://api.github.com/users/wo80","html_url":"https://github.com/wo80","followers_url":"https://api.github.com/users/wo80/followers","following_url":"https://api.github.com/users/wo80/following{/other_user}","gists_url":"https://api.github.com/users/wo80/gists{/gist_id}","starred_url":"https://api.github.com/users/wo80/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wo80/subscriptions","organizations_url":"https://api.github.com/users/wo80/orgs","repos_url":"https://api.github.com/users/wo80/repos","events_url":"https://api.github.com/users/wo80/events{/privacy}","received_events_url":"https://api.github.com/users/wo80/received_events","type":"User","site_admin":false},"repo":{"id":37058313,"node_id":"MDEwOlJlcG9zaXRvcnkzNzA1ODMxMw==","name":"CSparse.NET","full_name":"wo80/CSparse.NET","private":false,"owner":{"login":"wo80","id":1840402,"node_id":"MDQ6VXNlcjE4NDA0MDI=","avatar_url":"https://avatars0.githubusercontent.com/u/1840402?v=4","gravatar_id":"","url":"https://api.github.com/users/wo80","html_url":"https://github.com/wo80","followers_url":"https://api.github.com/users/wo80/followers","following_url":"https://api.github.com/users/wo80/following{/other_user}","gists_url":"https://api.github.com/users/wo80/gists{/gist_id}","starred_url":"https://api.github.com/users/wo80/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wo80/subscriptions","organizations_url":"https://api.github.com/users/wo80/orgs","repos_url":"https://api.github.com/users/wo80/repos","events_url":"https://api.github.com/users/wo80/events{/privacy}","received_events_url":"https://api.github.com/users/wo80/received_events","type":"User","site_admin":false},"html_url":"https://github.com/wo80/CSparse.NET","description":"A concise library for solving sparse linear systems with direct methods.","fork":false,"url":"https://api.github.com/repos/wo80/CSparse.NET","forks_url":"https://api.github.com/repos/wo80/CSparse.NET/forks","keys_url":"https://api.github.com/repos/wo80/CSparse.NET/keys{/key_id}","collaborators_url":"https://api.github.com/repos/wo80/CSparse.NET/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/wo80/CSparse.NET/teams","hooks_url":"https://api.github.com/repos/wo80/CSparse.NET/hooks","issue_events_url":"https://api.github.com/repos/wo80/CSparse.NET/issues/events{/number}","events_url":"https://api.github.com/repos/wo80/CSparse.NET/events","assignees_url":"https://api.github.com/repos/wo80/CSparse.NET/assignees{/user}","branches_url":"https://api.github.com/repos/wo80/CSparse.NET/branches{/branch}","tags_url":"https://api.github.com/repos/wo80/CSparse.NET/tags","blobs_url":"https://api.github.com/repos/wo80/CSparse.NET/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/wo80/CSparse.NET/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/wo80/CSparse.NET/git/refs{/sha}","trees_url":"https://api.github.com/repos/wo80/CSparse.NET/git/trees{/sha}","statuses_url":"https://api.github.com/repos/wo80/CSparse.NET/statuses/{sha}","languages_url":"https://api.github.com/repos/wo80/CSparse.NET/languages","stargazers_url":"https://api.github.com/repos/wo80/CSparse.NET/stargazers","contributors_url":"https://api.github.com/repos/wo80/CSparse.NET/contributors","subscribers_url":"https://api.github.com/repos/wo80/CSparse.NET/subscribers","subscription_url":"https://api.github.com/repos/wo80/CSparse.NET/subscription","commits_url":"https://api.github.com/repos/wo80/CSparse.NET/commits{/sha}","git_commits_url":"https://api.github.com/repos/wo80/CSparse.NET/git/commits{/sha}","comments_url":"https://api.github.com/repos/wo80/CSparse.NET/comments{/number}","issue_comment_url":"https://api.github.com/repos/wo80/CSparse.NET/issues/comments{/number}","contents_url":"https://api.github.com/repos/wo80/CSparse.NET/contents/{+path}","compare_url":"https://api.github.com/repos/wo80/CSparse.NET/compare/{base}...{head}","merges_url":"https://api.github.com/repos/wo80/CSparse.NET/merges","archive_url":"https://api.github.com/repos/wo80/CSparse.NET/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/wo80/CSparse.NET/downloads","issues_url":"https://api.github.com/repos/wo80/CSparse.NET/issues{/number}","pulls_url":"https://api.github.com/repos/wo80/CSparse.NET/pulls{/number}","milestones_url":"https://api.github.com/repos/wo80/CSparse.NET/milestones{/number}","notifications_url":"https://api.github.com/repos/wo80/CSparse.NET/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/wo80/CSparse.NET/labels{/name}","releases_url":"https://api.github.com/repos/wo80/CSparse.NET/releases{/id}","deployments_url":"https://api.github.com/repos/wo80/CSparse.NET/deployments","created_at":"2015-06-08T09:38:41Z","updated_at":"2019-07-09T13:37:53Z","pushed_at":"2019-08-18T19:47:14Z","git_url":"git://github.com/wo80/CSparse.NET.git","ssh_url":"git@github.com:wo80/CSparse.NET.git","clone_url":"https://github.com/wo80/CSparse.NET.git","svn_url":"https://github.com/wo80/CSparse.NET","homepage":null,"size":267,"stargazers_count":18,"watchers_count":18,"language":"C#","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":9,"mirror_url":null,"archived":false,"disabled":false,"open_issues_count":4,"license":{"key":"lgpl-2.1","name":"GNU Lesser General Public License v2.1","spdx_id":"LGPL-2.1","url":"https://api.github.com/licenses/lgpl-2.1","node_id":"MDc6TGljZW5zZTEx"},"forks":9,"open_issues":4,"watchers":18,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18"},"html":{"href":"https://github.com/wo80/CSparse.NET/pull/18"},"issue":{"href":"https://api.github.com/repos/wo80/CSparse.NET/issues/18"},"comments":{"href":"https://api.github.com/repos/wo80/CSparse.NET/issues/18/comments"},"review_comments":{"href":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18/comments"},"review_comment":{"href":"https://api.github.com/repos/wo80/CSparse.NET/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/wo80/CSparse.NET/pulls/18/commits"},"statuses":{"href":"https://api.github.com/repos/wo80/CSparse.NET/statuses/4e401e9de95e7640ad5ade1d639d562bf01aca9b"}},"author_association":"NONE"}}
other: {"actor":{"display_login":"andreasg123"}}