{"action":"closed","number":94,"pull_request":{"url":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/94","id":94706436,"html_url":"https://github.com/AtheMathmo/rulinalg/pull/94","diff_url":"https://github.com/AtheMathmo/rulinalg/pull/94.diff","patch_url":"https://github.com/AtheMathmo/rulinalg/pull/94.patch","issue_url":"https://api.github.com/repos/AtheMathmo/rulinalg/issues/94","number":94,"state":"closed","locked":false,"title":"LU rewrite, first draft","user":{"login":"Andlon","id":578309,"avatar_url":"https://avatars.githubusercontent.com/u/578309?v=3","gravatar_id":"","url":"https://api.github.com/users/Andlon","html_url":"https://github.com/Andlon","followers_url":"https://api.github.com/users/Andlon/followers","following_url":"https://api.github.com/users/Andlon/following{/other_user}","gists_url":"https://api.github.com/users/Andlon/gists{/gist_id}","starred_url":"https://api.github.com/users/Andlon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Andlon/subscriptions","organizations_url":"https://api.github.com/users/Andlon/orgs","repos_url":"https://api.github.com/users/Andlon/repos","events_url":"https://api.github.com/users/Andlon/events{/privacy}","received_events_url":"https://api.github.com/users/Andlon/received_events","type":"User","site_admin":false},"body":"This is by no means finished, but I wanted to give contributors an opportunity to weigh in with some opinions, if anyone wants to.\r\n\r\nIn line with some of the ideas discussed in #40, I've recently started to put together a redesign of the LU decomposition. If we reach concencus on the ideas put forth, I plan to do a similar redesign of the other decompositions.\r\n\r\nCurrently, the LU(P) decomposition as implemented in `rulinalg` simply returns a triplet of the three matrices `L`, `U` and `P`. One of the strengths of the LU decomposition, is that once decomposed, one can very efficiently solve many linear systems `Ax = b` where the matrix `A` is constant, but `b` varies. It would thus be convenient if this functionality was readily available and optimized through rulinalg's API. Thus, I propose to instead let the decomposition return a specialized type that makes this operation easier.\r\n\r\nIn addition, returning all three matrices is not optimal in terms of storage space. In particular, one can store the L and U matrices in the space of a single matrix, rather than two separate matrices, halving the memory costs. This is not yet implemented in this PR, but it's possible to implement without breaking changes.\r\n\r\nFinally, I want to implement a custom `PermutationMatrix` structure. Currently the permutation matrix is returned as a full `Matrix<T>`, but by its nature, a permutation matrix needs only `O(n)` storage, and it can be applied much more efficiently than performing a full matrix-matrix or matrix-vector application. This is also not yet implemented in this PR.\r\n\r\nI've also made one more important change: for whatever reason, the LUP decomposition that is currently implemented fails if the matrix is singular. However, there always exists an LUP decomposition for _any_ square matrix, so I've taken this into account, and as such we no longer need to return a `Result` for the decomposition itself.\r\n\r\nIn short, we currently write:\r\n```rust\r\nlet a: Matrix<T> = ...;\r\n// Perform LUP decomp in O(n^3) operations\r\nlet (l, u, p) = a.lup_decomp().expect(\"Should work?\");\r\n\r\n// Solving Ax = b in O(n^2) operations with the LU decomposition\r\n// is somewhat convoluted\r\nlet y = l.solve_l_triangular(P * b).expect(\"Matrix is invertible\")\r\nlet x = u.solve_u_triangular(y).expect(\"Matrix is invertible\");\r\n```\r\n\r\nWith the proposed changes, we have instead:\r\n\r\n```rust\r\nlet a: Matrix<T> = ...;\r\n// Consumes the matrix and returns an opaque decomposition object\r\n// in O(n^3) operations\r\nlet lu = a.lu();\r\n\r\n// Solve Ax = b in O(n^2) operations. The details of the operation are\r\n// conveniently abstracted away from the user, and we can heavily\r\n// optimize it if need be.\r\nlet x = lu.solve(b).expect(\"Matrix is invertible\");\r\n\r\n// Can compute determinant in O(n) operations\r\nlet det = lu.det();\r\n\r\n// Finally, can consume the decomposition to obtain\r\n// the individual matrices\r\nlet LU { l, u, p } = lu.decompose();\r\n```\r\n\r\nNote the last line in the previous example. I've explicitly avoided returning a triplet here, because it's very easy to mess up the order. In rulinalg we have (l, u, p), but i.e. NumPy returns (p, l, u). I even made this mistake once when working with the previous API. These sort of errors can be very frustrating if they are not quickly discovered! Of course, with the above struct deconstructing API, the call is order-independent, so the last line could have been replaced with `LU { p, l, u }` or `LU { u, p, l }` without having any effect on the behavior of the code.","created_at":"2016-11-21T22:06:01Z","updated_at":"2017-01-30T22:06:13Z","closed_at":"2017-01-30T22:06:13Z","merged_at":null,"merge_commit_sha":"d6347b15a4ff3287bc951bbaa4c870dc021bf624","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/94/commits","review_comments_url":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/94/comments","review_comment_url":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/comments{/number}","comments_url":"https://api.github.com/repos/AtheMathmo/rulinalg/issues/94/comments","statuses_url":"https://api.github.com/repos/AtheMathmo/rulinalg/statuses/4f3b156bb30f29d83b76890624fad83d467b7544","head":{"label":"Andlon:lu_rewrite","ref":"lu_rewrite","sha":"4f3b156bb30f29d83b76890624fad83d467b7544","user":{"login":"Andlon","id":578309,"avatar_url":"https://avatars.githubusercontent.com/u/578309?v=3","gravatar_id":"","url":"https://api.github.com/users/Andlon","html_url":"https://github.com/Andlon","followers_url":"https://api.github.com/users/Andlon/followers","following_url":"https://api.github.com/users/Andlon/following{/other_user}","gists_url":"https://api.github.com/users/Andlon/gists{/gist_id}","starred_url":"https://api.github.com/users/Andlon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Andlon/subscriptions","organizations_url":"https://api.github.com/users/Andlon/orgs","repos_url":"https://api.github.com/users/Andlon/repos","events_url":"https://api.github.com/users/Andlon/events{/privacy}","received_events_url":"https://api.github.com/users/Andlon/received_events","type":"User","site_admin":false},"repo":{"id":68537005,"name":"rulinalg","full_name":"Andlon/rulinalg","owner":{"login":"Andlon","id":578309,"avatar_url":"https://avatars.githubusercontent.com/u/578309?v=3","gravatar_id":"","url":"https://api.github.com/users/Andlon","html_url":"https://github.com/Andlon","followers_url":"https://api.github.com/users/Andlon/followers","following_url":"https://api.github.com/users/Andlon/following{/other_user}","gists_url":"https://api.github.com/users/Andlon/gists{/gist_id}","starred_url":"https://api.github.com/users/Andlon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Andlon/subscriptions","organizations_url":"https://api.github.com/users/Andlon/orgs","repos_url":"https://api.github.com/users/Andlon/repos","events_url":"https://api.github.com/users/Andlon/events{/privacy}","received_events_url":"https://api.github.com/users/Andlon/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Andlon/rulinalg","description":"A linear algebra library in Rust designed for machine learning","fork":true,"url":"https://api.github.com/repos/Andlon/rulinalg","forks_url":"https://api.github.com/repos/Andlon/rulinalg/forks","keys_url":"https://api.github.com/repos/Andlon/rulinalg/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Andlon/rulinalg/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Andlon/rulinalg/teams","hooks_url":"https://api.github.com/repos/Andlon/rulinalg/hooks","issue_events_url":"https://api.github.com/repos/Andlon/rulinalg/issues/events{/number}","events_url":"https://api.github.com/repos/Andlon/rulinalg/events","assignees_url":"https://api.github.com/repos/Andlon/rulinalg/assignees{/user}","branches_url":"https://api.github.com/repos/Andlon/rulinalg/branches{/branch}","tags_url":"https://api.github.com/repos/Andlon/rulinalg/tags","blobs_url":"https://api.github.com/repos/Andlon/rulinalg/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Andlon/rulinalg/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Andlon/rulinalg/git/refs{/sha}","trees_url":"https://api.github.com/repos/Andlon/rulinalg/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Andlon/rulinalg/statuses/{sha}","languages_url":"https://api.github.com/repos/Andlon/rulinalg/languages","stargazers_url":"https://api.github.com/repos/Andlon/rulinalg/stargazers","contributors_url":"https://api.github.com/repos/Andlon/rulinalg/contributors","subscribers_url":"https://api.github.com/repos/Andlon/rulinalg/subscribers","subscription_url":"https://api.github.com/repos/Andlon/rulinalg/subscription","commits_url":"https://api.github.com/repos/Andlon/rulinalg/commits{/sha}","git_commits_url":"https://api.github.com/repos/Andlon/rulinalg/git/commits{/sha}","comments_url":"https://api.github.com/repos/Andlon/rulinalg/comments{/number}","issue_comment_url":"https://api.github.com/repos/Andlon/rulinalg/issues/comments{/number}","contents_url":"https://api.github.com/repos/Andlon/rulinalg/contents/{+path}","compare_url":"https://api.github.com/repos/Andlon/rulinalg/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Andlon/rulinalg/merges","archive_url":"https://api.github.com/repos/Andlon/rulinalg/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Andlon/rulinalg/downloads","issues_url":"https://api.github.com/repos/Andlon/rulinalg/issues{/number}","pulls_url":"https://api.github.com/repos/Andlon/rulinalg/pulls{/number}","milestones_url":"https://api.github.com/repos/Andlon/rulinalg/milestones{/number}","notifications_url":"https://api.github.com/repos/Andlon/rulinalg/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Andlon/rulinalg/labels{/name}","releases_url":"https://api.github.com/repos/Andlon/rulinalg/releases{/id}","deployments_url":"https://api.github.com/repos/Andlon/rulinalg/deployments","created_at":"2016-09-18T17:41:10Z","updated_at":"2016-09-18T17:41:11Z","pushed_at":"2017-01-30T21:53:06Z","git_url":"git://github.com/Andlon/rulinalg.git","ssh_url":"git@github.com:Andlon/rulinalg.git","clone_url":"https://github.com/Andlon/rulinalg.git","svn_url":"https://github.com/Andlon/rulinalg","homepage":"https://crates.io/crates/rulinalg","size":1486,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"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":"AtheMathmo:master","ref":"master","sha":"9b55e26ab34219d5c4de249af667ed9908c9b0ff","user":{"login":"AtheMathmo","id":10150986,"avatar_url":"https://avatars.githubusercontent.com/u/10150986?v=3","gravatar_id":"","url":"https://api.github.com/users/AtheMathmo","html_url":"https://github.com/AtheMathmo","followers_url":"https://api.github.com/users/AtheMathmo/followers","following_url":"https://api.github.com/users/AtheMathmo/following{/other_user}","gists_url":"https://api.github.com/users/AtheMathmo/gists{/gist_id}","starred_url":"https://api.github.com/users/AtheMathmo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AtheMathmo/subscriptions","organizations_url":"https://api.github.com/users/AtheMathmo/orgs","repos_url":"https://api.github.com/users/AtheMathmo/repos","events_url":"https://api.github.com/users/AtheMathmo/events{/privacy}","received_events_url":"https://api.github.com/users/AtheMathmo/received_events","type":"User","site_admin":false},"repo":{"id":62955795,"name":"rulinalg","full_name":"AtheMathmo/rulinalg","owner":{"login":"AtheMathmo","id":10150986,"avatar_url":"https://avatars.githubusercontent.com/u/10150986?v=3","gravatar_id":"","url":"https://api.github.com/users/AtheMathmo","html_url":"https://github.com/AtheMathmo","followers_url":"https://api.github.com/users/AtheMathmo/followers","following_url":"https://api.github.com/users/AtheMathmo/following{/other_user}","gists_url":"https://api.github.com/users/AtheMathmo/gists{/gist_id}","starred_url":"https://api.github.com/users/AtheMathmo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AtheMathmo/subscriptions","organizations_url":"https://api.github.com/users/AtheMathmo/orgs","repos_url":"https://api.github.com/users/AtheMathmo/repos","events_url":"https://api.github.com/users/AtheMathmo/events{/privacy}","received_events_url":"https://api.github.com/users/AtheMathmo/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/AtheMathmo/rulinalg","description":"A linear algebra library in Rust designed for machine learning","fork":false,"url":"https://api.github.com/repos/AtheMathmo/rulinalg","forks_url":"https://api.github.com/repos/AtheMathmo/rulinalg/forks","keys_url":"https://api.github.com/repos/AtheMathmo/rulinalg/keys{/key_id}","collaborators_url":"https://api.github.com/repos/AtheMathmo/rulinalg/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/AtheMathmo/rulinalg/teams","hooks_url":"https://api.github.com/repos/AtheMathmo/rulinalg/hooks","issue_events_url":"https://api.github.com/repos/AtheMathmo/rulinalg/issues/events{/number}","events_url":"https://api.github.com/repos/AtheMathmo/rulinalg/events","assignees_url":"https://api.github.com/repos/AtheMathmo/rulinalg/assignees{/user}","branches_url":"https://api.github.com/repos/AtheMathmo/rulinalg/branches{/branch}","tags_url":"https://api.github.com/repos/AtheMathmo/rulinalg/tags","blobs_url":"https://api.github.com/repos/AtheMathmo/rulinalg/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/AtheMathmo/rulinalg/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/AtheMathmo/rulinalg/git/refs{/sha}","trees_url":"https://api.github.com/repos/AtheMathmo/rulinalg/git/trees{/sha}","statuses_url":"https://api.github.com/repos/AtheMathmo/rulinalg/statuses/{sha}","languages_url":"https://api.github.com/repos/AtheMathmo/rulinalg/languages","stargazers_url":"https://api.github.com/repos/AtheMathmo/rulinalg/stargazers","contributors_url":"https://api.github.com/repos/AtheMathmo/rulinalg/contributors","subscribers_url":"https://api.github.com/repos/AtheMathmo/rulinalg/subscribers","subscription_url":"https://api.github.com/repos/AtheMathmo/rulinalg/subscription","commits_url":"https://api.github.com/repos/AtheMathmo/rulinalg/commits{/sha}","git_commits_url":"https://api.github.com/repos/AtheMathmo/rulinalg/git/commits{/sha}","comments_url":"https://api.github.com/repos/AtheMathmo/rulinalg/comments{/number}","issue_comment_url":"https://api.github.com/repos/AtheMathmo/rulinalg/issues/comments{/number}","contents_url":"https://api.github.com/repos/AtheMathmo/rulinalg/contents/{+path}","compare_url":"https://api.github.com/repos/AtheMathmo/rulinalg/compare/{base}...{head}","merges_url":"https://api.github.com/repos/AtheMathmo/rulinalg/merges","archive_url":"https://api.github.com/repos/AtheMathmo/rulinalg/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/AtheMathmo/rulinalg/downloads","issues_url":"https://api.github.com/repos/AtheMathmo/rulinalg/issues{/number}","pulls_url":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls{/number}","milestones_url":"https://api.github.com/repos/AtheMathmo/rulinalg/milestones{/number}","notifications_url":"https://api.github.com/repos/AtheMathmo/rulinalg/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/AtheMathmo/rulinalg/labels{/name}","releases_url":"https://api.github.com/repos/AtheMathmo/rulinalg/releases{/id}","deployments_url":"https://api.github.com/repos/AtheMathmo/rulinalg/deployments","created_at":"2016-07-09T15:27:53Z","updated_at":"2017-01-28T00:49:30Z","pushed_at":"2017-01-30T22:00:55Z","git_url":"git://github.com/AtheMathmo/rulinalg.git","ssh_url":"git@github.com:AtheMathmo/rulinalg.git","clone_url":"https://github.com/AtheMathmo/rulinalg.git","svn_url":"https://github.com/AtheMathmo/rulinalg","homepage":"https://crates.io/crates/rulinalg","size":1705,"stargazers_count":102,"watchers_count":102,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":24,"mirror_url":null,"open_issues_count":35,"forks":24,"open_issues":35,"watchers":102,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/94"},"html":{"href":"https://github.com/AtheMathmo/rulinalg/pull/94"},"issue":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/issues/94"},"comments":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/issues/94/comments"},"review_comments":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/94/comments"},"review_comment":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/pulls/94/commits"},"statuses":{"href":"https://api.github.com/repos/AtheMathmo/rulinalg/statuses/4f3b156bb30f29d83b76890624fad83d467b7544"}},"merged":false,"mergeable":false,"mergeable_state":"dirty","merged_by":null,"comments":17,"review_comments":8,"maintainer_can_modify":false,"commits":7,"additions":600,"deletions":79,"changed_files":8}}
{"actor":{"display_login":"Andlon"}}