Is there a way to speed up this matrix (with only 1 & 0) multiplication & power operation?

General Usage Performance
,
3

Using @mcabbott 's hint and Russian Peasant exponentiation

using LinearAlgebra, BenchmarkTools

function init(size)
    cost_mat=zeros(Float64, size,size);
    for j in 1:size
        for i in j:size
            cost_mat[i,j] = rand()< 0.7 ? 1 : 0;
            cost_mat[j,i] = cost_mat[i,j];
        end
    end
    cost_mat += LinearAlgebra.I;
end

function compute1(cost_mat)
    N=48
    step=24
    c = copy(cost_mat);
    for i in 1:N
        # println(i,"/",N," multiplication done ")
        #After doing each power operation,I convert the values  to 1 or 0
        c = map(cij -> cij != 0.0 ? 1.0 : 0.0, c*(cost_mat^(step)));
    end
    c
end

function compute2(cost_mat)
    N=48*24
    c = copy(cost_mat);
    while N > 0
        if N % 2 == 0
            c *= c
            N ÷= 2
        else
            c *= cost_mat
            N -= 1
        end
        c = map(cij -> cij != 0.0 ? 1.0 : 0.0, c);
    end
    c
end

const cost_mat = init(553)
println("cost matrix calculated")

c1 = compute1(cost_mat)

c2 = compute2(cost_mat)
@assert c2 ≈ c1

@btime compute1(cost_mat)
@btime compute2(cost_mat)

I see

 762.914 ms (674 allocations: 786.30 MiB)
  36.623 ms (50 allocations: 58.33 MiB)
2 Likes