Working with BigInt type

General Usage
1

I have a set of p=100 covariates with some covariance matrix given for example by:

using LinearAlgebra
L=Symmetric(rand(100,100))

I need to extract submatrices from L and perform some operations. However, I have a very large number of submatrices to extract:

using Combinatorics
n=32
neig=combinations(1:100,n-1)

The variables neig is stored in a Base.Generator type. I cannot extract all the elements with collect(neig) because I get ERROR: OverflowError: binomial(100, 31) overflows, so I let it stored in neig. I want to apply a simple function like:

map(x->det(L[x,x]),neig)

but I get ERROR: OverflowError: binomial(100, 31) overflows . I get similar errors with other functions and operations I have to do with neig. If the matrix L is smaller, for example with size 5 x 5, the code works perfectly and I don’t have any trouble. How can I work with objects stored in Base.Iterators of Base.Generator types with a very large number of elements, like the variable neig? I’m not even able to create an empty null vector with zeros(length(neig_minus.iter)) for storing loop results with enumerate() because I get the same error. What are my options? Thank you !

2

The reason you’re seeing an overflow error is of course that binomial(100, 31) > typemax(Int64). The reason that’s being computed at all is that that’s the length of the combinatorics object your have in neig.

julia> binomial(big(100), 31)
66324638306863423796047200

So there are roughly 600 septillion combinations. Trying to allocate a vector of this length fails because no computer has enough memory (even if you’re just making a float array, that’s like 10 billion exa-bytes :rofl:).

The fact is that you could iterate over it without using map as in:

for c in combinations(1:100, n-1)
    det(L[c, c])
end

but it would take on the order of a trillion years.

Chances are that you probably need a different approach to the problem you’re trying to solve. I don’t know this for a fact, but perhaps there’s a way to efficiently compute all the determinants using a dynamic programming approach (combining the solution of a series of subproblems). Computing each one separately is definitely repeating a lot of work under the hood that could be shared between the calculations. Not to mention that the solution could never be stored in its entirety.

3 Likes
3

I understand, yes :slight_smile: I’ll try another approach :slight_smile: As I’m still a beginner with Julia, I thought there could be some hidden functionality or procedure. I even tried to explore the Int128 format :slight_smile:
Thanks for your advice anyway!