JuliaLang / JuliaLang/LinearAlgebra.jl

QR multiplication

Open
#512 1 comment 1 reaction 0 assignees View on GitHub
needs decision
Dominant language
Julia
Stars
77
Forks
65
Avg merge
3d 23h
Merged PRs (30d)
10

Description

This is a followup on https://github.com/JuliaLang/julia/pull/26391. As @KlausC points out, it is currently not possible to multiply `Q*R` for `QRSparseQ` (in the tall case). For the dense QR factorizations, this is possible because the multiplication methods allow that Q can both be interpreted as thin and square. E.g.
```julia
julia> using LinearAlgebra

julia> A = randn(4,2);

julia> F = qrfact(A);

julia> F.Q*Matrix(I, 4, 2)
4×2 Array{Float64,2}:
-0.687523 0.286761
-0.544745 0.0838634
0.0651093 -0.733251
0.475737 0.610801

julia> F.Q*Matrix(I, 2, 2)
4×2 Array{Float64,2}:
-0.687523 0.286761
-0.544745 0.0838634
0.0651093 -0.733251
0.475737 0.610801
```
Multiply Q in Householder form is actually only possible when the right hand side corresponds to a square Q so the special behavior is implemented by zero padding the right hand side.

There are two solutions here. Either we make sparse QR behave like the dense or the opposite. The former is the more complicated solution and I like the simplicity of the latter. People like to reconstruct the input with `Q*R` which wouldn't be possible if go with the latter. However, reconstructing the input is only useful for teaching and in that case, it might be instructive to require `F.Q*Matrix(I, 4, 2)*F.R`. Finally, if we decide to stick with dense behavior then we also need to fix `R'Q'` (as also pointed out by @KlausC).

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reviewing PR 26391 and the dense and sparse QR multiplication behavior described in this issue. Compare Q*R and R'Q' semantics for tall QRSparseQ and dense factorizations, then resolve which behavior should be supported. Done means the chosen behavior is implemented consistently and covered by tests for QR multiplication.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.