Timeline for Calculate the Hafnian as quickly as possible
Current License: CC BY-SA 4.0
44 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2023 at 2:07 | answer | added | 138 Aspen | timeline score: 0 | |
| Jun 13, 2023 at 13:06 | answer | added | 138 Aspen | timeline score: 0 | |
| Jun 13, 2023 at 12:49 | history | edited | 138 Aspen | CC BY-SA 4.0 |
MathJax equations support
|
| Jun 4, 2018 at 15:50 | comment | added | Nicolás Quesada | Recently Andreas Bjorklund, Brajesh Gupt and myself published a new algorithm for Hafnians of complex matrices: arxiv.org/pdf/1805.12498.pdf . For an n \times n matrix it scales like n^3 2^{n/2}. If I understand correctly Andreas' original algorithm from arxiv.org/pdf/1107.4466.pdf it scales like n^4 2^{n/2} or n^3 log(n) 2^{n/2} if you used Fourier transforms to do polynomial multiplications. Our algorithm is specifically taylored for complex matrices so it will not be as fast as the ones developed here for {-1,0,1} matrices. I wonder however if one can use some of the trick | |
| Mar 13, 2018 at 16:36 | history | edited | user9206 | CC BY-SA 3.0 |
added 299 characters in body
|
| Mar 13, 2018 at 10:52 | history | edited | user9206 | CC BY-SA 3.0 |
added 49 characters in body
|
| Mar 13, 2018 at 8:20 | history | edited | user9206 | CC BY-SA 3.0 |
deleted 41 characters in body
|
| Mar 13, 2018 at 2:42 | answer | added | miles | timeline score: 6 | |
| S Mar 12, 2018 at 9:30 | history | bounty ended | CommunityBot | ||
| S Mar 12, 2018 at 9:30 | history | notice removed | user9206 | ||
| Mar 7, 2018 at 14:15 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Mar 7, 2018 at 10:15 | history | edited | user9206 | CC BY-SA 3.0 |
added 104 characters in body
|
| Mar 7, 2018 at 6:10 | answer | added | miles | timeline score: 3 | |
| Mar 5, 2018 at 15:10 | history | edited | user9206 | CC BY-SA 3.0 |
added 43 characters in body
|
| Mar 5, 2018 at 12:32 | answer | added | Sanchises | timeline score: 1 | |
| S Mar 4, 2018 at 15:51 | history | bounty started | CommunityBot | ||
| S Mar 4, 2018 at 15:51 | history | notice added | user9206 | Draw attention | |
| Mar 4, 2018 at 11:31 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Mar 4, 2018 at 9:46 | history | edited | user9206 | CC BY-SA 3.0 |
added 146 characters in body
|
| Mar 3, 2018 at 20:43 | answer | added | Christian Sievers | timeline score: 14 | |
| Mar 3, 2018 at 18:39 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Mar 3, 2018 at 17:37 | history | edited | user9206 | CC BY-SA 3.0 |
added 118 characters in body
|
| Mar 3, 2018 at 17:19 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Mar 3, 2018 at 17:13 | history | edited | user9206 | CC BY-SA 3.0 |
added 61 characters in body
|
| Mar 3, 2018 at 14:45 | answer | added | Dennis | timeline score: 6 | |
| Mar 3, 2018 at 14:26 | answer | added | ngn | timeline score: 4 | |
| Mar 3, 2018 at 13:07 | comment | added | user9206 | @user202729 Yes they will be | |
| Mar 3, 2018 at 12:50 | answer | added | ngn | timeline score: 4 | |
| Mar 3, 2018 at 11:29 | comment | added | user202729 | I think that to be fair the randomly generated matrices should be the same for all submissions. | |
| Mar 3, 2018 at 10:36 | comment | added | user9206 | @miles Added a slightly bigger example. | |
| Mar 3, 2018 at 10:35 | history | edited | user9206 | CC BY-SA 3.0 |
added 729 characters in body
|
| Mar 3, 2018 at 10:26 | comment | added | miles | Do you have more test cases? perhaps for larger n? | |
| Mar 2, 2018 at 19:44 | comment | added | user9206 | @Dennis An old version used to say that but I must have written over it. I would prefer it if the code weren't specialised for -1,0,1 entries but I suppose I can't stop that. | |
| Mar 2, 2018 at 19:43 | history | edited | user9206 | CC BY-SA 3.0 |
added 188 characters in body
|
| Mar 2, 2018 at 19:40 | comment | added | Dennis | If the entries are limited to -1,0,1, that should be mentioned on the question. Does our code have to work at all for other matrices? | |
| Mar 2, 2018 at 19:37 | comment | added | user9206 | @Dennis In practice I will only use -1,0,1 to test (chosen at random). I don't want it to be a big int challenge. In all honesty I don't know if we will hit the limits of 64 bit ints before the code gets too slow to run but my guess is that we won't. Currently we are nowhere near that. | |
| Mar 2, 2018 at 19:36 | comment | added | Dennis | Is there a limit for the absolute values of the matrix entries? Can we return a floating point approximation? Do we have to use arbitrary precision integers? | |
| Mar 2, 2018 at 17:21 | history | edited | flawr | CC BY-SA 3.0 |
deleted 22 characters in body
|
| Mar 2, 2018 at 16:48 | history | edited | user9206 | CC BY-SA 3.0 |
added 201 characters in body
|
| Mar 2, 2018 at 16:28 | history | tweeted | twitter.com/StackCodeGolf/status/969610421182390273 | ||
| Mar 2, 2018 at 16:20 | history | edited | user9206 | CC BY-SA 3.0 |
added 14 characters in body
|
| Mar 2, 2018 at 15:58 | history | edited | Luis Mendo |
edited tags
|
|
| Mar 2, 2018 at 15:43 | history | edited | user9206 | CC BY-SA 3.0 |
added 63 characters in body
|
| Mar 2, 2018 at 15:16 | history | asked | user9206 | CC BY-SA 3.0 |