search

JuliaLang / julia

The Julia Programming Language
https://julialang.org/
MIT License
45.09k stars 5.43k forks source link

Efficient linear algebra over GF(2) #8469

Closed raichu closed 9 years ago

raichu commented 9 years ago

Does Julia somehow support doing linear algebra (SVD, etc.) with sparse matrices over Galois field GF(2)?

If yes, I'm particularly wondering about if the representation of the matrix is efficient (one bit per entry, basic operations such as multiplication are realized using bitwise operatorions etc.). Is it somehow doable with the IntModN package?

johnmyleswhite commented 9 years ago

This seems like a question that would be more appropriate for the julia-users mailing list.

stevengj commented 9 years ago

See #5429: some but not all of the linear-algebra operations support generic Number fields.

I think you may need to implement your own AbstractArray type, based on BitArray if you want one bit per entry storage. This is possible, but it is probably faster to use one byte per entry storage, and that is supported by IntModN.jl. However, IntModN currently uses a generic mod operation (which is slow because of #8188), so you might need your own type to exploit bit operations for modulus 2. That would not be hard to implement, however.

Sparsity is another matter...it's not clear how much you want to exploit sparsity if you want to compute things like an SVD (which is generally not sparse). Depends a lot on what you are trying to do.

JeffBezanson commented 9 years ago

Yes, check out BitArray. Other than that, see #5429.

raichu commented 9 years ago

Can't see how that's going to work for me.

timholy commented 9 years ago

That's a pretty puzzling remark, @raichu, but in any event further discussion should be moved to julia-users.

raichu commented 8 years ago

Sorry for not being explicit. As far as I see

Hence I can't see how BitArray or #5429 is going to help me.

I'll create two issues for these.

JeffBezanson commented 8 years ago

I would try the IntModN package together with our existing sparse matrix support and perhaps IterativeSolvers.jl. If that doesn't work we'd be interested to hear what goes wrong.