Hi Dima, I misread your statement >>> We have a matrix in some basis, not necessarily sparse. and thought it meant that your matrix was already of the form [ I A ]. Once you have this form, it's linear time, but I agree that getting there takes O(n^2m) time in a non-sparse matrix.
--Rudi > But how can one find a basis in linear time? Don't you need to do > reductions of vectors modulo a subbasis found so far? > (which is O(n^2) if you far enough in building the full basis) > > And you might have to do this for O(m) vectors, before, say, the > last basis element is found. Naively this seems to give > O(mn^2). > > Dima > >> --Rudi >> > > -- > > --- > You received this message because you are subscribed to the Google Groups > "sage-matroid" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. -- --- You received this message because you are subscribed to the Google Groups "sage-matroid" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
