Jason Grout wrote:
> William Stein wrote:
>> On Tue, Jun 23, 2009 at 4:30 PM, William Stein<wst...@gmail.com> wrote:
>>> 2009/6/23 Emmanuel Thomé <emmanuel.th...@gmail.com>:
>>>> I wonder what happens here:
>>>>
>>>> tiramisu ~ $ sage
>>>> ----------------------------------------------------------------------
>>>> | Sage Version 4.0, Release Date: 2009-05-29 |
>>>> | Type notebook() for the GUI, and license() for information. |
>>>> ----------------------------------------------------------------------
>>>> sage: p=3
>>>> sage: n=1000
>>>> sage: K=GF(p)
>>>> sage: KP.<x>=PolynomialRing(K)
>>>> sage: MS=MatrixSpace(K,n,n);
>>>> sage: A=MS.random_element()
>>>> sage: MSP=MatrixSpace(KP,n,n);
>>>> sage: time xI=x*MSP.identity_matrix()
>>>> CPU times: user 17.37 s, sys: 0.15 s, total: 17.52 s
>>>> Wall time: 17.54 s
>>>> sage: time xI=diagonal_matrix([x for i in range(n)])
>>>> CPU times: user 32.18 s, sys: 0.14 s, total: 32.33 s
>>>> Wall time: 32.34 s
>>>> sage: time xI.determinant()
>>>> <got fed up before it finishes...>
>>>>
>>> Type xl.determinant?? to see:
>>>
>>> ..
>>> # fall back to very very stupid algorithm -- expansion by minors.
>>> # TODO: surely there is something much better, even in total
>>> generality...
>>> # this is ridiculous.
>>> d = self._det_by_minors(self._ncols)
>>> self.cache('det', d)
>>> return d
>>>
>> Sorry, but it almost goes without saying...
>>
>> "implement it and post a patch!"
>
>
> Or finish the patch here:
>
> http://trac.sagemath.org/sage_trac/ticket/3048
>
> That patch implements generic LU decomposition and then uses that to do
> determinants and solving matrix equations. This makes determinants,
> ahem, *vastly* faster.
>
> To finish this, I think it would be sufficient to:
>
> 1. change the default pick of 'partial' pivoting to only happen in the
> case of CDF and RDF or RR or CC fields. Currently it is broken on
> symbolic matrices because the symbolic ring is "inexact".
>
> 2. Maybe change the name "lu_decomposition" to just "lu"
>
> 3. In using LU decomposition for solving, there was some question about
> the echelon form for some matrices (e.g., matrices over ZZ) being faster
> than this generic LU algorithm. So sometimes you probably want to use
> Sage's super-fast echelon implementations for certain matrices instead
> of this generic LU algorithm. I don't know what matrix types you'd want
> to prefer echelon form for, though.
>
> 4. Write necessary doctests and documentation.
>
And 5. Compare (maybe wrap??) to the nice LU decomposition routine that
already exists in sympy! I just found this. It looks like very nice
work. I should probably look at sympy more often when there are missing
bits in Sage!
Jason
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support-unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
