mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-10-04, 17:33   #1
paul0
 
Sep 2011

3·19 Posts
Default 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 Si and Winv. 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 Si*SiT based on S. I think to form Si*SiT 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, Si-1 is an input to this function, but I don't see it was used there. What am I missing?
Attached Thumbnails
Click image for larger version

Name:	j.ins.2016.09.052.1.jpg
Views:	43
Size:	46.9 KB
ID:	23475  

Last fiddled with by paul0 on 2020-10-04 at 17:56
paul0 is offline   Reply With Quote
Old 2020-10-04, 19:12   #2
paul0
 
Sep 2011

718 Posts
Default

I tried implementing M[x,x] = 1 as I mentioned above. It worked! ViT*A*Vi 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 Si*SiT.

Last fiddled with by paul0 on 2020-10-04 at 19:53
paul0 is offline   Reply With Quote
Old 2020-10-05, 02:07   #3
paul0
 
Sep 2011

3×19 Posts
Default

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.
paul0 is offline   Reply With Quote
Old 2020-10-05, 15:06   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·883 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2020-10-06, 05:20   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·3·7·137 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2020-10-06, 05:52   #6
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
Quote:
Originally Posted by henryzz View Post
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.
I agree with you both. I kept trying sporadically since 2015. Aside from Yang's paper, this recent C++ implementation also helped me (https://github.com/SebWouters/blanczos). It is well commented and seemed to written as teaching tool, though there are a few optimizations which may confuse beginners.

Here are the rest of the pseudocode from Yang's paper (full paper behind paywall): https://www.sparrho.com/item/an-impr...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 2020-10-06 at 06:23
paul0 is offline   Reply With Quote
Old 2020-10-06, 07:10   #7
paul0
 
Sep 2011

3·19 Posts
Default

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 Vi+1 were chosen in Si and/or Si-1". 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?
paul0 is offline   Reply With Quote
Old 2020-10-06, 08:12   #8
Chris Card
 
Chris Card's Avatar
 
Aug 2004

2×5×13 Posts
Default

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/factor-b...ockLanczos.cpp
Chris Card is offline   Reply With Quote
Old 2020-10-08, 04:09   #9
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by Chris Card View Post
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/factor-b...ockLanczos.cpp

appreciate it, thanks
paul0 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Msieve with MPI block Lanczos jasonp Msieve 104 2013-06-17 11:28
block wiedemann and block lanczos ravlyuchenko Msieve 5 2011-05-09 13:16
Why is lanczos hard to distribute? Christenson Factoring 39 2011-04-08 09:44
Block Lanczos with a reordering pass jasonp Msieve 18 2010-02-07 08:33
Lanczos error Andi47 Msieve 7 2009-01-11 19:33

All times are UTC. The time now is 05:47.

Sat Dec 5 05:47:30 UTC 2020 up 2 days, 1:58, 0 users, load averages: 1.90, 2.05, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.