View Single Post
Old 2020-10-06, 05:52   #6
Sep 2011

3×19 Posts

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.
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 ( 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):

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