mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2008-10-29, 05:04   #1
Greenk12
 
Oct 2008

E16 Posts
Default Help about document for Msieve 1.38

Hello everybody!

I am Binh. I am a student. Now, i am studying about factoring and Msieve. So I hope i will be received your help.

I want to know about Block Lanczos implementation in Msieve program.
I've already read about Block Lanczos theory ( document that i read : A New Parallel Approach to the Block Lanczos Algorithm for Finding Nullspaces over GF(2) - by I Flesch, A Block Lanczos Algorithm for Finding Dependencies over GF(2) - by Peter L.Montgomery)

I understanded Block Lanczos theory, but i don't understand Block Lanczos of implementation in Msieve program, especially :

uint64 * block_lanczos(msieve_obj *obj, uint32 nrows,
uint32 num_dense_rows, uint32 ncols,
la_col_t *B, uint32 *num_deps_found)
{...}

i don't understand what form matrix B that i need to pass in block_lanczos function.

Could you explaint it to me? Or Could you show me an example a matrix B that i need to pass in block_lanczos function ?

Could you show me any document about your block_lanczos of implementation ?

Thank you for reading!
Hope being received your help.
Greenk12 is offline   Reply With Quote
Old 2008-10-29, 13:05   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

Msieve represents matrices by column, because they're built one column at a time; B is an array of ncols matrix columns, and each column is given an la_col_t structure. The la_col_t has two fields:

- the count of sparse nonzero elements in that column
- an array of 32-bit words to hold the row numbers containing a 1 for
that column

Rows are numbered from 0 to (nrows - 1), and the first num_dense_rows rows are considered dense. The array has one 32-bit word for each of the sparse rows (sorted by increasing row index), and then (num_dense_rows+31)/32 words where the nonzero dense rows are stored in packed (bitwise) form. Dense row i gets bit i in this latter array. QS matrices always have num_dense_rows = 0, and the same block Lanczos code is used by both QS and NFS.

There is very little linear algebra documentation outside comments in the code, but the algorithm is exactly as described in Montgomery's initial paper.

Last fiddled with by jasonp on 2008-10-29 at 13:07
jasonp is offline   Reply With Quote
Old 2008-10-30, 02:51   #3
Greenk12
 
Oct 2008

2×7 Posts
Default

Yes, I see.

Thank you very much.

Continue working.
Greenk12 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
msieve on KNL frmky Msieve 3 2016-11-06 11:45
Msieve on a Mac (Help) pxp Msieve 1 2013-02-28 14:56
Using msieve with c burrobert Msieve 9 2012-10-26 22:46
msieve help em99010pepe Msieve 23 2009-09-27 16:13
fun with msieve masser Sierpinski/Riesel Base 5 83 2007-11-17 19:39

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

Sun Sep 20 14:29:52 UTC 2020 up 10 days, 11:40, 1 user, load averages: 1.62, 1.43, 1.43

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