Pivoting in sparse QR

General Usage
,
1

I have a skinny sparse matrix that I have taken care to order its rows and columns in such a way as to ensure that the sparse QR factorization should be fast [O(n) space and time]. However when I call qr in Julia 1.7.2 it runs very slowly [O(n^3) by my tests]. Using the help function I see that qr has a keyword argument called ordering, but the only option that the documentation offers is ORDERING_DEFAULT, and using that results in an UndefVarError. Does anyone know how to turn off the reordering completely? Thanks in advance.
–shiv–
PS: Or a hint as how to find the corresponding source code for sparse qr would also probably suffice.

2

In reply to my own post I think I found the correct source in https://github.com/JuliaSparse/SuiteSparse.jl/blob/master/src/spqr.jl

Now I just need to figure out how to access ORDERING_FIXED. It would be nice if this was exported either from LinearAlgebra or SparseArrays which is where we are accessing qr from I think.

3

Actually the docs seem to be incorrect as “ordering” is not accepted as a keyword argument. I get the following error:

ERROR: MethodError: no method matching qr(::SparseMatrixCSC{Float32, Int64}; ordering=0) Closest candidates are: qr(::SparseMatrixCSC{<:Union{Float16, Float32}}; tol) at c:\users\00shi\appdata\local\programs\julia-1.7.2\share\julia\stdlib\v1.7\SuiteSparse\src\spqr.jl:213 got unsupported keyword argument “ordering” qr(::Union{SparseMatrixCSC{Complex{T}}, SparseMatrixCSC{T}}; tol) where T<:AbstractFloat at c:\users\00shi\appdata\local\programs\julia-1.7.2\share\julia\stdlib\v1.7\SuiteSparse\src\spqr.jl:218 got unsupported keyword argument “ordering”

Looking at the corresponding source file the keyword “ordering” is masked off! Does anyone have an easy workaround to reach deeper in spqr.jl and call the function qr that does allow the keyword?

Thanks.
–shiv–

4

Just from a glance at the source files, this code seems to run just fine:

using SparseArrays, SuiteSparse
sample_sparse = sprandn(100,50,0.01)
fixed_ordering_qr = qr(sample_sparse, ordering=SuiteSparse.SPQR.ORDERING_FIXED)

Is this what you’re looking for?

Maybe I’m missing what you mean by “masked off”, but I would guess that when you were reading that source file you just missed that this is all wrapped in the SuiteSparse.SPQR module, and so ORDERING_FIXED wasn’t in the namespace you expected?

1 Like
5

Strange, when I first tried that I got the error that “ordering” was not a keyword. But now everything seems fine!
Thanks.
–shiv–

6

I think that was a premature. Running the code this way shows the re-ordering still happening. I will try other options and see if one of them has a better chance of working.

7

I think I see what is happening. It still re-orders the rows but not the columns. Would be good to have this in the documentation if possible.