[sage-support] Re: Constructing subsapces of vector spaces

2012-12-04 Thread Andrew Mathas
Thanks Nils. I this is similar to, but more elegant than, what I tried 
earlier. I went back to the solution above, however, I thought that there 
was probably a lot of overhead in creating the space ZZ^3 and the 
homomorphism. Indeed,

%timeit V.hom([(ZZ^3)(v) for v in [[1,2,3],[2,1,4],[3,3,7]]]).kernel()
125 loops, best of 3: 2.15 ms per loop

sage: %timeit 
V.submodule_with_basis([V.linear_combination_of_basis(b.list())  for b in 
mat.kernel().basis()])
625 loops, best of 3: 1.39 ms per loop

so it does seem to be slower, although one example is hardly definitive.

Andrew

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




[sage-support] Re: Constructing subsapces of vector spaces

2012-12-04 Thread Nils Bruin

On Tuesday, December 4, 2012 3:14:27 AM UTC-8, Andrew Mathas wrote:

 Thanks Nils. I this is similar to, but more elegant than, what I tried 
 earlier. I went back to the solution above, however, I thought that there 
 was probably a lot of overhead in creating the space ZZ^3 and the 
 homomorphism. Indeed,

 %timeit V.hom([(ZZ^3)(v) for v in [[1,2,3],[2,1,4],[3,3,7]]]).kernel()
 125 loops, best of 3: 2.15 ms per loop

 sage: %timeit 
 V.submodule_with_basis([V.linear_combination_of_basis(b.list())  for b in 
 mat.kernel().basis()])
 625 loops, best of 3: 1.39 ms per loop

 so it does seem to be slower, although one example is hardly definitive.


I wouldn't draw any conclusions from that. In one timeit you are still 
constructing the matrix/hom whereas in the other you already have it. 
Anyway, indeed, the whole module (homomorphism) code is incredibly 
inefficient because special cases such a ZZ-modules haven't been 
special-cased at all yet (except for computing the kernel code). If you 
want speed, write it out in matrices:

 sage: %timeit 
matrix([[1,2,3],[2,1,4],[3,3,7]]).transpose().right_kernel_matrix()*matrix([[0,1,2,3],[2,3,1,4],[1,3,2,1]])
625 loops, best of 3: 668 µs per loop

As long as you only need submodules it's not so bad. Once you really need 
quotients (especially non-free ones) you probably are better off using 
modules.

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




[sage-support] Re: Constructing subsapces of vector spaces

2012-12-03 Thread John Cremona
Try mat.kernel_on(V).   

Also, if v is a vector in the ambient space which happens to lie in V then 
V.coordinates(v) will give its coordinates w.r.t. the basis of V.

John Cremona

On Monday, December 3, 2012 1:38:38 AM UTC, Andrew Mathas wrote:

 Hi All,

 I have been playing with some code where I want to find a submodule of a 
 module V which is annihilated by a bunch of maps. What I want to do 
 something like the following:

 V= some free submodule of rank v inside a space of rank d\ge v.
 mat=[[0 for col in range(w)] for row in range(v)]  # fairly sparse matrix 
 which describes the map f on bases of V and W
 ...compute non-zero entries of the matrix ``mat``
 V = V.intersection( matrix(mat).kernel() )

 where v=dim V,  w=dim W where f is a map from V to W. Of course, this 
 doesn't quite work because matrix(mat).kernel() returns a submodule of ZZ^v 
 with respect to its standard basis whereas the space V has a very different 
 basis in general. To get around this I found myself writing

 kernel=V.submodule_with_basis([V.linear_combination_of_basis(b.list())  
 for b in matrix(pmat).kernel().basis()])
 V=V.intersection(kernel)

 This strikes me as being a very convoluted way of writing something is 
 presumably quite common: writing the standard basis elements as linear 
 combinations of another basis. My question is: is there a better way to 
 do this?

 For a little while, I tried defining W=FreeModule(ZZ,w) and then 
 constructing the map f explicitly as a homomorphism from V to W. Doing it 
 this way does make f.kernel() into a submodule of V, but this approach just 
 seems to create a lot of extra overhead with very little benefit as I 
 essentially still had to construct the matrix ``mat`` above and used it to 
 define ``f`` with respect to the bases of ``V`` and ``W``. In fact, all 
 this really did was shift my problem above of writing the basis of the 
 kernel in terms of the basis of V to the problem of writing the images of f 
 in terms of the standard basis of W. (Even though I imagine that this 
 second approach is much slower I really should have  checked by doing some 
 profiling before rewriting as above, but I didn't...)

 Any thoughts?

 Cheers,
 Andrew





-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




[sage-support] Re: Constructing subsapces of vector spaces

2012-12-03 Thread Andrew Mathas
Hi John,

Thanks for the reply, but you have my problem upside down as I don't need 
to restrict from the ambient space to the subspace but rather to extend 
from the subspace to the ambient space. 

For example, I could have:

sage: V
Free module of degree 4 and rank 3 over Integer Ring
User basis matrix:
[0 1 2 3]
[2 3 1 4]
[1 3 2 1]
sage: mat=matrix([[1,2,3],[2,1,4],[3,3,7]]); mat.kernel()
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1  1 -1]

The problem that is V is isomorphic to Z^3, but it is represented as a 
subspace of Z^4, whereas the kernel is a subspace of Z^3. As I mentioned, 

sage: V.submodule_with_basis([V.linear_combination_of_basis(b.list())  for 
b in mat.kernel().basis()])
Free module of degree 4 and rank 1 over Integer Ring
User basis matrix:
[1 1 1 6]

does give the kernel as a subspace of V. I was just wondering if there was 
a better way of doing this.

Cheers,
Andrew

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




[sage-support] Re: Constructing subsapces of vector spaces

2012-12-03 Thread Nils Bruin


On Monday, December 3, 2012 5:09:40 PM UTC-8, Andrew Mathas wrote:

 Hi John,

 Thanks for the reply, but you have my problem upside down as I don't 
 need to restrict from the ambient space to the subspace but rather to 
 extend from the subspace to the ambient space. 

 For example, I could have:

 sage: V
 Free module of degree 4 and rank 3 over Integer Ring
 User basis matrix:
 [0 1 2 3]
 [2 3 1 4]
 [1 3 2 1]
 sage: mat=matrix([[1,2,3],[2,1,4],[3,3,7]]); mat.kernel()
 Free module of degree 3 and rank 1 over Integer Ring
 Echelon basis matrix:
 [ 1  1 -1]

 The problem that is V is isomorphic to Z^3, but it is represented as a 
 subspace of Z^4, whereas the kernel is a subspace of Z^3. As I mentioned, 


So, when you're computing the kernel, you should tell the system that you 
want a kernel of a homomorphism on V; not on abstract Z^3:

sage: A=ZZ^4
sage: V=A.submodule_with_basis([[0,1,2,3],[2,3,1,4],[1,3,2,1]])
sage: phi=V.hom([(ZZ^3)(v) for v in [[1,2,3],[2,1,4],[3,3,7]]])
sage: phi.kernel()
Free module of degree 4 and rank 1 over Integer Ring
Echelon basis matrix:
[1 1 1 6]


-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.