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