William Stein wrote: > On Tue, Jun 23, 2009 at 4:30 PM, William Stein<[email protected]> wrote: >> 2009/6/23 Emmanuel Thomé <[email protected]>: >>> >>> 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. Jason --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
