Problem of the calculation of matrix

Specific Domains Numerics
1

Background :

I use Julia to construct Symmetric normalized Laplacian matrix L^{sym} (Matrix D is a diagonal matrix):L^{sym}=D^{-1/2}×L×D^{-1/2}. Matrix L^{sym} is a sparse matrix.

My computer configuration:

julia> versioninfo()
Julia Version 1.2.0
Commit c6da87ff4b (2019-08-20 00:03 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, ivybridge)

My code:

D = ... # sparse matrix
L = ... # sparse matrix
Lsym = D^(-0.5)*L*D^(-0.5)

Question:

  • When L is 10000 × 10000 sparse matrix , the calculation speed of L^{sym} is fine.
  • When L is 100000 × 100000 sparse matrix , the calculation speed of L^{sym} is very slow.

I wonder if there’s a faster way to calculate L^{sym}, or my code has problems calculating large sparse matrix.

2

Try

sqrtD = sqrt(D) 
Lsym = sqrtD*L*sqrt(D)

It should make it at least twice as fast.

1 Like
3

In your code, you wrote D = ... # sparse matrix but mentioned that D is diagonal. You could probably save some additional time by using D = Diagonal(vector_of_coefficients_on_the_diagonal).
(I assume that your D is a sparse matrix right now.)

1 Like
4

Thank you for your reply. I tried it according to your method. It has a very obvious acceleration effect on my computer! :grinning:

5

Thank you for your reply, I think I may understand what you mean. But because it’s D^{-1/2}, so maybe it should be:

using LinearAlgebra

sqrtD = Diagonal(rand(1:1,10000))/sqrt(D) # Diagonal(rand(1:1,10000)) is to build an identity matrix
Lsym = sqrtD*L*sqrtD

According to your method, it‘s really much faster. Thank you！:grinning:

1 Like