Hi all,
I have written some code which involves a lot of matrix operations,
where the base ring is a univariate polynomial ring over the
rationals. I think there are (at least) three ways to speed this up:
(1) Improve my code to perform fewer matrix operations, but I
guess that's something for me to look at.
(2) Improve the underlying implementation of QQ['x'], see my post
earlier today on that.
(3) I am wondering whether something can be done about the
overhead in the matrix multiplication? This is the main point of this
post and I'll explain it further below:
sage: R.<t> = QQ[]
sage: N = random_matrix(R, 28, 28)
sage: N*N
The last call takes about 1.9s on my laptop, and %prun gives the
following details
ncalls tottime filename
21953 0.567 polynomial_ring.py:211(_element_constructor_)
21952 0.290 polynomial_element_generic.py:817(_mul_)
21952 0.258 polynomial_element_generic.py:673(_add_)
43905 0.178 polynomial_element_generic.py:590(__init__)
That is, a significant time is spent creating new polynomials. If I
were to implement the multiplication of matrices over QQ['x'] myself
(which of course is NOT the point of this post), I guess one would up
front know how many new polynomials needed to be allocated (i.e. all
n^2 for the target matrix, plus some temporary ones) and try to keep
the number of temporary ones low.
Is there anything that one can do easily to improve this at the
moment?
On a related note, say one has a given matrix M to begin with, and,
starting with the identity matrix C, has a loop like this:
for i in range(1,n):
C = M*C
[some fast changes to the matrix C]
How much overhead does this create, i.e., does this allocate a new
matrix every iteration when the product is computed? In terms of
memory allocation, I think one might want to have something like
allocate M, C and T
for i in range(1,n):
compute T = M*C (without allocating a new matrix)
set C = T (by value, not reference)
[some fast changes to the matrix C]
but I am not sure whether anything like this is possible.
Any help would be greatly appreciated.
Many thanks,
Sebastian
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
