Why is work with Q in qr() is so expensive?

General Usage Performance
, ,
1

In the picture below, we can see that it is very efficient to generate a random unitary matrix Q using the qr() function in LinearAlgebra.

However, if we want to work with the generated Q, it appears to be very expensive in memory and time. With size 401 by 401, Q*1 takes 24 seconds and 1.5 GiB of memory, with size 500 by 500 it appears to take forever.

I wonder what is the reason for this, and how to walk around this issue.

:pray:Thank you!

image
image908×698 39.7 KB

2

this is really strange and could be a bug.
Try Q = convert(Matrix,qr(A).Q) * 1 as a workaround

2 Likes
3

Works ! :pray:

1 Like
4

This appears to hit a very slow fallback:

julia> @which Q*1
*(A::AbstractArray, B::Number) in Base at arraymath.jl:55

Can you open an issue?

2 Likes
5

I have just raised an issue here.

1 Like
6

I have also responded in the issue, but let me repeat here for convenience:

julia> for i in 1:100:500

           A = randn(i,i)
           println("Size = $i")
           printstyled("Time took for q : ", color=:green)
           @time Q = qr(A).Q
           printstyled("Time took for Q*1 : ", color=:red)
           @time Q = Q*1
           println("")
       end
Size = 1
Time took for q :   0.000008 seconds (5 allocations: 352 bytes)
Time took for Q*1 :   0.000010 seconds (2 allocations: 192 bytes)

Size = 101
Time took for q :   0.000418 seconds (8 allocations: 136.922 KiB)
Time took for Q*1 :   0.000158 seconds (4 allocations: 159.656 KiB)

Size = 201
Time took for q :   0.000888 seconds (8 allocations: 429.109 KiB)
Time took for Q*1 :   0.000433 seconds (4 allocations: 631.531 KiB)

Size = 301
Time took for q :   0.001847 seconds (8 allocations: 877.547 KiB)
Time took for Q*1 :   0.001077 seconds (4 allocations: 1.383 MiB)

Size = 401
Time took for q :   0.003631 seconds (8 allocations: 1.447 MiB)
Time took for Q*1 :   0.003361 seconds (4 allocations: 2.454 MiB)

julia> @which qr(randn(2,2)).Q * 1
*(A::LinearAlgebra.AbstractQ, b::Number) in LinearAlgebra at /Users/crstnbr/repos/julia/usr/share/julia/stdlib/v1.7/LinearAlgebra/src/qr.jl:618

julia> versioninfo()
Julia Version 1.7.0-DEV.915
Commit 2ba139c48e* (2021-04-13 04:20 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin20.3.0)
  CPU: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
Environment:
  JULIA_EDITOR = subl
  JULIA_NUM_THREADS = 6
  JULIA_PKG_SERVER = eu-central.pkg.julialang.org

So this issue seems to be fixed on master (Julia 1.7-DEV)

2 Likes
7

For reference: It was fixed in the PR #39533.

1 Like