Hi
As it turns out I had an undergraduate student do a research project
on Dodgson's method, and we have a paper coming out in College Math
Journal later this year on a way that sort of fixes it, but (still)
not always. Here's a preprint that's somewhat strewn with typos, but
should still get the idea across:
http://arxiv.org/abs/0906.3840
An example in that paper shows that permutations of the matrix rows
and/or columns won't always work; consider the matrix
2 0 1 0 1
0 2 0 1 0
1 0 2 0 1
0 1 0 2 0
1 0 1 0 2
She's now writing her master's thesis and part of it will be a project
to study an idea of a colleague to fix it completely. However,
Bareiss' algorithm looks to be far more useful.
regards
john perry
On Aug 4, 11:33 am, javier <[email protected]> wrote:
> Hi Harald,
>
> I think the operations in the case with zeroes are not random, but a
> cyclic permutation of the rows, which allows to reuse most of the
> previously computed minors. I haven't read a complete description of
> the algorithm, but if cyclic permutations are always enough in the
> case with zeroes, they should just add at most a quadratic term to the
> computation time.
>
> Cheers
> J
>
> On 4 Aug, 16:20, Harald Schilly <[email protected]> wrote:
>
> > On 4 Aug., 16:05, Robert Miller <[email protected]> wrote:
>
> > >http://en.wikipedia.org/wiki/Dodgson_condensation
>
> > Nice, never heard of, but how does the case with zeros work? In the
> > example with zeros, C has zeros and then they do some random
> > operations (?) on the initial matrix to get rid of them. That sounds
> > bad. Rather, if this is really O(n^3), this algorithm should be called
> > first and if there happens to be a zero case, stop it and do the
> > O(n^4) routine.
>
> > H
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
