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.

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., IT-32, 1, 54-62, 1986.

See also:

[URL="http://http://www4.ncsu.edu/~kaltofen/bibliography/91/KaSa91.pdf"]Kaltofen and Saunders, On Wiedemann's Method Solving Sparse Linear Equations[/URL]

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 CADO-NFS. Unfortunately scaling to large problems disqualifies the implementation for tutorial applications. The same is true of the BL code in Msieve.

I used Montgomery's paper in order to implement Block Lanczos for my PSIQS implementation in Java. It is not very difficult to follow.

[QUOTE=alpertron;416306]I used Montgomery's paper in order to implement Block Lanczos for my PSIQS implementation in Java. It is not very difficult to follow.[/QUOTE]

may I have a copy of your Java implementation?

His page is [URL="http://www.alpertron.com.ar/ENGLISH.HTM"]here[/URL], I know from the past that it contains the source codes, too, but I didn't check recently

[QUOTE=paul0;416307]may I have a copy of your Java implementation?[/QUOTE]

If you are trying to implement the method, Peter's paper will be far more useful.
It explains many things that the code will not.

[QUOTE=paul0;416307]may I have a copy of your Java implementation?[/QUOTE]
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).