Added in-place functions 'qraddcol!' and 'qrdelcol!'

[nabw]

Thanks for the disposition!

The idea here is that the A and R matrices are allocated from the beginning, so only the temporary vectors in the qraddcol operations are used. I tried to minimize allocation in general to obtain a performant implementation. Because of this, when you add a new column, you must tell the function how full your R matrix is.

So here are the modifications:

• I added a 'qrdelcol!' function that deletes columns from both A and R. This is mostly untouched from the existing implementation.
• I added a 'qraddcol!' function that appends a column to A and R. It needs to know how many diagonal elements R currently has.
• Within the column addition routing, one needs to solve triangular systems. I have also added two auxiliary functions 'solveR!' and 'solveRT! that do forward/backward substitution to solve the associated systems with a non-full R. These are tested as well.

I tried the following code:

using QRupdate
using LinearAlgebra
using TimerOutputs

m, n = 10000, 100
A = randn(m, 0)
R = Array{Float64, 2}(undef, 0, 0)
Rin = zeros(m,m)
Ain = zeros(m, m)
for i in 1:n
    println("======", i)
    a = randn(m)
    @timeit "dynamic" global R = qraddcol(A, R, a)
    @timeit "dynamic" global A = [A a]
    @timeit "in-place" qraddcol!(Ain, Rin, a, i-1)
end
print_timer()

and got the following output:

───────────────────────────
Time Allocations
─────────────────────── ────
Tot / % measured: 8.11s / 60.9% 2.04GiB / 25.3%

Section ncalls time %tot avg alloc %tot avg
────────────────────────────────────
dynamic 200 3.71s 75.1% 18.6ms 512MiB 96.9% 2.56MiB
in-place 100 1.23s 24.9% 12.3ms 16.3MiB 3.1% 167KiB
────────────────────────────────────

So, roughly a 60% time reduction and considerable savings in terms of memory allocations.

[mpf]

Thank you @nabw! The improvement is significant! 🎉