[GAP Forum] running with grape package under windows 64

[R.N. Tsai]

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." <rbailey at grenfell.mun.ca>
 To: R.N. Tsai <r_n_tsai at yahoo.com> 
Cc: GAP Forum <forum at 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-bounces at gap-system.org [mailto:forum-bounces at gap-system.org] On Behalf Of R.N. Tsai
Sent: July-07-16 5:28 PM
To: Alexander Konovalov <alexander.konovalov at st-andrews.ac.uk>
Cc: GAP Forum <forum at 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.konovalov at st-andrews.ac.uk>
 To: R.N. Tsai <r_n_tsai at yahoo.com>
Cc: GAP Forum <forum at 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_tsai at 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 at 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.