Dear Robert and forum,
That was actually a very good suggestion. I changed the "Graph" call to one
that usesthis function instead :
tanner:=function(x,y) if(x<=m)then if(y<=m)then return false; else
return H[x][y-m]=1; fi; else if(y>m)then return false; else
return H[y][x-m]=1; fi; fi; end;
gamma:=Graph(Group(()),[1..n+m],OnPoints,tanner,true);
girth:=Girth(gamma);
which avoids creating the large matrix. There are no memory problems with this
even for H larger than 10Kx10K.The speed is also very good even under
windows64. I will need to look at larger matrices soon so any othersuggestions
for efficiency are appreciated.
Regards,R.N.
From: "Bailey, Robert F." <rbai...@grenfell.mun.ca>
To: R.N. Tsai <r_n_t...@yahoo.com>
Cc: GAP Forum <fo...@gap-system.org>
Sent: Thursday, July 7, 2016 1:54 PM
Subject: RE: [GAP Forum] running with grape package under windows 64
Dear R.N.,
Some suggestions:
If you are using Linux, you can override GAP's default memory allocation when
you launch it (see http://www.gap-system.org/Faq/faq.html#6.2 for a discussion
of how to handle memory problems).
However, if the size of the adjacency matrix is the issue, you should consider
an alternative way of constructing the graph in GRAPE. In particular, as you
say, because the graph is bipartite its adjacency matrix will have two massive
all-zero blocks. One idea would be to rewrite the adjacency function (i.e.
replace the "function(x,y) return A[x][y]=1; end" part) to be based on entries
of H rather than A: the edges of your graph are determined precisely from where
the entries of H are 1. That way, you avoid the need to construct A.
If the graph is really sparse, just listing all edges may possibly take up less
memory than the matrix H anyway, and the adjacency function would only need to
return [x,y] as an edge if [x,y] is in your list.
Regards,
Robert Bailey.
==============================
Dr. Robert Bailey
Division of Science (Mathematics)
Grenfell Campus
Memorial University of Newfoundland
Corner Brook, NL A2H 6P9, Canada
Office: AS 3022
Phone: +1 (709) 637-6293
Web: http://www2.grenfell.mun.ca/rbailey/
-----Original Message-----
From: forum-boun...@gap-system.org [mailto:forum-boun...@gap-system.org] On
Behalf Of R.N. Tsai
Sent: July-07-16 5:28 PM
To: Alexander Konovalov <alexander.konova...@st-andrews.ac.uk>
Cc: GAP Forum <fo...@gap-system.org>
Subject: Re: [GAP Forum] running with grape package under windows 64
Dear Alexander and forum,
Thanks for your suggestion; it did in fact work, so now grape works with both
gap32 and gap64.Performance under windows seems to get much worse as the size
of the graph gets bigger. I movedto linux64 and the performance is much better
there until gap runs out of memory.
I have some followup questions regarding memory management in gap and graph
calculations with grapeor other packages : (the moderators of the forum can
move to another topic if they think that's better).
(1)I'm using grape to calculate the girth of large graphs. These graphs are the
"Tanner graphs" of low density parity check (LDPC) codes. These type of graphs
are frequently used in coding theory to analyze the error correcting
capability of the code. In particular, the length of the shortest cycles
(girth) and number of such cycles is important. I looked in the guava package
which has some constructs for LDPC codes ("QCLDPCCodeFromGroup" for example)
but nothing specific for Tanner graphs.....
(2)Tanner graphs are easily described : take the parity check matrix of the
code "H" of size mxn and form A=(m+n)x(m+n) matrix defined as A=[0,H],[H',0]];
here H' is transpose. H is large (say 10K x 10K) binary matrix (0,1 entries)
but very sparse (percentage of 1's is <2%). Here's how I get "A" from "H" :
dim:=DimensionsMat(H);m:=dim[1];n:=dim[2]; T:=H;
T1:=List([1..m],x->Concatenation(0*[1..m],T[x])); T:=TransposedMat(H);
T2:=List([1..n],x->Concatenation(T[x],0*[1..n])); A:=Concatenation(T1,T2);
This results in a large sparse matrix "A" which is >99% 0's. Is there a
better way to define it?
(3)With the adjacency matrix "A" I define a graph "gamma" using grape's
documentation :
gamma:=Graph(Group(()),[1..n+m],OnPoints,function(x,y)return
A[x][y]=1;end,true);
by the construction of "A", it is known to be bipartite with the partition of
vertices well known, namely [1..m] and [m+1..m+n] but I don't know how to use
this extra knowledge to help grape work with the graph more efficiently.
(4)I get the girth through girth:=Girth(gamma); I would also like to get the
number of cycles with length=girth but I don't know how that's done.
(5)Finally, is there a way to "clear memory" within gap? I noticed that if I
process H1 then try to process H2 in the same gap session gap reports that the
memory limit was exceeded, but if I exit gap and start it again with H2, then
it works. I don't save anything from the calculations (I just print out the
results) so I don't know what's using the memory. Here's an example :
gap>Process(H1); #finishes ok; no variables saved... gap>Process(H2); #comes
back with memory problem if I exit gap and start again gap>Process(H2); #now
this works without memory problem.
Thanks for your help.
R.N.
From: Alexander Konovalov <alexander.konova...@st-andrews.ac.uk>
To: R.N. Tsai <r_n_t...@yahoo.com>
Cc: GAP Forum <fo...@gap-system.org>
Sent: Thursday, July 7, 2016 2:46 AM
Subject: Re: [GAP Forum] running with grape package under windows 64
> On 7 Jul 2016, at 07:19, R.N. Tsai <r_n_t...@yahoo.com> wrote:
>
> Dear GAP forum,I'm doing some calculations with gap+grape package under
> windows. Things work fine with the gap32 version, but grape doesn't seem to
> workwith gap64. The graphs I'm working with are very large and I would liketo
> run gap64 with 16GBytes memory. Is there a 64 bit version of grapeavailable
> somewhere?Thanks,R.N.
Dear R.N.,
Grape uses a stand-alone binary, so it can interact with 64-bit GAP version
even being 32-bit application. The problem is that GAP looks for the binary
for GRAPE using the architecture-dependent path which it assumes to be
'x86_64-unknown-cygwin-gcc-default64'. As a quick workaround, I suggest to
try this: in the 'bin' directory of your GRAPE installation, you should
have the directory 'i686-pc-cygwin-gcc-default32'. Copy it to the directory
'x86_64-unknown-cygwin-gcc-default64' and try to load GRAPE from 64-bit
version of GAP now. Please let me know if this helps!
Best wishes
Alexander
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
This electronic communication is governed by the terms and conditions at
http://www.mun.ca/cc/policies/electronic_communications_disclaimer_2011.php.
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
