mersenneforum.org Block Wiedemann for beginners
 Register FAQ Search Today's Posts Mark Forums Read

 2015-11-15, 14:02 #1 paul0   Sep 2011 3×19 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 2015-11-15 at 15:00
 2015-11-15, 20:34 #2 sean     Aug 2004 New Zealand 110111102 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., IT-32, 1, 54-62, 1986. See also: Kaltofen and Saunders, On Wiedemann's Method Solving Sparse Linear Equations
 2015-11-15, 23:43 #3 jasonp Tribal Bullet     Oct 2004 33·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 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
 2015-11-16, 14:04 #4 alpertron     Aug 2002 Buenos Aires, Argentina 22·337 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.
2015-11-16, 14:17   #5
paul0

Sep 2011

3·19 Posts

Quote:
 Originally Posted by alpertron 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?

 2015-11-16, 14:33 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 5·1,877 Posts His page is here, I know from the past that it contains the source codes, too, but I didn't check recently
2015-11-16, 14:34   #7
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by paul0 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.

2015-11-16, 17:09   #8
alpertron

Aug 2002
Buenos Aires, Argentina

101010001002 Posts

Quote:
 Originally Posted by paul0 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

 Similar Threads Thread Thread Starter Forum Replies Last Post ravlyuchenko Msieve 5 2011-05-09 13:16 pstach Factoring 25 2009-01-04 12:46 Bundu Lone Mersenne Hunters 3 2008-12-30 17:41 fivemack Math 0 2008-06-16 10:57 BWetter246 GMP-ECM 5 2006-11-15 13:19

All times are UTC. The time now is 17:00.

Wed Apr 21 17:00:24 UTC 2021 up 13 days, 11:41, 0 users, load averages: 2.64, 2.48, 2.31