Cannot solve Ax = B for sparse matrices A, B

[lzxnl]

A\B works if A is a sparse matrix and B is a sparse vector. A\B does not work if B is a sparse matrix.

Example:

using SparseArrays, LinearAlgebra
A = sparse(I,100,100)
B = sparse(I,100,100)
C = sprandn(100,0.5)
A\B # will fail 
A\C # will work. 

Sometimes I can get around this by dividing column by column, but it's nevertheless still a strange bug to have.

[andreasnoack]

See also JuliaLang/LinearAlgebra.jl#381

[dkarrasch]

For this very specific case, I think we could provide the missing

ldiv!(::Diagonal{Bool,Array{Bool,1}}, ::SparseMatrixCSC{Float64,Int64})

easily. For the more general case, would it make sense to have the column-by-colum solver the default? Extracting columns from SparseMatrixCSC should be cheap.

[dkarrasch]

Hm, actually why not something like

function mydiv!(C::AbstractMatrix, A::SparseMatrixCSC, B::SparseMatrixCSC)
    F = factorize(A)
    return mydiv!(C, F, B)
end

function mydiv!(C::AbstractMatrix, F::Factorization, B::SparseMatrixCSC)
    @views for (c, b) in zip(eachcol(C), eachcol(B))
        ldiv!(c, F, b)
    end
    return C
end

I couldn't find how eachcol is defined on sparse matrices, but doing all the rowvals-nzrange-sparsevec-thing manually was worse than that.

[lzxnl]

The issue is, column-wise division doesn't seem to work either in general. I have not yet determined when you can divide by a sparse column.
A = sprand(100,100,0.5)
B = sprand(100,0.5)
A\B will not work

[dkarrasch]

You said in the OP it does work, and I tested my code snippet.

[lzxnl]

That's what confuses me. It sometimes works for some matrices and sometimes doesn't. It works if you're dividing a sparse identity matrix by a sparse column vector but not always. Sorry, I should have made that clearer. I'll amend my original post soon. ?? Outlook for Android<https://aka.ms/ghei36>

…

________________________________ From: Daniel Karrasch <[email protected]> Sent: Thursday, December 12, 2019 12:49:35 PM To: JuliaLang/julia <[email protected]> Cc: lzxnl <[email protected]>; Author <[email protected]> Subject: Re: [JuliaLang/julia] Cannot solve Ax = B for sparse matrices A, B (#34052) You said in the OP it does work, and I tested my code snippet. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub<https://github.com/JuliaLang/julia/issues/34052?email_source=notifications&email_token=ANNNDYZ5MPU7WOHS7MR6FR3QYJ2S7A5CNFSM4JYDAK42YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEGXPBZQ#issuecomment-565113062>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/ANNNDY4AVWCML3OYYU5EHVDQYJ2S7ANCNFSM4JYDAK4Q>.

[dkarrasch]

Maybe the failure you're seeing with sparse vectors has nothing to do with the sparse vectors, but simply with the fact that the sparse matrix is singular? If it works sometimes, i.e., you don't get a MethodError: no method matching ..., it means there are methods that handle that case, and failure depends on the numerical values.

Sorry, I should have made that clearer. I'll amend my original post soon.

Yes, providing the error message should help to clarify what exactly doesn't work.

[lzxnl]

A = sprand(100,100,0.5)
B = sparse(I,100,100)
C = sprand(100,0.5)
A\C

MethodError: no method matching ldiv!(::SuiteSparse.UMFPACK.UmfpackLU{Float64,Int64}, ::SparseVector{Float64,Int64})
Closest candidates are:
ldiv!(!Matched::IterativeSolvers.Identity, ::Any) at C:\Users\nicho.julia\packages\IterativeSolvers\QuajJ\src\common.jl:31
ldiv!(!Matched::Number, ::AbstractArray) at C:\cygwin\home\Administrator\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.2\LinearAlgebra\src\generic.jl:152
ldiv!(!Matched::Transpose{#s617,#s616} where #s616<:(LowerTriangular{#s615,#s614} where #s614<:(Union{DenseArray{T,2}, Base.ReinterpretArray{T,2,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, Base.ReshapedArray{T,2,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{Base.ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, SubArray{T,2,A,I,L} where L where I<:Tuple{Vararg{Union{Int64, AbstractRange{Int64}, Base.AbstractCartesianIndex},N} where N} where A<:Union{Base.ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, Base.ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{Base.ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, DenseArray}} where T) where #s615) where #s617, ::SparseVector) at C:\cygwin\home\Administrator\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.2\SparseArrays\src\sparsevector.jl:1798

However, B\C goes through.

[lzxnl]

It looks like there's a routine there specifically for the identity.

[dkarrasch]

No, the special method is for Diagonals, because factorize checks for "triangularity/diagonality", and then wraps the matrix into the corresponding type. I'm a bit confused as to why my code snippet worked, perhaps because it's a view (SubArray) and not a SparseVector.

[ViralBShah]

This works now.