QR Decomposition Extremely Slow

linearalgebra

#1

It seems converting a Q matrix to a Float Matrix takes high-degree polynomial time at best.

Is this a bug? If so, is there any way to work around it? I don’t remember having this problem on earlier versions (I am using 1.01). Granted my laptop is pretty slow, but this is worse than matrix inversion, so the performance doesn’t make a lot of sense to me.

using LinearAlgebra
function mwe()
  local Q::Matrix{Float64}

  X = rand(200,13)
  f = qr(X)
  @time Q = Matrix{Float64}(f.Q)

  X = rand(400,13)
  f = qr(X)
  @time Q = Matrix{Float64}(f.Q)

  X = rand(600,13)
  f = qr(X)
  @time Q = Matrix{Float64}(f.Q)

  X = rand(800,13)
  f = qr(X)
  @time Q = Matrix{Float64}(f.Q)
end

mwe()

Output:
0.260873 seconds (120.00 k allocations: 145.569 MiB, 1.49% gc time)
2.115116 seconds (480.00 k allocations: 1.022 GiB, 3.70% gc time)
6.812497 seconds (1.08 M allocations: 3.372 GiB, 4.46% gc time)
15.563167 seconds (1.92 M allocations: 7.901 GiB, 3.08% gc time)


#2

I am seeing similar behavior in 1.0 on a Windows 10 machine. I would say this is a bug. Unless someone else sees an obvious problem with your code, I suggest that you open an issue.


#3

#4

Issue opened: # 29846


#5

RalphAS on the GitHub issue thread (# 29846) noted that we can drop the type parameter and recover performance, e.g. writing Matrix{Float64}(f.Q). This workaround fixed the slowness in my code, so I will count the question as solved.