Timeline for Computing determinants of matrices of linear forms
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 14, 2012 at 10:28 | comment | added | David E Speyer | Ahh, I think I see. So, whenever the algorithm says to compute $F/G$, what I actually do is take a least squares solution to the overdetermined linear equations $F=GH$, where $H$ is of known degree. Interesting... | |
| Aug 14, 2012 at 0:32 | comment | added | Jack Huizenga | You can also reduce to the single-variable case by substituting $(x,y,z) \mapsto (1,x^n,x^m)$ where $0<< n << m$; for sufficiently large $n,m$ there will be a unique way to undo this substitution after computing the determinant. | |
| Aug 14, 2012 at 0:31 | comment | added | Chris Godsil | @David Speyer: what quid says. (Dodgson will work over a UFD, but PID was as much as I felt safe asserting from memory.) I suspect Igor is right about the relative speed, but both algorithms are easy to implement. My impression is that if the number of variables increases, Dodgson may become more attractive. | |
| Aug 14, 2012 at 0:07 | comment | added | user9072 | But it requires no 'true' division; all division are a priori known to be exact. And PID is not really relevant. What one need to be able to do is: given A and B where it is known that A divides B in the ring, compute (an approximation to) the co-divior. I am not completely sure now, but this seems feasible also for multi var poly (though perhaps it is too expensive to keep the algo competitive relative to approximation). | |
| Aug 13, 2012 at 23:22 | comment | added | David E Speyer | Confused about suggestion (1). $\mathbb{R}[x,y,z]$ is not a PID (though it is a UFD) and every version of Dodgson condensation I know requires division. | |
| Aug 13, 2012 at 22:00 | comment | added | Chris Godsil | Fixed the terminology. | |
| Aug 13, 2012 at 21:59 | history | edited | Chris Godsil | CC BY-SA 3.0 |
added 3 characters in body
|
| Aug 13, 2012 at 21:49 | comment | added | Igor Rivin | First, it is Dodgson CONDENSATION. Second, what is so unpleasant about interpolation? I would conjecture that it would be MUCH faster than the other algorithms you suggest, and the implementation (at least in mathematica) is completely trivial. | |
| Aug 13, 2012 at 18:50 | history | answered | Chris Godsil | CC BY-SA 3.0 |