Block Wiedemann for beginners

paul0 · 2015-11-15, 14:02

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:

Kaltofen and Saunders, On Wiedemann's Method Solving Sparse Linear Equations

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:

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?

LaurV · 2015-11-16, 14:33

His page is here, 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:

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.

alpertron · 2015-11-16, 17:09

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

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, 23:43	#3
jasonp Tribal Bullet Oct 2004 5×23×31 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

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

2015-11-15, 20:34	#2
sean Aug 2004 New Zealand 2·5·23 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-16, 14:04	#4
alpertron Aug 2002 Buenos Aires, Argentina 2·761 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:33	#6
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 24060₈ Posts	His page is here, I know from the past that it contains the source codes, too, but I didn't check recently