For comparison: PLE decomposition needs 2.8 multiplications if asymptotically fast multiplication is used and 0.66 if cubic multiplication is used, cf.
http://arxiv.org/pdf/1112.5717.pdf On Tuesday 03 Jul 2012, Dima Pasechnik wrote: > On Tuesday, 3 July 2012 20:22:37 UTC+8, Martin Albrecht wrote: > > As far as I can tell all methods need matrix multiplication, so whatever > > choice me make the difference will be constant, i.e., how many > > matrix-matrix > > products we need (assuming asymptotically fast techniques were > > implemented) > > well, as far as I see, my latest proposal needs one product, of a general > matrix by an upper-triangular > matrix. > > > On Tuesday 03 Jul 2012, Dima Pasechnik wrote: > > > On Tuesday, 3 July 2012 17:45:52 UTC+8, Javier López Peña wrote: > > > > I know little of random methods, but do we really need to make things > > > > so > > > > > > complicated? As the OP suggests, we might as well just generate > > > > matrices > > > > > > uniformly at random and discard if not invertible. The set of > > > > invertible > > > > > > matrices is Zariski open, so the probability of hitting a > > > > non-invertible > > > > > > matrix should be very small (0 for real or complex matrices, I don't > > > > know > > > > > > about finite fields). > > > > > > well, it's not that small, especially for finite fields. E.g. for F_2 > > > > and > > > > > n=3, one only gets 168 invertible matrices out of 512=2^9 in total... > > > (I can't resist saying that the order of GL(n,q) is > > > (q^n-1)(q^{n-1}-1)...(q^2-1)(q-1)) > > > So it's not gonna be very fast, also note that computing the > > > determinant comes at a nonzero cost when matrices are big... > > > > > > Dima > > > > > > > I understand this naive method might not be the quickest possible > > > > algorithm but it is much faster than what we have now and just works, > > > > so > > > > > > why not implement just that, with the obvious fix so that the > > > > MatrixSpace > > > > > > doesn't get called over and over? > > > > > > > > Cheers, > > > > J > > > > > > > > On Tuesday, July 3, 2012 5:31:39 AM UTC+1, Dima Pasechnik wrote: > > > >> On Tuesday, 3 July 2012 11:26:54 UTC+8, Dima Pasechnik wrote: > > > >>> On Tuesday, 3 July 2012 10:36:37 UTC+8, Dima Pasechnik wrote: > > > >>>> On Tuesday, 3 July 2012 09:56:04 UTC+8, Charles Bouillaguet wrote: > > > >>>>> > Mhh, why not? If A = LUP we just write AP^-1 = LU, hence for > > > > each > > > > > >>>>> LU we > > > >>>>> > > > >>>>> > construct there are as many As as there are permutation > > > > matrices, > > > > > >>>>> > or > > > >>>>> > > > >>>>> am I > > > >>>>> > > > >>>>> > missing something (again :))? > > > >>>>> > > > >>>>> I am not sure that the LUP decomposition is unique (I understand > > > > that > > > > > >>>>> the LU is). > > > >>>> > > > >>>> An invertible matrix need not have an LU decomposition. E.g. > > > >>>> A=[[0,1],[1,1]] does not have it. > > > >>>> > > > >>>> It's evident over F_2: L can only take 2 values, and U can only > > > > take 2 > > > > > >>>> values, so you can't have > > > >>>> more than 4 different matrices of the form LU :–) > > > >>> > > > >>> by the way, for generating random elements it might be better to > > > >>> use the Bruhat decomposition, which is unique. See > > > >>> http://en.wikipedia.org/wiki/Bruhat_decomposition > > > >> > > > >> I take the last part back, sorry, it makes little sense. > > > >> What certainly is doable is the following: > > > >> 1) uniformly select a random maximal flag > > > >> 2) uniformly select a random element U in the subgroup stabilizing > > > > the > > > > > >> "canonical" maximal flag, i.e. the one stabilized by the > > > >> upper triangular matrices. > > > >> Then an element MU, for M being a matrix mapping the "canonical" > > > >> flag > > > > to > > > > > >> the flag selected at step 1, will be uniformly > > > >> distributed over the whole group G (as step 1 selects a coset of U > > > >> in G). > > > >> > > > >>>>> If A has more distinct LUP factorizations than B, then A > > > >>>>> is more likely to be produced by this process than B.... > > > >>>>> > > > >>>>> Charles > > > > Cheers, > > Martin Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
