{"action":"created","comment":{"url":"https://api.github.com/repos/gonum/matrix/pulls/comments/60423198","id":60423198,"diff_hunk":"@@ -178,3 +178,155 @@ func (s *SymDense) InverseCholesky(chol *Cholesky) error {\n \ts.SymOuterK(1, &t)\n \treturn err\n }\n+\n+// RankOne performs a rank-1 update (or downdate when alpha is negative) of the\n+// Cholesky factorization orig as if the update had been applied to the original\n+// matrix A, storing the result into the reciever. That is, if in the original\n+// Cholesky factorization\n+//  U^T * U = A,\n+// in the updated factorization\n+//  U'^T * U' = A + alpha * x * x^T = A'.\n+//\n+// Note that when alpha is negative, the downdating problem may be\n+// ill-conditioned and the results may be inaccurate, or the updated matrix A'\n+// may not be positive definite and not have a Cholesky factorization. RankOne\n+// returns whether the updated matrix A' is positive definite.\n+//\n+// The utility of RankOne comes from the fact that updating the factorization is\n+// an O(n²) algorithm while computing it from scratch is an O(n³) algorithm.\n+func (c *Cholesky) RankOne(orig *Cholesky, alpha float64, x *Vector) (ok bool) {\n+\tn := orig.Size()\n+\tif x.Len() != n {\n+\t\tpanic(matrix.ErrShape)\n+\t}\n+\tif orig != c {\n+\t\tif c.chol == nil {\n+\t\t\tc.chol = NewTriDense(n, matrix.Upper, nil)\n+\t\t} else if c.chol.mat.N != n {\n+\t\t\tpanic(matrix.ErrShape)\n+\t\t}\n+\t\tc.chol.Copy(orig.chol)\n+\t}\n+\n+\tif alpha == 0 {\n+\t\treturn true\n+\t}\n+\n+\t// Algorithms for updating and downdating the Cholesky factorization are\n+\t// described, for example, in\n+\t// - J. J. Dongarra, J. R. Bunch, C. B. Moler, G. W. Stewart: LINPACK\n+\t//   Users' Guide. SIAM (1979), pages 10.10--10.14\n+\t// or\n+\t// - P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders: Methods for\n+\t//   modifying matrix factorizations. Mathematics of Computation 28(126)\n+\t//   (1974), Method C3 on page 521\n+\t//\n+\t// The implementation is based on LINPACK code\n+\t// http://www.netlib.org/linpack/dchud.f\n+\t// http://www.netlib.org/linpack/dchdd.f\n+\t// and\n+\t// https://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=2646\n+\t//\n+\t// According to http://icl.cs.utk.edu/lapack-forum/archives/lapack/msg00301.html\n+\t// LINPACK is released under BSD license.\n+\t//\n+\t// See also:\n+\t// - M. A. Saunders: Large-scale Linear Programming Using the Cholesky\n+\t//   Factorization. Technical Report Stanford University (1972)\n+\t//   http://i.stanford.edu/pub/cstr/reports/cs/tr/72/252/CS-TR-72-252.pdf\n+\t// - Matthias Seeger: Low rank updates for the Cholesky decomposition.\n+\t//   EPFL Technical Report 161468 (2004)\n+\t//   http://infoscience.epfl.ch/record/161468\n+\n+\twork := make([]float64, n)\n+\tblas64.Copy(n, x.RawVector(), blas64.Vector{1, work})\n+\n+\tif alpha > 0 {\n+\t\t// Compute rank-1 update.\n+\n+\t\tblas64.Scal(n, math.Sqrt(alpha), blas64.Vector{1, work})\n+\t\tumat := c.chol.mat.Data\n+\t\tfor i := 0; i < n; i++ {\n+\t\t\t// Compute parameters of the Givens matrix that zeroes\n+\t\t\t// the i-th element of x.\n+\t\t\tc, s, r, _ := blas64.Rotg(umat[i*n+i], work[i])\n+\t\t\tif r < 0 {\n+\t\t\t\t// Multiply by -1 to have positive diagonal\n+\t\t\t\t// elemnts.\n+\t\t\t\tr *= -1\n+\t\t\t\tc *= -1\n+\t\t\t\ts *= -1\n+\t\t\t}\n+\t\t\tumat[i*n+i] = r\n+\t\t\tif i < n-1 {\n+\t\t\t\t// Multiply the extended factorization matrix by\n+\t\t\t\t// the Givens matrix from the left. Only\n+\t\t\t\t// the i-th row and x are modified.\n+\t\t\t\tblas64.Rot(n-i-1,\n+\t\t\t\t\tblas64.Vector{1, umat[i*n+i+1 : i*n+n]},\n+\t\t\t\t\tblas64.Vector{1, work[i+1 : n]},\n+\t\t\t\t\tc, s)\n+\t\t\t}\n+\t\t}\n+\t\tc.updateCond(-1)\n+\t\treturn true\n+\t}\n+\n+\t// Compute rank-1 downdate.\n+\n+\talpha = math.Sqrt(-alpha)\n+\tblas64.Scal(n, alpha, blas64.Vector{1, work})\n+\t// Solve U^T * p = x storing the result into work.\n+\tok = lapack64.Trtrs(blas.Trans, c.chol.RawTriangular(), blas64.General{\n+\t\tRows:   n,\n+\t\tCols:   1,\n+\t\tStride: 1,\n+\t\tData:   work,\n+\t})\n+\tif !ok {\n+\t\t// The original matrix is singular.","path":"mat64/cholesky.go","position":121,"original_position":110,"commit_id":"4609a7961ac5675493cc5c1523d9e624486c028b","original_commit_id":"c7571be3420f9946ddd902caf7f0d89fe3c73dab","user":{"login":"btracey","id":3680859,"avatar_url":"https://avatars.githubusercontent.com/u/3680859?v=3","gravatar_id":"","url":"https://api.github.com/users/btracey","html_url":"https://github.com/btracey","followers_url":"https://api.github.com/users/btracey/followers","following_url":"https://api.github.com/users/btracey/following{/other_user}","gists_url":"https://api.github.com/users/btracey/gists{/gist_id}","starred_url":"https://api.github.com/users/btracey/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/btracey/subscriptions","organizations_url":"https://api.github.com/users/btracey/orgs","repos_url":"https://api.github.com/users/btracey/repos","events_url":"https://api.github.com/users/btracey/events{/privacy}","received_events_url":"https://api.github.com/users/btracey/received_events","type":"User","site_admin":false},"body":"https://github.com/gonum/matrix/issues/377","created_at":"2016-04-20T14:56:40Z","updated_at":"2016-04-20T14:56:40Z","html_url":"https://github.com/gonum/matrix/pull/376#discussion_r60423198","pull_request_url":"https://api.github.com/repos/gonum/matrix/pulls/376","_links":{"self":{"href":"https://api.github.com/repos/gonum/matrix/pulls/comments/60423198"},"html":{"href":"https://github.com/gonum/matrix/pull/376#discussion_r60423198"},"pull_request":{"href":"https://api.github.com/repos/gonum/matrix/pulls/376"}}},"pull_request":{"url":"https://api.github.com/repos/gonum/matrix/pulls/376","id":66959274,"html_url":"https://github.com/gonum/matrix/pull/376","diff_url":"https://github.com/gonum/matrix/pull/376.diff","patch_url":"https://github.com/gonum/matrix/pull/376.patch","issue_url":"https://api.github.com/repos/gonum/matrix/issues/376","number":376,"state":"open","locked":false,"title":"mat64: add Cholesky.SymRankOne","user":{"login":"vladimir-ch","id":1837502,"avatar_url":"https://avatars.githubusercontent.com/u/1837502?v=3","gravatar_id":"","url":"https://api.github.com/users/vladimir-ch","html_url":"https://github.com/vladimir-ch","followers_url":"https://api.github.com/users/vladimir-ch/followers","following_url":"https://api.github.com/users/vladimir-ch/following{/other_user}","gists_url":"https://api.github.com/users/vladimir-ch/gists{/gist_id}","starred_url":"https://api.github.com/users/vladimir-ch/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vladimir-ch/subscriptions","organizations_url":"https://api.github.com/users/vladimir-ch/orgs","repos_url":"https://api.github.com/users/vladimir-ch/repos","events_url":"https://api.github.com/users/vladimir-ch/events{/privacy}","received_events_url":"https://api.github.com/users/vladimir-ch/received_events","type":"User","site_admin":false},"body":"","created_at":"2016-04-19T04:36:38Z","updated_at":"2016-04-20T14:56:40Z","closed_at":null,"merged_at":null,"merge_commit_sha":"8fba07494fbbc136b64cf88128f754f43203979f","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/gonum/matrix/pulls/376/commits","review_comments_url":"https://api.github.com/repos/gonum/matrix/pulls/376/comments","review_comment_url":"https://api.github.com/repos/gonum/matrix/pulls/comments{/number}","comments_url":"https://api.github.com/repos/gonum/matrix/issues/376/comments","statuses_url":"https://api.github.com/repos/gonum/matrix/statuses/4609a7961ac5675493cc5c1523d9e624486c028b","head":{"label":"gonum:cholesky-rankone","ref":"cholesky-rankone","sha":"4609a7961ac5675493cc5c1523d9e624486c028b","user":{"login":"gonum","id":3771091,"avatar_url":"https://avatars.githubusercontent.com/u/3771091?v=3","gravatar_id":"","url":"https://api.github.com/users/gonum","html_url":"https://github.com/gonum","followers_url":"https://api.github.com/users/gonum/followers","following_url":"https://api.github.com/users/gonum/following{/other_user}","gists_url":"https://api.github.com/users/gonum/gists{/gist_id}","starred_url":"https://api.github.com/users/gonum/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gonum/subscriptions","organizations_url":"https://api.github.com/users/gonum/orgs","repos_url":"https://api.github.com/users/gonum/repos","events_url":"https://api.github.com/users/gonum/events{/privacy}","received_events_url":"https://api.github.com/users/gonum/received_events","type":"Organization","site_admin":false},"repo":{"id":8569918,"name":"matrix","full_name":"gonum/matrix","owner":{"login":"gonum","id":3771091,"avatar_url":"https://avatars.githubusercontent.com/u/3771091?v=3","gravatar_id":"","url":"https://api.github.com/users/gonum","html_url":"https://github.com/gonum","followers_url":"https://api.github.com/users/gonum/followers","following_url":"https://api.github.com/users/gonum/following{/other_user}","gists_url":"https://api.github.com/users/gonum/gists{/gist_id}","starred_url":"https://api.github.com/users/gonum/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gonum/subscriptions","organizations_url":"https://api.github.com/users/gonum/orgs","repos_url":"https://api.github.com/users/gonum/repos","events_url":"https://api.github.com/users/gonum/events{/privacy}","received_events_url":"https://api.github.com/users/gonum/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/gonum/matrix","description":"Matrix packages for the Go language.","fork":false,"url":"https://api.github.com/repos/gonum/matrix","forks_url":"https://api.github.com/repos/gonum/matrix/forks","keys_url":"https://api.github.com/repos/gonum/matrix/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gonum/matrix/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gonum/matrix/teams","hooks_url":"https://api.github.com/repos/gonum/matrix/hooks","issue_events_url":"https://api.github.com/repos/gonum/matrix/issues/events{/number}","events_url":"https://api.github.com/repos/gonum/matrix/events","assignees_url":"https://api.github.com/repos/gonum/matrix/assignees{/user}","branches_url":"https://api.github.com/repos/gonum/matrix/branches{/branch}","tags_url":"https://api.github.com/repos/gonum/matrix/tags","blobs_url":"https://api.github.com/repos/gonum/matrix/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gonum/matrix/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gonum/matrix/git/refs{/sha}","trees_url":"https://api.github.com/repos/gonum/matrix/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gonum/matrix/statuses/{sha}","languages_url":"https://api.github.com/repos/gonum/matrix/languages","stargazers_url":"https://api.github.com/repos/gonum/matrix/stargazers","contributors_url":"https://api.github.com/repos/gonum/matrix/contributors","subscribers_url":"https://api.github.com/repos/gonum/matrix/subscribers","subscription_url":"https://api.github.com/repos/gonum/matrix/subscription","commits_url":"https://api.github.com/repos/gonum/matrix/commits{/sha}","git_commits_url":"https://api.github.com/repos/gonum/matrix/git/commits{/sha}","comments_url":"https://api.github.com/repos/gonum/matrix/comments{/number}","issue_comment_url":"https://api.github.com/repos/gonum/matrix/issues/comments{/number}","contents_url":"https://api.github.com/repos/gonum/matrix/contents/{+path}","compare_url":"https://api.github.com/repos/gonum/matrix/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gonum/matrix/merges","archive_url":"https://api.github.com/repos/gonum/matrix/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gonum/matrix/downloads","issues_url":"https://api.github.com/repos/gonum/matrix/issues{/number}","pulls_url":"https://api.github.com/repos/gonum/matrix/pulls{/number}","milestones_url":"https://api.github.com/repos/gonum/matrix/milestones{/number}","notifications_url":"https://api.github.com/repos/gonum/matrix/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gonum/matrix/labels{/name}","releases_url":"https://api.github.com/repos/gonum/matrix/releases{/id}","deployments_url":"https://api.github.com/repos/gonum/matrix/deployments","created_at":"2013-03-05T01:59:12Z","updated_at":"2016-04-17T10:26:22Z","pushed_at":"2016-04-20T05:05:46Z","git_url":"git://github.com/gonum/matrix.git","ssh_url":"git@github.com:gonum/matrix.git","clone_url":"https://github.com/gonum/matrix.git","svn_url":"https://github.com/gonum/matrix","homepage":"","size":1122,"stargazers_count":245,"watchers_count":245,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":36,"mirror_url":null,"open_issues_count":17,"forks":36,"open_issues":17,"watchers":245,"default_branch":"master"}},"base":{"label":"gonum:master","ref":"master","sha":"859f0a9ae83d693aa0781e378051f0b4df3612bf","user":{"login":"gonum","id":3771091,"avatar_url":"https://avatars.githubusercontent.com/u/3771091?v=3","gravatar_id":"","url":"https://api.github.com/users/gonum","html_url":"https://github.com/gonum","followers_url":"https://api.github.com/users/gonum/followers","following_url":"https://api.github.com/users/gonum/following{/other_user}","gists_url":"https://api.github.com/users/gonum/gists{/gist_id}","starred_url":"https://api.github.com/users/gonum/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gonum/subscriptions","organizations_url":"https://api.github.com/users/gonum/orgs","repos_url":"https://api.github.com/users/gonum/repos","events_url":"https://api.github.com/users/gonum/events{/privacy}","received_events_url":"https://api.github.com/users/gonum/received_events","type":"Organization","site_admin":false},"repo":{"id":8569918,"name":"matrix","full_name":"gonum/matrix","owner":{"login":"gonum","id":3771091,"avatar_url":"https://avatars.githubusercontent.com/u/3771091?v=3","gravatar_id":"","url":"https://api.github.com/users/gonum","html_url":"https://github.com/gonum","followers_url":"https://api.github.com/users/gonum/followers","following_url":"https://api.github.com/users/gonum/following{/other_user}","gists_url":"https://api.github.com/users/gonum/gists{/gist_id}","starred_url":"https://api.github.com/users/gonum/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gonum/subscriptions","organizations_url":"https://api.github.com/users/gonum/orgs","repos_url":"https://api.github.com/users/gonum/repos","events_url":"https://api.github.com/users/gonum/events{/privacy}","received_events_url":"https://api.github.com/users/gonum/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/gonum/matrix","description":"Matrix packages for the Go language.","fork":false,"url":"https://api.github.com/repos/gonum/matrix","forks_url":"https://api.github.com/repos/gonum/matrix/forks","keys_url":"https://api.github.com/repos/gonum/matrix/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gonum/matrix/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gonum/matrix/teams","hooks_url":"https://api.github.com/repos/gonum/matrix/hooks","issue_events_url":"https://api.github.com/repos/gonum/matrix/issues/events{/number}","events_url":"https://api.github.com/repos/gonum/matrix/events","assignees_url":"https://api.github.com/repos/gonum/matrix/assignees{/user}","branches_url":"https://api.github.com/repos/gonum/matrix/branches{/branch}","tags_url":"https://api.github.com/repos/gonum/matrix/tags","blobs_url":"https://api.github.com/repos/gonum/matrix/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gonum/matrix/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gonum/matrix/git/refs{/sha}","trees_url":"https://api.github.com/repos/gonum/matrix/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gonum/matrix/statuses/{sha}","languages_url":"https://api.github.com/repos/gonum/matrix/languages","stargazers_url":"https://api.github.com/repos/gonum/matrix/stargazers","contributors_url":"https://api.github.com/repos/gonum/matrix/contributors","subscribers_url":"https://api.github.com/repos/gonum/matrix/subscribers","subscription_url":"https://api.github.com/repos/gonum/matrix/subscription","commits_url":"https://api.github.com/repos/gonum/matrix/commits{/sha}","git_commits_url":"https://api.github.com/repos/gonum/matrix/git/commits{/sha}","comments_url":"https://api.github.com/repos/gonum/matrix/comments{/number}","issue_comment_url":"https://api.github.com/repos/gonum/matrix/issues/comments{/number}","contents_url":"https://api.github.com/repos/gonum/matrix/contents/{+path}","compare_url":"https://api.github.com/repos/gonum/matrix/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gonum/matrix/merges","archive_url":"https://api.github.com/repos/gonum/matrix/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gonum/matrix/downloads","issues_url":"https://api.github.com/repos/gonum/matrix/issues{/number}","pulls_url":"https://api.github.com/repos/gonum/matrix/pulls{/number}","milestones_url":"https://api.github.com/repos/gonum/matrix/milestones{/number}","notifications_url":"https://api.github.com/repos/gonum/matrix/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gonum/matrix/labels{/name}","releases_url":"https://api.github.com/repos/gonum/matrix/releases{/id}","deployments_url":"https://api.github.com/repos/gonum/matrix/deployments","created_at":"2013-03-05T01:59:12Z","updated_at":"2016-04-17T10:26:22Z","pushed_at":"2016-04-20T05:05:46Z","git_url":"git://github.com/gonum/matrix.git","ssh_url":"git@github.com:gonum/matrix.git","clone_url":"https://github.com/gonum/matrix.git","svn_url":"https://github.com/gonum/matrix","homepage":"","size":1122,"stargazers_count":245,"watchers_count":245,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":36,"mirror_url":null,"open_issues_count":17,"forks":36,"open_issues":17,"watchers":245,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/gonum/matrix/pulls/376"},"html":{"href":"https://github.com/gonum/matrix/pull/376"},"issue":{"href":"https://api.github.com/repos/gonum/matrix/issues/376"},"comments":{"href":"https://api.github.com/repos/gonum/matrix/issues/376/comments"},"review_comments":{"href":"https://api.github.com/repos/gonum/matrix/pulls/376/comments"},"review_comment":{"href":"https://api.github.com/repos/gonum/matrix/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/gonum/matrix/pulls/376/commits"},"statuses":{"href":"https://api.github.com/repos/gonum/matrix/statuses/4609a7961ac5675493cc5c1523d9e624486c028b"}}}}