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