Large Matrix Powers in Julia

Question

I am working with very large graphs and their corresponding weighted adjacency matrices, and I need to take these large matrices to similarly large powers (i.e. raising matrices to the power of tens of thousands).

The issue I have run into is that elements of the matrix quickly become too large for the computer to handle, and I am wondering how to get around this problem.

Has anyone worked with such problems before(raising matrices to large powers), and how did you resolve them?

I know Python's numpy can handle these computations. Is there an analogous library in Julia that can do this as well?

@user14717 It can be diagonalized, would diagonalizing circumvent the issue? As you would still be dealing with large numbers, especially after converting back to original form. — GEG
If you have the eigendecomposition A = U'DU you can just take the desired power of D, that is the eigenvalues on the diagonal. — carstenbauer
Eventually, you will always mix different scales (eigenvalues) when applying the basis transformation U. But this is pretty much unavoidable. — carstenbauer
Yes, however upon operating on D, how can you be sure that the numerical entries are represented in a way such that they do not have too many digits, leading to corruption? — GEG

Bill Bill · Accepted Answer · 2019-12-09T22:29:46

You could do a transfomation of type to BigFloat:

julia> A = [1.5 2 -4; 3 -1 -6; -10 2.3 4]
3×3 Array{Float64,2}:
   1.5   2.0  -4.0
   3.0  -1.0  -6.0
 -10.0   2.3   4.0

julia> (BigFloat.(A))^32000
3×3 Array{BigFloat,2}:
  4.16164e+31019   8.71351e+31017  -3.22788e+31019
  4.60207e+31019   9.63565e+31017  -3.56949e+31019
 -5.83403e+31019  -1.22151e+31018   4.52503e+31019

Large Matrix Powers in Julia

1 Answers