20201004, 17:33  #1 
Sep 2011
3·19 Posts 
trying to implement block lanczos on GF2...
Hi, I'm currently trying to implement Block Lanczos, but I'm having some trouble understanding the notation on calculating S_{i} and W_{inv}. I'm reading Montgomery's paper and Yang et. al.'s pseudocode (attached).
On line 13 of the attached file, the algorithm seems to create a set S of row & col where a 1 is found. Eventually I need to compute S_{i}*S_{i}^{T} based on S. I think to form S_{i}*S_{i}^{T} I just need to set M[x,x] = 1 for each x ∈ S. M is a square matrix with side size of machine word (as defined by the paper) rows and cols. Is this correct? Also, S_{i1} is an input to this function, but I don't see it was used there. What am I missing? Last fiddled with by paul0 on 20201004 at 17:56 
20201004, 19:12  #2 
Sep 2011
3×19 Posts 
I tried implementing M[x,x] = 1 as I mentioned above. It worked! V_{i}^{T}*A*V_{i} becomes zero. However, it seems that not all X  Y are nullspaces of B. I got 10 out of 32 valid nullspace, then 6 out of 32 on a matrix with more dependencies. The paper says I need to combine these vectors. How do I do that? gaussian elimination?
I'd like to mention that I'm avoiding optimizations for now, like the ANDing of S_{i}*S_{i}^{T}. Last fiddled with by paul0 on 20201004 at 19:53 
20201005, 02:07  #3 
Sep 2011
71_{8} Posts 
It seems that I missed an entire paragraph about the last step with gaussian elmination. will try to implement that first. also, RIP Peter Montgomery.

20201005, 15:06  #4 
Tribal Bullet
Oct 2004
6716_{8} Posts 
You figured it out, but yes the block Lanczos algorithm finds the nullspace of A^T*A and not of A, since the algorithm only works for symmetric matrices.To get the answers you need, Gauss elimination of the nullspace vectors you have is necessary.
I remember how great it felt when I managed to get the code running on a real problem, BL is hard to figure out from papers, or even from other people's code. 
20201006, 05:20  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
11×17×31 Posts 
It looks like Yang's paper is an improvement to clarity. I have tried and failed with other references in the past. Time for another go at some point. Congratulations on getting this working.

20201006, 05:52  #6  
Sep 2011
3·19 Posts 
Quote:
Quote:
Here are the rest of the pseudocode from Yang's paper (full paper behind paywall): https://www.sparrho.com/item/animpr...zation/9c93ad/ I got the last step working and got it to work with my toy NFS implementation. The terms Montgomery used for the last step (page 114) were unfamiliar to me, so I'm a bit suspicious that by running gaussian elimination, I may have bypassed the entire Block Lanczos process. Also, I don't know yet how to not compute U explicitly. I have 2 questions: 1. Is it normal for the first dependency to be always trivial? 2. The very last output is "a basis for ZU". This just means the nullspaces of B are the columns of ZU? EDIT: it seems that i'm in the wrong subforum, feel free to move this thread mods. Last fiddled with by paul0 on 20201006 at 06:23 

20201006, 07:10  #7 
Sep 2011
57_{10} Posts 
I'd like to add a third question:
3. In Montgomery's paper p. 115, he writes: "Afterwards I check whether all nonzero columns of V_{i+1} were chosen in S_{i} and/or S_{i1}". This assertion is implemented in the c++ implementation I linked above. What would happen if I do not implement this assertion? Will my implementation silently fail for some inputs? 
20201006, 08:12  #8 
Aug 2004
2×5×13 Posts 
For what it's worth, here's my C++ implementation of block lanczos that I wrote a few years ago, based on Montgomery's paper:
https://github.com/ChrisCGH/factorb...ockLanczos.cpp 
20201008, 04:09  #9  
Sep 2011
71_{8} Posts 
Quote:
appreciate it, thanks 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Msieve with MPI block Lanczos  jasonp  Msieve  104  20130617 11:28 
block wiedemann and block lanczos  ravlyuchenko  Msieve  5  20110509 13:16 
Why is lanczos hard to distribute?  Christenson  Factoring  39  20110408 09:44 
Block Lanczos with a reordering pass  jasonp  Msieve  18  20100207 08:33 
Lanczos error  Andi47  Msieve  7  20090111 19:33 