Timeline for Computing a large permanent
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2013 at 9:44 | vote | accept | Felix Goldberg | ||
| Apr 29, 2013 at 17:23 | answer | added | Timothy Chow | timeline score: 8 | |
| Apr 29, 2013 at 16:16 | comment | added | Felix Goldberg | @quid an approximation might do, depending how good it is. | |
| Apr 29, 2013 at 15:31 | comment | added | Gerhard Paseman | I now understand Rysers formula better,and the answer will not be as simple. However, you can use it to approximate the permanent, and I am guessing the answer will be near 9^91. Gerhard "Give Or Take A Googol" Paseman, 2013.04.29 | |
| Apr 29, 2013 at 13:33 | comment | added | Gerhard Paseman | If I understand Ryser's formula correctly, you can use it to great effect, since it will amount to (something like) 9^91. Gerhard "Invites Verification Of This Estimate" Paseman, 2013.04.29 | |
| Apr 29, 2013 at 9:01 | history | edited | Felix Goldberg | CC BY-SA 3.0 |
added 95 characters in body
|
| Apr 29, 2013 at 2:44 | comment | added | Gerhard Paseman | Perhaps there is a small submatrix of this that might be hard to compute. If you tell us more about the instance, perhaps we can suggest something. Gerhard "Ask Me About Smaller Cases" Paseman, 2013.04.28 | |
| Apr 29, 2013 at 2:39 | comment | added | Brendan McKay | If the matrix is extremely sparse it could be possible. It is much bigger than problems usually solvable. | |
| Apr 29, 2013 at 2:23 | answer | added | none | timeline score: 1 | |
| Apr 28, 2013 at 23:04 | comment | added | John Wiltshire-Gordon | If your matrix is an integer matrix, it should be possible to compute the last few bits in the base 2 expansion. Maybe that would be helpful? | |
| Apr 28, 2013 at 21:01 | history | edited | user9072 |
edited tags
|
|
| Apr 28, 2013 at 20:58 | comment | added | user9072 | Do you need the exact value or would an approximation suffice? | |
| Apr 28, 2013 at 20:47 | comment | added | Victor Kleptsyn | My first guess would be that no, unless the matrix has some properties that will help (for instance, if it's an adjacency matrix of a planar graph): in general, computing permanents is a hard problem (sf. en.wikipedia.org/wiki/Permanent_is_sharp-P-complete ) | |
| Apr 28, 2013 at 20:35 | comment | added | Carlo Beenakker | have you tried Brian Butler's code? sites.google.com/site/brianbutlerengineer/home/research (scroll to bottom of page) | |
| Apr 28, 2013 at 20:10 | comment | added | Gerhard Paseman | Is there any symmetry or reduction that you can exploit? (An obvious example would be that it has a block submatrix all with the same entry.) Gerhard "Ask Me About Binary Matrices" Paseman, 2013.04.28 | |
| Apr 28, 2013 at 20:03 | history | asked | Felix Goldberg | CC BY-SA 3.0 |