Actually there are two issues.
Sure, the determinant issue is fairly easily diagnosed. No wonder that an n!
algorithm takes time. I'll try to look into this.
But it's not the only thing.
> sage: p=3
> sage: n=1000
> sage: K=GF(p)
> sage: KP.<x>=PolynomialRing(K)
> 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
While in comparison, doing
M=matrix(KP,n)
for i in range(n): M[i,i]=x
returns instantly.
Tracing it down, it seems that when calling diagonal_matrix:
- The list is converted to a dictionary.
- Because a dense matrix was requested, this dictionary is in turn converted
to a flat list of n^2 entries.
- The base __matrix_class constructor is called, and calls the parent ring
conversion routine for each entry.
I don't know whether it's reasonable or not to have a million coercions of
zero take thirty seconds total (quite possibly not), but in any case these
can be avoided.
I suggest the attached patch.
E.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
# HG changeset patch
# User Emmanuel Thomé <emmanuel.th...@normalesup.org>
# Date 1245943398 -7200
# Node ID efedd98e25dab18c4c54c1b7bd527a70102c6936
# Parent d2d8c2f97d3256393f73b03df19d7c2a82db8a0f
Change the behaviour for dense matrices given by dictionaries. Fixes the slow
behaviour of A=diagonal_matrix([x for i in range(n)]).
diff -r d2d8c2f97d32 -r efedd98e25da sage/matrix/matrix_space.py
--- a/sage/matrix/matrix_space.py Fri Jun 19 10:30:41 2009 -0700
+++ b/sage/matrix/matrix_space.py Thu Jun 25 17:23:18 2009 +0200
@@ -366,9 +366,11 @@
rows = True
if not self.__is_sparse and isinstance(entries, dict):
- entries = dict_to_list(entries, self.__nrows, self.__ncols)
- coerce = True
- copy = False
+ A = self(0)
+ for ij, y in entries.iteritems():
+ i,j = ij
+ A[i,j] = y
+ return A
elif self.__is_sparse and isinstance(entries, (list, tuple)):
entries = list_to_dict(entries, self.__nrows, self.__ncols,
rows=rows)
coerce = True
