# In-place computation of Q (from QR decomposition)

**URL:** <https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881>\
**Category:** General Usage\
**Created:** [November 27, 2022, 3:20am UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881 "2022-11-27T03:20:51Z")\
**Posts on this page:** 16\
**Page:** 2

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 28, 2022, 3:56pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/22 "2022-11-28T15:56:24Z")

</div>

That is a lovely idea! Quite a bit faster!

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 28, 2022, 5:48pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/23 "2022-11-28T17:48:19Z")

</div>

> [@juthohaegeman](#):
>
> `lmul!(q.Q, Matrix{eltype(A)}(I, size(A)))`

I want to accomplish this:

```julia
q = qr!(A)
A .= Matrix(q.Q)

```

I apologize for being dense, but I fail to see how your example accomplishes that.

---

<div class="post-metadata">

**Author:** ![mstewart](https://avatars.discourse-cdn.com/v4/letter/m/b5a626/32.png) [@mstewart](https://discourse.julialang.org/u/mstewart)\
**Post date:** [November 28, 2022, 6:52pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/24 "2022-11-28T18:52:13Z")

</div>

That call to `lmul!` should return the orthogonalized matrix. (And does when I run it.) Is it the part about doing it in-place in `A` that you are worried about? That seems problematic, given that `A` is being used to store the Householder vectors in `q.Q`. I don’t know a way to completely avoid allocating a new matrix to store the non-Householder representation of Q.

Edit: Digging a little, LAPACK has a routine [DORGQR](https://netlib.org/lapack/explore-3.1.1-html/dorgqr.f.html) that does exactly this for a QR factorization computed from of `dgeqrf` using an additional workspace array of size `NB*N` where `NB` is the block size. It’s even available in Julia at a low level:

```julia
julia> using LinearAlgebra

help?> LAPACK.orgqr!
  orgqr!(A, tau, k = length(tau))

  Explicitly finds the matrix Q of a QR factorization after calling geqrf! on A. Uses the output of geqrf!. A is overwritten by Q.

```

It looks like what `qr!` does, however, is call the alternate algorithm `dgeqrt`. I don’t see a fully in-place routine for constructing `Q` in that case. This should be workable, but maybe requires low level calls to LAPACK for `dgeqrf` and `dorgqr`. I don’t see anything higher level provided by `LinearAlgebra`, anyway, that would facilitate the use of `dorgqr`.

---

<div class="post-metadata">

**Author:** ![juthohaegeman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juthohaegeman/32/8620_2.png) [@juthohaegeman](https://discourse.julialang.org/u/juthohaegeman)\
**Post date:** [November 28, 2022, 6:52pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/25 "2022-11-28T18:52:36Z")

</div>

? I guess by then writing `A .= lmul!(q.Q, Matrix{eltype(A)}(I, size(A)))`. Note that this is a two step process; first `Matrix{eltype(A)}(I, size(A))` allocates a new matrix to store the result, in particular by initializing it as the first columns of the identity matrix. Then the result is written in that place using `lmul!(q.Q, Matrix{eltype(A)}(I, size(A)))`. Finally, the contents of that result is copied back into `A` using `A .= lmul!(q.Q, Matrix{eltype(A)}(I, size(A)))`

Not sure what you are after, but with Lapack QR you will not manage to make the columns of `A` orthogonal without allocating an intermediate result. The same happens with `A .= Matrix(q.Q)`. The call `Matrix(q.Q)` first allocates the result, which then afterwards is copied back into the memory of `A`.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 29, 2022, 1:04am UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/26 "2022-11-29T01:04:34Z")

</div>

> [@juthohaegeman](#):
>
> `A .= lmul!(q.Q, Matrix{eltype(A)}(I, size(A)))`

This is actually slower for me.

```julia
@time q = qr!(A)
@time A .= Matrix(q.Q)
@time A .= lmul!(q.Q, Matrix{eltype(A)}(I, size(A)))

```

gives

```julia
 30.569143 seconds (5 allocations: 562.625 KiB)                                                        
 51.667263 seconds (9 allocations: 5.968 GiB, 5.91% gc time)                                           
 64.343821 seconds (8 allocations: 2.988 GiB)      

```

An advantage seems to be half the allocation of `A .= Matrix(q.Q)`.

On Windows 10, single thread.

Edit: It is weird that there is a difference at all. `Matrix(q.Q)` seems to be implemented with `lmul!`!

> <https://github.com/JuliaLang/julia/blob/865007d701341526bc5442fcb2409a82a82a7ccd/stdlib/LinearAlgebra/src/qr.jl#L575>

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 29, 2022, 1:12am UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/27 "2022-11-29T01:12:09Z")

</div>

> [@mstewart](#):
>
> Edit: Digging a little, LAPACK has a routine [DORGQR](https://netlib.org/lapack/explore-3.1.1-html/dorgqr.f.html) that does exactly this for a QR QRQR factorization

Great find! I will pursue this a bit, since the cost of materializing Q is so huge.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 29, 2022, 1:18am UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/28 "2022-11-29T01:18:30Z")

</div>

> [@mstewart](#):
>
> At this point it’s organized as a blocked version of MGS, but it’s probably not fair to call it MGS. In applying `A1'` you are computing inner products with multiple orthogonalized columns at once which seems a bit more like classical Gram-Schmidt. Maybe it is best interpreted as a blocked hybrid.

This is a good question. On my test examples I saw very reasonable numerical stability. But, as you say, it is some form of hybrid algorithm.

---

<div class="post-metadata">

**Author:** ![juthohaegeman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juthohaegeman/32/8620_2.png) [@juthohaegeman](https://discourse.julialang.org/u/juthohaegeman)\
**Post date:** [November 29, 2022, 10:00am UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/29 "2022-11-29T10:00:21Z")

</div>

I am also suspicious that the timings are so different. As for the allocation, it seems that this was fixed only recently:

> <https://github.com/JuliaLang/julia/pull/46162>
>
> Convert instead of creating another copy.

---

<div class="post-metadata">

**Author:** ![mstewart](https://avatars.discourse-cdn.com/v4/letter/m/b5a626/32.png) [@mstewart](https://discourse.julialang.org/u/mstewart)\
**Post date:** [November 29, 2022, 12:20pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/30 "2022-11-29T12:20:21Z")

</div>

The interface in `LinearAlgebra.LAPACK` is really pleasant (if you can figure out which routines you want…), but the performance is not what I would have hoped for:

```julia
using LinearAlgebra

function computeQ!(A)
  m, n = size(A)
  k = min(m, n)
  tau = zeros(eltype(A), k)
  LAPACK.geqrf!(A, tau)
  LAPACK.orgqr!(A, tau, k)
  return A
end

@show Threads.nthreads()
@show BLAS.get_num_threads()

m = 2_000_000
n = 400
A = rand(m, n)
B = deepcopy(A)
A .= B
computeQ!(A)
@show norm(A'*A - LinearAlgebra.I)
A .= B
@time computeQ!(A)

```

gives

```julia
Threads.nthreads() = 4
BLAS.get_num_threads() = 4
norm(A' * A - LinearAlgebra.I) = 4.035802930011282e-14
110.681526 seconds (5 allocations: 203.500 KiB)

```

This is on my slower older desktop compared to the faster 6 core machine on which I ran the blocked MGS-like algorithm yesterday. But still, that’s a little disappointing. I separated them and the time is about evenly split between `geqrf!` and `orgqr!`, which is not surprising; `orgqr!` applys the same reflectors using the same routines. The standard Julia `qr!` which calls `geqrt!` runs in about 22 seconds on this problem on my system, so it’s about twice as fast as `geqrf!`.

The main difference is that `geqrt` is recursive and it stores the matrices T used to represent blocks of reflectors as I - V T V^T. `geqrf` generates the T on the fly from the individual reflectors. I think `geqrt` is considered the more state-of-the-art algorithm. But it doesn’t seem to have an equivalent to `orgqr!`, or at least I didn’t find it poking around LAPACK. There is a routine `gemqrt` for multiplication that is used by `lmul!`. I think the vector `tau` needed by `orgqr!` should be stored on the diagonals of the matrices T stored in the struct returned by `qr!`. You could perhaps pull those out and combine `qr!` with `orgqr!`. But constructing Q would definitely be the slower part of that computation.

I really am surprised there isn’t something analogous to `orgqr` made to work with the output of `geqrt`. If it exists, it seems like it should be named `orgqrt`, but I don’t see that anywhere.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [November 29, 2022, 3:29pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/31 "2022-11-29T15:29:50Z")

</div>

Could you try it with `MKL.jl`?  
Assuming you use the default `OpenBLAS`, it is not known for optimized LAPACK routines.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 29, 2022, 4:57pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/32 "2022-11-29T16:57:27Z")

</div>

To provide a bit of context: the package [SubSIt.jl](https://github.com/PetrKryslUCSD/SubSIt.jl) implements the subspace iteration algorithm for the solution of the generalized eigenvalue problem of free vibration (positive semi-definite pencil of sparse symmetric matrices, smallest-magnitude eigenvalues, size of matrices many times larger than the number of eigenvalues, but number of eigenvalues can go into thousands). The original algorithm has been tweaked in a couple of ways, one of which is to orthonormalize the current guess of the subspace (it appears to is significantly improve convergence). I also have a suspicion (no theory, as yet) that the subspace only needs to be close to orthonormal, and does not need to be perfectly orthonormal.

It is really necessary to materialize the matrix of the orthonormal basis, hence my struggle with `qr!`: it needs to be fast, and it needs to avoid allocations (the matrix of the basis can be tremendously large).

At this point I have implemented the very neat algorithm of @mstewart (many thanks!), with minor improvements, and SubSIt can now regularly beat Arpack.

---

<div class="post-metadata">

**Author:** ![mstewart](https://avatars.discourse-cdn.com/v4/letter/m/b5a626/32.png) [@mstewart](https://discourse.julialang.org/u/mstewart)\
**Post date:** [November 29, 2022, 6:02pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/33 "2022-11-29T18:02:18Z")

</div>

Yeah. I was just going with OpenBLAS. I split up some of the timings and the code looks like:

```julia
using LinearAlgebra
using MKL

@show Threads.nthreads()
@show BLAS.get_num_threads()
@show BLAS.get_config()

m = 2_000_000
n = 400
A = rand(m, n)
tau = zeros(Float64, n)
B = deepcopy(A)

A .= B
@time LAPACK.geqrf!(A, tau)
@time LAPACK.orgqr!(A, tau, n)

A .= B
@time qr!(A)

```

For OpenBLAS, commenting out the `using MKL`, I get:

```julia
Threads.nthreads() = 4
BLAS.get_num_threads() = 4
BLAS.get_config() = LBTConfig([ILP64] libopenblas64_.so)
 55.597908 seconds (58.73 k allocations: 3.234 MiB, 0.06% compilation time)
 55.310785 seconds (96.04 k allocations: 4.970 MiB, 0.11% compilation time)
 22.972657 seconds (75.61 k allocations: 4.162 MiB, 0.12% compilation time)

```

That was about what I was seeing before. With MKL it is:

```julia
Threads.nthreads() = 4
BLAS.get_num_threads() = 4
BLAS.get_config() = LBTConfig([ILP64] libmkl_rt.so, [LP64] libmkl_rt.so)
 36.772481 seconds (58.73 k allocations: 4.383 MiB, 0.09% compilation time)
 20.155890 seconds (96.04 k allocations: 737.587 MiB, 0.30% compilation time)
 24.449802 seconds (75.61 k allocations: 4.162 MiB, 0.55% compilation time)

```

So it’s a decent gain for `geqrf!`, a huge win for building `Q` using `orgqr!`, and essentially a tie for `qr!`.

---

<div class="post-metadata">

**Author:** ![mstewart](https://avatars.discourse-cdn.com/v4/letter/m/b5a626/32.png) [@mstewart](https://discourse.julialang.org/u/mstewart)\
**Post date:** [November 29, 2022, 6:10pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/34 "2022-11-29T18:10:03Z")

</div>

Cool! I’m glad it was useful. I hope the level of orthogonality continues to be adequate. From your matrix dimensions I had guessed there was probably a large sparse eigenvalue problem behind it all. That 2,000,000\times 400 test was really tough on the 16GB machines I was trying it out on. I felt the pain of unnecessary allocations.

---

<div class="post-metadata">

**Author:** ![mstewart](https://avatars.discourse-cdn.com/v4/letter/m/b5a626/32.png) [@mstewart](https://discourse.julialang.org/u/mstewart)\
**Post date:** [November 29, 2022, 8:53pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/35 "2022-11-29T20:53:38Z")

</div>

If you do run into numerical trouble, there is this work on [block MGS algorithms](https://epubs.siam.org/doi/abs/10.1137/18M1197400?journalCode=sjmael) that seem to have numerical properties similar to MGS. They look a bit more involved than my suggestion.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [November 30, 2022, 12:13am UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/36 "2022-11-30T00:13:51Z")

</div>

> [@mstewart](#):
>
> ```julia
> function computeQ!(A)
> m, n = size(A)
> k = min(m, n)
> tau = zeros(eltype(A), k)
> LAPACK.geqrf!(A, tau)
> LAPACK.orgqr!(A, tau, k)
> return A
> end
> 
> ```

Splendid! This is the solution. Many thanks!

---

<div class="post-metadata">

**Author:** ![mstewart](https://avatars.discourse-cdn.com/v4/letter/m/b5a626/32.png) [@mstewart](https://discourse.julialang.org/u/mstewart)\
**Post date:** [November 30, 2022, 12:58pm UTC](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881/37 "2022-11-30T12:58:11Z")

</div>

If you want to go in the direction of using LAPACK semi-directly then you can try:

```julia
function computeQT!(A; nb = 32)
  m, n = size(A)
  k = min(m, n)
  T = zeros(eltype(A), nb, k)
  tau = zeros(eltype(A), k)
  LAPACK.geqrt!(A, T)
  b = Int(ceil(k / nb))
  ib = k - (b - 1) * nb
  for l = 1:(b - 1)
    for j = 1:nb
      tau[(l - 1) * nb + j] = T[j, (l - 1) * nb + j]
    end
  end
  for j = 1:ib
    tau[(b - 1) * nb + j] = T[j, (b - 1) * nb + j]
  end
  LAPACK.orgqr!(A, tau, k)
  return A
end

```

Benchmarking three versions with MKL:

```julia
@show Threads.nthreads()
@show BLAS.get_num_threads()
@show BLAS.get_config()
m = 2_000_000
n = 400
A = rand(m, n)
B = deepcopy(A)
A .= B
@time computeQT!(A)
@show norm(A'*A - LinearAlgebra.I)
A .= B
@time computeQ!(A)
@show norm(A'*A - LinearAlgebra.I)
A .= B
@time mgsortho3!(A)
@show norm(A'*A - LinearAlgebra.I)

```

gave

```julia
Threads.nthreads() = 6
BLAS.get_num_threads() = 6
BLAS.get_config() = LBTConfig([ILP64] libmkl_rt.so, [LP64] libmkl_rt.so)
 19.251219 seconds (204.59 k allocations: 743.491 MiB, 0.38% compilation time)
norm(A' * A - LinearAlgebra.I) = 4.9510605234084604e-14
 28.385975 seconds (33.59 k allocations: 734.794 MiB, 0.06% compilation time)
norm(A' * A - LinearAlgebra.I) = 5.3692519363244134e-14
 20.521297 seconds (7.44 M allocations: 324.980 MiB, 0.40% gc time, 5.91% compilation time)
norm(A' * A - LinearAlgebra.I) = 4.348223673677305e-13
4.348223673677305e-13

```

It also seems like I’m seeing perhaps a little better orthogonality for Housholder approaches. After looking at what’s out there for blocked Gram-Schmidt, I think `mgsortho3!` is probably a little too naive and lacking in theory to really trust. For `computeQT!` it may look like I’m depending on weird LAPACK internals, but the algorithm and storage format that guarantees that the elements of `tau` are where I pulled them out of `T` are part of the documentation of LAPACK `(d|z|s|c)geqrt` that is called by `geqrt!`. So it shouldn’t be something that changes on you.

[Previous page](https://discourse.julialang.org/t/in-place-computation-of-q-from-qr-decomposition/90881.md?page=1)
