20151115, 14:02  #1 
Sep 2011
111001_{2} Posts 
Block Wiedemann for beginners
Hello, I'm trying to implement a faster LA step instead my current Gaussian Reduction implementation. As what usually happens with new concepts, I can't comprehend how Block Wiedemann works. I think I will eventually understand it  I've gotten this far with NFS. For now, please point out papers, code, or examples that may help me understand Block Wiedemann.
Thanks. Edit: I just realized that this forum has more experience with Block Lanczos. Is there a dummy example I can work with? I tend to understand things better with that. Last fiddled with by paul0 on 20151115 at 15:00 
20151115, 20:34  #2 
Aug 2004
New Zealand
2·3·37 Posts 
I don't know a lot about it, but the original paper by Wiedemann is:
Douglas H. Wiedemann, Solving Sparse Linear Equations Over Finite Fields, IEEE Trans. Info. Th., IT32, 1, 5462, 1986. See also: Kaltofen and Saunders, On Wiedemann's Method Solving Sparse Linear Equations 
20151115, 23:43  #3 
Tribal Bullet
Oct 2004
3^{3}×131 Posts 
Neither block Lanczos nor block Wiedemann have a tutorial article available that explains them step by step; also, neither are amenable to small examples, as both methods require a matrix several times larger than the block size in order to need several iterations. Just making the block size 2 isn't safe either, as solving a matrix that small can work by random chance even if the implementation is broken.
Pretty much the only BW available that can scale to large problems is in CADONFS. Unfortunately scaling to large problems disqualifies the implementation for tutorial applications. The same is true of the BL code in Msieve. Last fiddled with by jasonp on 20151115 at 23:46 
20151116, 14:04  #4 
Aug 2002
Buenos Aires, Argentina
2^{3}×13^{2} Posts 
I used Montgomery's paper in order to implement Block Lanczos for my PSIQS implementation in Java. It is not very difficult to follow.

20151116, 14:17  #5 
Sep 2011
111001_{2} Posts 

20151116, 14:34  #7 
Nov 2003
2^{2}×5×373 Posts 

20151116, 17:09  #8 
Aug 2002
Buenos Aires, Argentina
2^{3}×13^{2} Posts 
My code is not intended to be digested by students, because I tried to make it as optimized as possible. So it will not be useful for you. I recommend you to download Peter Montgomery's paper (I do not know if it is still online).
Last fiddled with by alpertron on 20151116 at 17:10 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
block wiedemann and block lanczos  ravlyuchenko  Msieve  5  20110509 13:16 
Yet another Block Wiedemann thread  pstach  Factoring  25  20090104 12:46 
LMH for Beginners on V5  Bundu  Lone Mersenne Hunters  3  20081230 17:41 
Very basic question about Wiedemann methods  fivemack  Math  0  20080616 10:57 
ECM Factoring for beginners  BWetter246  GMPECM  5  20061115 13:19 