Products of sparse by dense matrices dont revert to specialized methods

using LinearAlgebra

function multiply_sparse_dense(A::SparseMatrixCSC{T}, B::AbstractMatrix{T}) where T
    m, n = size(A)
    C = zeros(T, m, size(B, 2))
    
    for j = 1:size(B, 2)
        for i = 1:n
            for k = A.colptr[i]:(A.colptr[i+1]-1)
                C[A.rowval[k], j] += A.nzval[k] * B[i, j]
            end
        end
    end
    
    return C
end

A = sparse([1 0 0; 0 2 0; 0 0 3])
B = [1 2; 3 4; 5 6]

C = multiply_sparse_dense(A, B)
println(C)

Solution 1: Using a nested loop

In this solution, we use a nested loop to iterate over the columns of the dense matrix and the non-zero elements of the sparse matrix. For each non-zero element, we update the corresponding element in the result matrix by multiplying it with the corresponding element in the dense matrix.

The time complexity of this solution is O(nnz(A) * n * m), where nnz(A) is the number of non-zero elements in the sparse matrix, n is the number of columns in the dense matrix, and m is the number of rows in the dense matrix.

using LinearAlgebra

function multiply_sparse_dense(A::SparseMatrixCSC{T}, B::AbstractMatrix{T}) where T
    m, n = size(A)
    C = zeros(T, m, size(B, 2))
    
    for j = 1:size(B, 2)
        for i = 1:n
            for k = A.colptr[i]:(A.colptr[i+1]-1)
                C[A.rowval[k], j] += A.nzval[k] * B[i, j]
            end
        end
    end
    
    return C
end

A = sparse([1 0 0; 0 2 0; 0 0 3])
B = [1 2; 3 4; 5 6]

C = multiply_sparse_dense(A, B)
println(C)

Solution 2: Using matrix multiplication

In this solution, we convert the sparse matrix to a dense matrix and then perform matrix multiplication using the dot product of rows and columns. This approach leverages the optimized matrix multiplication algorithms available in Julia.

The time complexity of this solution is O(m * n * p), where m is the number of rows in the sparse matrix, n is the number of columns in the sparse matrix, and p is the number of columns in the dense matrix.

using LinearAlgebra

function multiply_sparse_dense(A::SparseMatrixCSC{T}, B::AbstractMatrix{T}) where T
    C = convert(Matrix{T}, A) * B
    return C
end

A = sparse([1 0 0; 0 2 0; 0 0 3])
B = [1 2; 3 4; 5 6]

C = multiply_sparse_dense(A, B)
println(C)

Solution 3: Using the `mul!` function

In this solution, we use the `mul!` function from the `LinearAlgebra` module to perform the matrix multiplication in-place. This avoids the need to allocate memory for the result matrix, resulting in improved performance and reduced memory usage.

The time complexity of this solution is O(nnz(A) * n * m), where nnz(A) is the number of non-zero elements in the sparse matrix, n is the number of columns in the dense matrix, and m is the number of rows in the dense matrix.

using LinearAlgebra

function multiply_sparse_dense(A::SparseMatrixCSC{T}, B::AbstractMatrix{T}) where T
    m, n = size(A)
    C = zeros(T, m, size(B, 2))
    
    mul!(C, A, B)
    
    return C
end

A = sparse([1 0 0; 0 2 0; 0 0 3])
B = [1 2; 3 4; 5 6]

C = multiply_sparse_dense(A, B)
println(C)

Among the three options, Solution 3 using the `mul!` function is the best choice. It provides the best performance and memory efficiency by avoiding unnecessary memory allocations. Additionally, it leverages the optimized matrix multiplication algorithms available in Julia.