mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-11-15, 14:02   #1
paul0
 
Sep 2011

3×19 Posts
Default 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 2015-11-15 at 15:00
paul0 is offline   Reply With Quote
Old 2015-11-15, 20:34   #2
sean
 
sean's Avatar
 
Aug 2004
New Zealand

2·3·37 Posts
Default

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:

Kaltofen and Saunders, On Wiedemann's Method Solving Sparse Linear Equations
sean is offline   Reply With Quote
Old 2015-11-15, 23:43   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353410 Posts
Default

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.

Last fiddled with by jasonp on 2015-11-15 at 23:46
jasonp is offline   Reply With Quote
Old 2015-11-16, 14:04   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×11×61 Posts
Default

I used Montgomery's paper in order to implement Block Lanczos for my PSIQS implementation in Java. It is not very difficult to follow.
alpertron is offline   Reply With Quote
Old 2015-11-16, 14:17   #5
paul0
 
Sep 2011

3×19 Posts
Default

Quote:
Originally Posted by alpertron View Post
I used Montgomery's paper in order to implement Block Lanczos for my PSIQS implementation in Java. It is not very difficult to follow.
may I have a copy of your Java implementation?
paul0 is offline   Reply With Quote
Old 2015-11-16, 14:33   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

243116 Posts
Default

His page is here, I know from the past that it contains the source codes, too, but I didn't check recently
LaurV is offline   Reply With Quote
Old 2015-11-16, 14:34   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by paul0 View Post
may I have a copy of your Java implementation?
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-11-16, 17:09   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·11·61 Posts
Default

Quote:
Originally Posted by paul0 View Post
may I have a copy of your Java implementation?
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 2015-11-16 at 17:10
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
block wiedemann and block lanczos ravlyuchenko Msieve 5 2011-05-09 13:16
Yet another Block Wiedemann thread pstach Factoring 25 2009-01-04 12:46
LMH for Beginners on V5 Bundu Lone Mersenne Hunters 3 2008-12-30 17:41
Very basic question about Wiedemann methods fivemack Math 0 2008-06-16 10:57
ECM Factoring for beginners BWetter246 GMP-ECM 5 2006-11-15 13:19

All times are UTC. The time now is 14:04.

Fri Feb 26 14:04:16 UTC 2021 up 85 days, 10:15, 0 users, load averages: 1.95, 1.91, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.