CODEWITHSUNDEEP
pythonnumpyscipyoverflow
John
John

Reputation: 49

How to avoid overflow in calculation matrix determinant with large elements

I am going to calculate the determinant of a random 2D-matrix (G) in Python. The matrix is of size about 30 by 30, where each element is chosen randomly from a large prime field with characteristic P using random.randrange(0,P) (e.g. P= 2^160 - 47). The problem is that when I use det command of both scipy and numpy they return inf. After finding determinant, I want to find the answer in the prime field, that is det(G)% P.

Is there any way to calculate this? Thank you in advance.

Here is a sample code:

import numpy as np
import random
from scipy.linalg import det
N= 30
p = 2**160 - 47
G = np.zeros((N, N))
    
for i in range(N):
   for j in range(N):
      G[i][j] = random.randrange(0, p)

ans = det(G)%p

Upvotes: 0

Views: 265

Answers (1)

Warren Weckesser
Warren Weckesser

Reputation: 114831

NumPy is not the right tool for this. You need a library that can handle arbitrarily large integers. One option is SymPy. SymPy even has the function randMatrix that can generate your random matrix. For example,

import random
from sympy import randMatrix


N = 30
p = 2**160 - 47

G = randMatrix(N, min=0, max=p-1)

ans = G.det() % p
print(ans)

A typical run prints

381271413373650154061019607002336594108159531272

In the call of randMatrix, I used max=p-1, because the docstring for randMatrix implies that the function random.Random.randint will be used to generate the random entries in the matrix, and that function includes max in the possible random values. randrange does not include max.

Upvotes: 1

Related Questions