mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Block Wiedemann for beginners (https://www.mersenneforum.org/showthread.php?t=20664)

paul0 2015-11-15 14:02

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.

sean 2015-11-15 20:34

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]

jasonp 2015-11-15 23:43

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.

alpertron 2015-11-16 14:04

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

paul0 2015-11-16 14:17

[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?

LaurV 2015-11-16 14:33

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

R.D. Silverman 2015-11-16 14:34

[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.

alpertron 2015-11-16 17:09

[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).


All times are UTC. The time now is 13:36.

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