# Which algorithm does Julia use for matrix QR decomposition?
**URL:** https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566
**Category:** New to Julia
**Tags:** factorization, matrix
**Created:** [December 13, 2023, 12:19pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566 "2023-12-13T12:19:19Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@boywithacoin](https://discourse.julialang.org/u/boywithacoin)
#### Post date: [December 13, 2023, 12:19pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566/1 "2023-12-13T12:19:19Z")
Which algorithm does Julia uses for QR decomposition?
Additionally, parallelizing decomposition methods is non-trivial. Does it use a specialized implementation on the GPU?
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [December 13, 2023, 2:30pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566/2 "2023-12-13T14:30:12Z")
> [@boywithacoin](#):
>
> Which algorithm does Julia uses for QR decomposition?
Julia uses multiple dispatch, so `qr(A)` depends on the type of `A`. For generic dense matrices, it uses Householder QR (via LAPACK’s `*geqrf`), and there is a [`pivot` argument](https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#LinearAlgebra.qr) to use a column-pivoted variant (via LAPACK’s `*geqp3`).
> [@boywithacoin](#):
>
> Does it use a specialized implementation on the GPU?
The standard library can use CPU threads, but does nothing with the GPU — you use a GPU with GPUArrays.jl or similar. You can also use distributed memory with Elemental.jl, and so on. I don’t know offhand if those packages include parallel QR functions.
---
### Author:  [@boywithacoin](https://discourse.julialang.org/u/boywithacoin)
#### Post date: [December 13, 2023, 6:47pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566/3 "2023-12-13T18:47:54Z")
> Julia uses multiple dispatch, so `qr(A)` depends on the type of `A`
Could you point me to the source code where it solves for specific cases? Also, does above cover all cases, you think?
1. Square matrix
2. Non-square matrix
a. Overdetermined
b. Underdetermined
> [@stevengj](#):
>
> For generic dense matrices, it uses Householder QR (via LAPACK’s `*geqrf`)
on macOS, is it using Apple’s provided LAPACK or does it ship its own? The apple owned LAPACK is accessed via Accelerate framework I believe. Located at: `/Accelerate.framework/Frameworks/vecLib.framework/Headers/lapack.h`
---
### Author:  [@RomeoV](https://discourse.julialang.org/u/RomeoV)
#### Post date: [December 13, 2023, 6:57pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566/4 "2023-12-13T18:57:23Z")
You can find the source by running
```julia
@edit qr(rand(100, 100))
```
In this particular case, you’ll see that it’s actually calling `qr!` (the in-place version), but it’s in the same file.
If the call stack becomes more complicated, you can pretty easily “descend” down the dispatch stack using Cthulhu.jl:
```julia
using Cthulhu, LinearAlgebra
@descend qr(rand(100, 100))
```
---
### Author:  [@RomeoV](https://discourse.julialang.org/u/RomeoV)
#### Post date: [December 13, 2023, 7:10pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566/5 "2023-12-13T19:10:16Z")
When doing the same for a CUDA array, `@descend` will eventually take you to a cuSOLVER call (i.e. Nvidia’s cuBLAS). You can find what algorithm they use [here](https://docs.nvidia.com/cuda/cusolver/index.html).
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [December 13, 2023, 8:04pm UTC](https://discourse.julialang.org/t/which-algorithm-does-julia-use-for-matrix-qr-decomposition/107566/6 "2023-12-13T20:04:01Z")
> [@boywithacoin](#):
>
> on macOS, is it using Apple’s provided LAPACK or does it ship its own?
It defaults to using the LAPACK from [OpenBLAS](https://www.openblas.net/), which is bundled with Julia. It can optionally use Apple Accelerate via the [Accelerate.jl](https://github.com/JuliaLinearAlgebra/AppleAccelerate.jl) package (or Intel MKL via the [MKL.jl](https://github.com/JuliaLinearAlgebra/MKL.jl) package) — you just type `using Accelerate` and the same calls like `qr(...)` will be internally redirected transparently to Accelerate’s implementation (if it exists), thanks to a magical bit of infrastructure called [libblastrampoline](https://github.com/JuliaLinearAlgebra/libblastrampoline).
> [@boywithacoin](#):
>
> Also, does above cover all cases, you think?
>
> 1. Square matrix
> 2. Non-square matrix
> a. Overdetermined
> b. Underdetermined
Yes. (There is also the LQ factorization.) For a matrix that might be rank deficient, using the [pivoted variant](https://www.netlib.org/lapack/lug/node42.html) `qr(A, ColumnNorm())` is usually a good idea.