TropicalGEMM

The fastest Tropical matrix multiplication in the world! Supported matrix element types include

• max-plus algebra: Tropical{BlasType}
• min-plus algebra numbers: TropicalMinPlus{BlasType}
• max-times algebra numbers: TropicalMaxMul{BlasType}

Please check TropicalNumbers.jl for the definitions of these types. The BlasType is the storage type, which could be one of Bool, Float16, Float32, Float64, Int16, Int32, Int64, Int8, UInt16, UInt32, UInt64, UInt8, SIMDTypes.Bit.

Get started

Open a Julia REPL and type ] to enter the pkg> mode, and then install related packages with

pkg> add TropicalGEMM, BenchmarkTools, TropicalNumbers

Loading TropicalGEMM module into the workspace affects the * on Tropical matrices immediately. The following is a minimum working example

julia> using TropicalNumbers, BenchmarkTools

julia> a = Tropical.(randn(1000, 1000));

julia> @btime $a * $a;
  2.588 s (6 allocations: 7.66 MiB)

julia> using TropicalGEMM

julia> @btime $a * $a;
  66.916 ms (2 allocations: 7.63 MiB)

Use transpose(a) for tropical matrices, rather than the conjugating adjoint a'. Conjugation is not defined for these semirings. The in-place Octavian entry points matmul! and matmul_serial! reject adjoint inputs and outputs before entering their pointer kernels, including adjoints wrapped in views.

Benchmarks

Matrix size n x n, CPU Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz. The benchmark and plotting scripts could be found in the benchmarks folder.

References

1. This package originates from the following issue: JuliaSIMD/LoopVectorization.jl#201
2. For applications, please check the papers listed in the CITATION.bib.