JuliaLang / julia / #37752

87%

Build Type

push

local

Committed by web-flow

Commit Message

stdlib: faster kronecker product between hermitian and symmetric matrices (#53186)

The kronecker product between complex hermitian matrices is again
hermitian, so it can be computed much faster by only doing the upper (or
lower) triangular. As @andreasnoack will surely notice, this only true
for types where `conj(a*b) == conj(a)*conj(b)`, so I'm restricting the
function to act only on real and complex numbers. In the symmetric case,
however, no additional assumption is needed, so I'm letting it act on
anything.

Benchmarking showed that the code is roughly 2 times as fast as the
vanilla kronecker product, as expected. The fastest case was always the
UU case, and the slowest the LU case. The code I used is below
```julia
using LinearAlgebra
using BenchmarkTools
using Quaternions

randrmatrix(d, uplo = :U) = Hermitian(randn(Float64, d, d), uplo)
randcmatrix(d, uplo = :U) = Hermitian(randn(ComplexF64, d, d), uplo)
randsmatrix(d, uplo = :U) = Symmetric(randn(ComplexF64, d, d), uplo)
randqmatrix(d, uplo = :U) = Symmetric(randn(QuaternionF64, d, d), uplo)

dima = 69
dimb = 71
for randmatrix in [randrmatrix, randcmatrix, randsmatrix, randqmatrix]
    for auplo in [:U, :L]
        for buplo in [:U, :L]
            a = randmatrix(dima, auplo)
            b = randmatrix(dimb, buplo)
            c = kron(a,b)
            therm = @belapsed kron!($c, $a, $b)
            C = Matrix(c)
            A = Matrix(a)
            B = Matrix(b)
            told = @belapsed kron!($C, $A, $B)
            @show told/therm
        end
    end
end
```
Weirdly enough, I got this expected speedup in one of my machines, but
when running the benchmark in another I got roughly the same time. I
guess that's a bug with `BechmarkTools`, because that's not consistent
with the times I get running the functions individually, out of the
loop.

Another issue is that although I added a couple of tests, I couldn't get
them to run. Perhaps someone here can tell me what's going on? I could
run ... (continued)

Run Details

170 of 172 new or added lines in 3 files covered. (98.84%)

72 existing lines in 8 files now uncovered.

76197 of 87170 relevant lines covered (87.41%)

15863283.27 hits per line