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 -~----------~----~----~----~------~----~------~--~---
