{"action":"created","issue":{"url":"https://api.github.com/repos/pygae/clifford/issues/40","repository_url":"https://api.github.com/repos/pygae/clifford","labels_url":"https://api.github.com/repos/pygae/clifford/issues/40/labels{/name}","comments_url":"https://api.github.com/repos/pygae/clifford/issues/40/comments","events_url":"https://api.github.com/repos/pygae/clifford/issues/40/events","html_url":"https://github.com/pygae/clifford/issues/40","id":351176486,"node_id":"MDU6SXNzdWUzNTExNzY0ODY=","number":40,"title":"Support for Sparse Algebras ","user":{"login":"Stefan-Endres","id":8235072,"node_id":"MDQ6VXNlcjgyMzUwNzI=","avatar_url":"https://avatars2.githubusercontent.com/u/8235072?v=4","gravatar_id":"","url":"https://api.github.com/users/Stefan-Endres","html_url":"https://github.com/Stefan-Endres","followers_url":"https://api.github.com/users/Stefan-Endres/followers","following_url":"https://api.github.com/users/Stefan-Endres/following{/other_user}","gists_url":"https://api.github.com/users/Stefan-Endres/gists{/gist_id}","starred_url":"https://api.github.com/users/Stefan-Endres/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Stefan-Endres/subscriptions","organizations_url":"https://api.github.com/users/Stefan-Endres/orgs","repos_url":"https://api.github.com/users/Stefan-Endres/repos","events_url":"https://api.github.com/users/Stefan-Endres/events{/privacy}","received_events_url":"https://api.github.com/users/Stefan-Endres/received_events","type":"User","site_admin":false},"labels":[{"id":147467080,"node_id":"MDU6TGFiZWwxNDc0NjcwODA=","url":"https://api.github.com/repos/pygae/clifford/labels/enhancement","name":"enhancement","color":"84b6eb","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-08-16T12:05:53Z","updated_at":"2018-08-16T13:38:34Z","closed_at":null,"author_association":"NONE","body":"In certain high-dimensional applications we only make use a subspace of grades. For example the Cl(n) Clifford algebra grows in dimensionality by `O(2^n)` while a using only blades of grade `k = 1` and `k = n - 1` grows linearly by `O(2n)`.\r\n\r\nI wrote a quick naive implementation just to test initiation times, the `kr` argument is used to specify a list of desired grades.\r\n\r\nhttps://github.com/Stefan-Endres/clifford/commit/81c78c3cd36b3d952ec652072167af786d874116\r\n\r\n```\r\n>>> cf.Cl(4, kr=[1, 3])\r\n(Layout([1, 1, 1, 1], [(), (1,), (2,), (3,), (4,), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)], \r\nfirstIdx=1, \r\nnames=['', 'e1', 'e2', 'e3', 'e4', 'e123', 'e124', 'e134', 'e234']), \r\n{'e1': (1^e1), 'e2': (1^e2), 'e3': (1^e3), 'e4': (1^e4), \r\n'e123': (1^e123), 'e124': (1^e124), 'e134': (1^e134), 'e234': \r\n(1^e234)})\r\n\r\n>>> cf.Cl(4)\r\n(Layout([1, 1, 1, 1], [(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)], \r\nfirstIdx=1, \r\nnames=['', 'e1', 'e2', 'e3', 'e4', 'e12', 'e13', 'e14', 'e23', 'e24', 'e34', 'e123', 'e124', 'e134', 'e234', 'e1234']), \r\n{'e1': (1^e1), 'e2': (1^e2), 'e3': (1^e3), 'e4': (1^e4), \r\n'e12': (1^e12), 'e13': (1^e13), 'e14': (1^e14), 'e23': (1^e23), 'e24': (1^e24), 'e34': (1^e34),\r\n'e123': (1^e123), 'e124': (1^e124), 'e134': (1^e134), 'e234': (1^e234), 'e1234':\r\n(1^e1234)})\r\n```\r\nSome basic operations such as mutlivector addition, grade projection etc. are preserved nicely. Others such as dual (in cases where the result is an initiated grade) and reflection are not.\r\n\r\nThe initiation time growth isn't as promising as I'd hoped for either, but could possibly be drastically improved with a less naive implementation. In particular 99.1% of the initiation is spent in this loop in  `_getEvenOdd`: https://github.com/pygae/clifford/blob/8793d3e4faf758770ae80d8d9e111574677772bc/clifford/__init__.py#L567\r\n\r\nThere is a comment in the code that states the loop runs for `grade!` permutations, however, at the moment it is unclear to me how the rest of the algebra and code will be affected when I change the range of these permutations or if it is even still looping for all the canonical grades at the moment. Especially when supplied with more arbitrary grade ranges.\r\n\r\nInitiation times:\r\n\r\n```\r\ncf.Cl(4)\r\nInitiation time: 0.22497177124023438\r\ncf.Cl(4, kr=[1, 3]) \r\nInitiation time: 0.0009617805480957031\r\ncf.Cl(5)\r\nInitiation time: 0.009763717651367188\r\ncf.Cl(5, kr=[1, 4]) \r\nInitiation time: 0.0020651817321777344\r\ncf.Cl(6)\r\nInitiation time: 0.0555272102355957\r\ncf.Cl(6, kr=[1, 5]) \r\nInitiation time: 0.010433673858642578\r\ncf.Cl(7)\r\nInitiation time: 0.41026782989501953\r\ncf.Cl(7, kr=[1, 6]) \r\nInitiation time: 0.08707642555236816\r\ncf.Cl(8)\r\nInitiation time: 4.242865324020386\r\ncf.Cl(8, kr=[1, 7]) \r\nInitiation time: 1.0086712837219238\r\ncf.Cl(9)\r\nInitiation time: 61.97481608390808\r\ncf.Cl(9, kr=[1, 8]) \r\nInitiation time: 15.875498056411743\r\n# cf.Cl(10) did not initiate after several minutes \r\nf.Cl(10, kr=[1, 9]) \r\nInitiation time: 329.20880341529846\r\n\r\n```\r\ncProfile for `cf.Cl(9, kr=[1, 8]`:\r\n\r\n\r\nName | Call Count | Time (ms) | Own Time (ms)\r\n-- | -- | -- | --\r\n__init__ | 1 | 23157 | 0\r\nCl | 1 | 23157 | 0\r\n_genEvenOdd | 1 | 23155 | 973\r\nmodify_idx | 362880 | 20229 | 11265\r\ntypeof | 3265940 | 8964 | 1721\r\nwrapper | 3265942 | 6188 | 1311\r\n_typeof_int | 3265937 | 3374 | 1064\r\nbit_length | 3265937 | 2310 | 1436\r\n\r\nI would be happy to contribute as much as possible under the direction of the developers.\r\n\r\nRegards, \r\nStefan Endres"},"comment":{"url":"https://api.github.com/repos/pygae/clifford/issues/comments/413548452","html_url":"https://github.com/pygae/clifford/issues/40#issuecomment-413548452","issue_url":"https://api.github.com/repos/pygae/clifford/issues/40","id":413548452,"node_id":"MDEyOklzc3VlQ29tbWVudDQxMzU0ODQ1Mg==","user":{"login":"hugohadfield","id":3056964,"node_id":"MDQ6VXNlcjMwNTY5NjQ=","avatar_url":"https://avatars0.githubusercontent.com/u/3056964?v=4","gravatar_id":"","url":"https://api.github.com/users/hugohadfield","html_url":"https://github.com/hugohadfield","followers_url":"https://api.github.com/users/hugohadfield/followers","following_url":"https://api.github.com/users/hugohadfield/following{/other_user}","gists_url":"https://api.github.com/users/hugohadfield/gists{/gist_id}","starred_url":"https://api.github.com/users/hugohadfield/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hugohadfield/subscriptions","organizations_url":"https://api.github.com/users/hugohadfield/orgs","repos_url":"https://api.github.com/users/hugohadfield/repos","events_url":"https://api.github.com/users/hugohadfield/events{/privacy}","received_events_url":"https://api.github.com/users/hugohadfield/received_events","type":"User","site_admin":false},"created_at":"2018-08-16T13:38:34Z","updated_at":"2018-08-16T13:38:34Z","author_association":"CONTRIBUTOR","body":"These even and odd permutation tables appear to be used only in _gmtElement. I think modifying _genEvenOdd to use your kr parameter and limiting the  for i in range(self.gaDims): to the indices of your sparse algebra will work fine and will bring big speedups"}}
{"actor":{"display_login":"hugohadfield"}}