My code is not downloadable anywhere that I am aware of. I used to use it in my quadratic sieve before I switched to Jason P's block Lanczos code (BL solves a more restricted problem but is fine for the QS). My old code is some of the earliest mathematical C code that I wrote, so can certainly be improved. I can certainly make it available at some point. The crossover with block Lanczos was about 6000x6000.
The matrices of 6000x6000 had something like 12 nonzero entries in each row, so quite sparse. Of course the matrix quickly becomes dense as the algorithm proceeds. I was also taking advantage of the fact that the left hand side of the matrix was more dense than the right, which is probably not the situation you would have arising in your research, Martin. At any rate, it might make a reasonable base case for an implementation of something. Bill. On 20 May, 09:47, Martin Albrecht <[EMAIL PROTECTED]> wrote: > On Tuesday 20 May 2008, Bill Hart wrote: > > > Martin, > > > On the M4RI website you say that M4R inversion is asymptotically fast > > with time complexity n^3/log_2(n), but Strassen's method has > > complexity n^log2(7), which I would call asymptotically fast. > > > Do you just mean asymptotically faster than the classical algorithm? > > Yes, I'll fix that. > > > By the way, I wrote some code ages ago for computing the row echelon > > form of sparse matrices over GF2 which essentially inverts 6000x6000 > > sparse matrices in about a second. > > Excellent, is the code available somewhere? How dense are these matrices? > > My plan for M4RI is: > > - polish what we have for multiplication now, find appropriate/acceptable > parameters for a wide range of platforms, make sure it builds everywhere etc. > > - during dev1 Greg and I are going to work on Strassen + M4RI/echelonisation. > This is the actual application we are most interested in > > - Once that is done, I want to look into sparse matrices (which are probably > much more relevant for my work than dense matrices) so I'd be interested in > looking into your old code. I'm not sure this should go under the roof of the > M4RI library but if it does then this probably warrants a name change :-) > > Martin > > -- > name: Martin Albrecht > _pgp:http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _www:http://www.informatik.uni-bremen.de/~malb > _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
