Julia 中的布尔矩阵乘法

Question

我需要在 Julia 中将两个布尔矩阵相乘。

只做 A*A 或 A^2 returns Int64 矩阵。

有没有办法有效地乘以布尔矩阵？

Answer 1

一个非常简单的解决方案是

function bool_mul(A,B)
    return A*B .!= 0
end

这不是最有效的，因为它将为 A*B 分配一个矩阵，但最终可能成为可用的最快解决方案之一。

Answer 2

根据 Oscar 关于在代码周围添加两个 for 循环的评论，但没有 LoopVectorization 改进，尽管没有在 any 调用中分配完整数组（因此 any 在第一次出现时停止），这相当快（编辑：将标准 AND & 替换为短路 &&）：

function bool_mul2(A, B)
    mA, nA = size(A)
    mB, nB = size(B)
    nA ≠ mB && error()
    AB = BitArray(undef, mA, nB)
    for i in 1:mA, j in 1:nB
        AB[i,j] = any(A[i,k] && B[k,j] for k in 1:nA)
    end
    AB
end

（请注意，我删除了 any 中的 [ 和 ] 以不在那里分配。

例如，对于大小为 1000×1000 的 A 和 B，我得到

julia> @btime bool_mul2($A, $B) ;
  16.128 ms (3 allocations: 122.25 KiB)

与

相比

julia> @btime bool_mul($A, $B) ;
  346.374 ms (12 allocations: 7.75 MiB)

编辑：为了对矩阵进行平方，也许可以尝试

function bool_square(A)
    m, n = size(A)
    m ≠ n && error()
    A² = BitArray(undef, n, n)
    for i in 1:n, j in 1:n
        A²[i,j] = any(A[i,k] && A[k,j] for k in 1:n)
    end
    A²
end

我得到

julia> A = rand(Bool, 500, 500) ;

julia> @btime $A * $A .!= 0 ;
  42.483 ms (12 allocations: 1.94 MiB)

julia> @btime bool_square($A) ;
  4.653 ms (3 allocations: 30.69 KiB)

Julia 中的布尔矩阵乘法

Boolean matrix multiplication in Julia

boolean

matrix-multiplication

julia