List Archives >  Maple User Group List Archive >  Archive by date >  This Month By Date >  This Month By Topic

[MUG] Matrix and filling it up

Search email archive for  

[MUG] Matrix and filling it up
Author: Caroline Ibrahim    Posted: Wed, 23 Oct 2002 11:43:14 -0400
>> From: Caroline Ibrahim "cibrah" Hello all, Another question of efficiency. I want to create this huge matrix (say 1048576 by 5) and fill it up with 0, 1, 2 and 3 in an ordered manner. For example the first column of the matrix will have 262144 zeros, then 262144 ones,then 262144 twos and 262144 threes. In the second column, the first 65536 rows will have zeros, the next 65536 rows ones, then 65536 rows of twos and 65536 rows of threes. The rest of the rows of the second column are filled the same way the first 262144 are filled up. I hope you got the pattern here of filling up the rest of the columns. What's the best way to create this matrix with less running time? Can this be done using sequences? (I need to use it in some other calculations). Thanks. Caroline

[MUG] Re: Matrix and filling it up
Author: Carl Devore    Posted: Sat, 26 Oct 2002 20:40:22 -0400
>> From: Carl Devore "devore" On Wed, 23 Oct 2002, Caroline Ibrahim wrote: > I want to create this huge matrix (say 1048576 by 5) and fill it up with > 0, 1, 2 and 3 in an ordered manner. For example the first column of the > matrix will have 262144 zeros, then 262144 ones,then 262144 twos and > 262144 threes. In the second column, the first 65536 rows will have > zeros, the next 65536 rows ones, then 65536 rows of twos and 65536 rows of > threes. The rest of the rows of the second column are filled the same way > the first 262144 are filled up. I hope you got the pattern here of > filling up the rest of the columns. > > What's the best way to create this matrix with less running time? Can > this be done using sequences? (I need to use it in some other > calculations). More important than filling it up efficiently is using it efficiently. Yes, the fastest way that I can find to fill it is with sequences: A:= Matrix( [seq]([seq](seq(i $ 4^(10-j), i= 0..3), k= 1..4^(j-1)), j= 1..5) ,scan= columns ,datatype= integer[1] ); This takes 6.6 secs on my computer. The datatype= integer[1] will cut the memory usage by a factor 4, but does not have a significant effect on the fill time. The restricted datatype may inhibit some subsequent calculations. It might be better to use an indexing function, escpecially if you do not plan to change the Matrix. The indexing function giving the value as a function of the row & column (i & j) would be: (i,j)-> irem(iquo(i-1, 4^(10-j)), 4); This will use almost 0 memory, but makes the lookups take a bit longer. Example: `index/Caroline`:= IJ-> irem(iquo(IJ[1]-1, 4^(10-IJ[2])), 4); proc() :-A:= Matrix(4^10,5, storage= empty, shape= Caroline); [][] end(); A[746908,3]; 1 The matrix creation needs to be done in a procedure to avoid processing every (i,j) at creation time.

[MUG] Re: Matrix and filling it up
Author: Maple User Group    Posted: Fri, 1 Nov 2002 10:16:40 -0500 (
>> From: Maple User Group "maple_gr" -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Tue, 29 Oct 2002 17:42:33 -0500 (EST) From: David Linder "dlinder" To: "maple-list" Subject: Matrix and filling it up Here's what I sent this to the original poster. In my email to that poster I had NN set to only four columns. Below I set it to 5. MM := 1048576; NN := 5; m := Matrix(MM,NN): for i from 1 to NN do N := MM/(2^(i+1)); for k from 1 to 4 do vk := Vector(N,shape=constant[k-1]): for j from 1 to 2^(i-1) do bump := 4*(j-1); m[(bump+k-1)*N+1..(bump+k)*N,i] := vk: od: od: od: I hope that I interpreted the question properly and that this does generate the Matrix that is actually wanted. On a 600Mz PIII running RedHat Linux 6.1 this took about 2.8 sec . I found that the memory allocation for the above is roughly the same as for creating a Matrix filled entirely with just one single number at creation time, with the fill=<value> option, ie, about 21Mb. If I change the Matrix() constructor call above to m := Matrix(MM,NN,datatype=integer[1]): then the memory allocation drops to about 5.5Mb . When I try Carl Devore's first example below, with the explicit full storage of all the entries, then on my machine I find that the memory allocation is 115Mb and the time it takes to be about 30 sec. That's with the datatype set to integer[1] . I just cut and pasted that example from the post below. Cheers, Dave Linder -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Thu, 31 Oct 2002 02:24:52 -0500 (EST) From: Carl Devore "devore" To: David Linder "dlinder" Subject: Matrix and filling it up I believe that the OP intended to group by powers of 4, so the N assignment should be N:= MM/4^i and the upper bound on the innermost loop should be 4^(i-1). > On a 600Mz PIII running RedHat Linux 6.1 this took > about 2.8 sec . It is great to know that high-level looping and `..` index constructions beat using seq inside the Matrix command. I never would have guessed that. > If I change the Matrix() constructor call above to > m := Matrix(MM,NN,datatype=integer[1]): > then the memory allocation drops to about 5.5Mb . It is good that these are just the number of bytes in the actual matrix -- there is no waste. The seq commands apparently generate a lot of garbage. If I measure the time that it takes to multiply this matrix by a vector, it takes half the time when the datatype is integer[1]. This may be due to caching. I am using a 1.6 GHz P4 Win XP with 256K L2 cache. It is also very good to note that using LinearAlgebra:-Modular:-Mulitply cuts the multiplication time by a factor of 20 when compared to LinearAlgebra:-LA_Main:-MatrixMatrixMultiply. -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Thu, 31 Oct 2002 15:06:31 -0500 (EST) From: Caroline Ibrahim "cibrah" To: "maple-list" Subject: Matrix and filling it up Thanks David and Carle for the helpful reply re the above. I think there is a better way of doing what I need other than creating this matrix. Here's the situation: I have a bunch of homomorphisms from a group with presentation, let's say, <a_1, b_1, a_2, b_2> into a finietly generated abelian group (say Z2xZ4 or Z4xZ4). Of these I want to pick only those that are epimorphisms. My matrix question before was based on the idea of multiplying the matrix by images of {a_1, b_1...etc.} and checking for existence of generators of the abelian group in the product matrix. Is there another way to do this? Someone mentioned a Hermite(?) command, but I don't know how that works. Thanks. Caroline

Previous by date: [MUG] Re: plots from Maple, Maple User Group
Next by date: [MUG] Re: Question about programming maple with graphic commands, Maple User Group
Previous thread: [MUG] Maple and Octave, Brad Camroux
Next thread: [MUG] Re: Question about programming maple with graphic commands, Raphael Giromini