How to get nullspace of large sparse matrix using block wiedemann in linbox?

[kwondawoon]

I'm very new to linbox.

I have a large sparse matrix (about 200,000x150,000 ).

I want to get nullspace using block wiedemann in linbox.

how to get the nullspace by BW? please tell me how.

[bdsaunders]

There is not currently an off the shelf nullspace basis code for sparse matrices in linbox. That said, the components are all there and work on this is part of my personal to-do list. i'd be glad to help.

Questions:

1. context: is it an integer matrix or over a finite field?

2. size of problem: Do you have an estimate of the rank? What is the density of nonzeroes? left or right nullspace?

3. method: Why BW in particular --- Is the goal simply the result or also the method to be used is relevant to your purposes?

4. partial? Would random nullspace vectors help or is full basis needed?

Best, -dave

On Mon, Jul 30, 2018 at 6:43 AM, kwondawoon notifications@github.com wrote:

I'm very new to linbox.

I have a large sparse matrix (about 200,000x150,000 ).

I want to get nullspace using block wiedemann in linbox.

how to get the nullspace by BW? please tell me how.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/linbox-team/linbox/issues/130, or mute the thread https://github.com/notifications/unsubscribe-auth/ADk6I-pyFZsFWFtmuvPcCClC-YsegVLNks5uLuM8gaJpZM4VmLta .

[kwondawoon]

Thank you for your reply.

1. I have binary matrix ( over GF(2) )

2. The rank of matrix is almost full rank and the number of nonzero per row is 2,000~3,000. I want to get left nullspace of m x n rectangular matrix (m>n)

3. Since I don't want to store full matrix, I want to use BW.

4. Until I get nullspace vector as many as I want. It is almost full basis nullspace.

Thank you for your help.

-dawoon

[bdsaunders]

Hi again, Dawoon,

It does sound like a case for BW. I am going to suggest the version described in the very recent thesis of Gavin Harrison and currently in the branch "poly-smith-form" of LinBox.

Let A be your matrix with zero columns appended to make it square, nxn, where n is about 200000. Do you know if A is semi-simple (for all row vectors x, xA^2 = 0 implies xA = 0), or nearly so? This affects whether preconditioning is desirable.

Let me discuss how some recent work (Gavin's thesis as well as Pascal Giorgi's recent update of block order basis computation) and some current work (Matthew Lambert's project on fast sparse matrix matrix product) could play into solving the problem.

Part 0. Choose preconditioning, B = PA, where P is random, (very) sparse, and nonsingular. P may or may not be necessary.

Part 1. For blocksize b, compute blocks s_i = U^T B^i V, where U and V are random bxn matrices. A small blocksize will suffice. Gavin's thesis suggests as small as b = 12. At each step you know Y = B^{i-1} V, so you multiply by A getting Z = BY = B^i V. and then do the dense product UZ. Four Russians multiplication can be done for the dense product UZ (M4RI). Clever representation of A and P --- possibly with a scheme under development by Matthew --- can play a big role in making the spmm product BY be fast. In LinBox this part 1 is done by making a suitable BlockBlackboxContainer object.

Part 2. Block Berlekamp Massey or order basis, to obtain a bxb matrix minimal polynomial. Probably order basis.

Part 3. Use Gavin's Poly Smith form stuff to get a scalar polynomial (hopefully not divisible by x^2, of form xf(x), where f(0) = 0. (We hope preconditioning has made it semi-simple so that this is true.) If it is not semi-simple adjustments will be necessary in the final step.

Part 4. Compute nullspace vectors N = Rf(B), where random R has row dimension as large as you like.(Matthew's code likely will perform more efficiently with more rows). Adjust for the fact that B = PA, of course.

If you want to do this on your own, my suggestion is to start with making a custom block blackbox container which will encapsulate the use of your matrix and provide the interface for the later parts. If you are willing to share your matrix, I can ask Matthew (a PhD student here at UD) to try his methods for speeding up sparse matrix product.

Best, -dave

On Tue, Jul 31, 2018 at 2:07 AM, kwondawoon notifications@github.com wrote:

Thank you for your reply.

1.

I have binary matrix ( over GF(2) ) 2.

The rank of matrix is almost full rank and the number of nonzero per row is 2,000~3,000. I want to get left nullspace of m x n rectangular matrix (m>n) 3.

Since I don't want to store full matrix, I want to use BW. 4.

Until I get nullspace vector as many as I want. It is almost full basis nullspace.

Thank you for your help.

-dawoon

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/linbox-team/linbox/issues/130#issuecomment-409105676, or mute the thread https://github.com/notifications/unsubscribe-auth/ADk6I0iCtxEz7wx1n5o9AUjfevb7mQONks5uL_QFgaJpZM4VmLta .