To be able to edit code and run cells, you need to run the notebook yourself. Where would you like to run the notebook?

In the cloud (experimental)

Binder is a free, open source service that runs scientific notebooks in the cloud! It will take a while, usually 2-7 minutes to get a session.

On your computer

(Recommended if you want to store your changes.)

  1. Copy the notebook URL:
  2. Run Pluto

    (Also see: How to install Julia and Pluto)

  3. Paste URL in the Open box

Frontmatter

If you are publishing this notebook on the web, you can set the parameters below to provide HTML metadata. This is useful for search engines and social media.

Author 1

Matrix coloring comparison

11.4 ms

A comparison between matrix coloring packages in Julia.

At the moment we include:

11.8 ms
begin
using Pkg
Pkg.activate(mktempdir())
Pkg.add([
Pkg.PackageSpec("CairoMakie"),
Pkg.PackageSpec("Chairmarks"),
Pkg.PackageSpec(url="https://github.com/exanauts/ColPack.jl", rev="gd/super_upgrade_colpack"),
Pkg.PackageSpec("DataFrames"),
Pkg.PackageSpec("DataFramesMeta"),
Pkg.PackageSpec("LinearAlgebra"),
Pkg.PackageSpec("PlutoUI"),
Pkg.PackageSpec("ProgressLogging"),
Pkg.PackageSpec("SparseMatrixColorings"),
Pkg.PackageSpec("SparseArrays"),
Pkg.PackageSpec("StableRNGs"),
Pkg.PackageSpec("Statistics"),
Pkg.PackageSpec("Test"),
])
using CairoMakie
using Chairmarks
using ColPack
using DataFrames
using DataFramesMeta
using LinearAlgebra
using PlutoUI
using ProgressLogging
using SparseMatrixColorings
using SparseMatrixColorings: NaturalOrder
using SparseArrays
using StableRNGs
using Statistics
using Test
end
❔
269 s
TableOfContents()
16.1 μs

Setup

7.4 ms

SparseMatrixColorings

7.1 ms
smc_column_coloring (generic function with 1 method)
function smc_column_coloring(J)
return column_coloring(J, GreedyColoringAlgorithm(NaturalOrder()))
end
435 μs
smc_row_coloring (generic function with 1 method)
function smc_row_coloring(J)
return row_coloring(J, GreedyColoringAlgorithm(NaturalOrder()))
end
444 μs
smc_symmetric_coloring (generic function with 1 method)
function smc_symmetric_coloring(H)
return symmetric_coloring(H, GreedyColoringAlgorithm(NaturalOrder()))
end
432 μs
---
colpack_column_coloring (generic function with 1 method)
function colpack_column_coloring(J)
method = "COLUMN_PARTIAL_DISTANCE_TWO"
order = "NATURAL"
coloring = ColPackPartialColoring(J, method, order)
return get_colors(coloring)
end
527 μs
colpack_row_coloring (generic function with 1 method)
function colpack_row_coloring(J)
method = "ROW_PARTIAL_DISTANCE_TWO"
order = "NATURAL"
coloring = ColPackPartialColoring(J, method, order)
return get_colors(coloring)
end
541 μs
colpack_symmetric_coloring (generic function with 1 method)
function colpack_symmetric_coloring(H)
method = "STAR"
order = "NATURAL"
coloring = ColPackColoring(H, method, order)
return get_colors(coloring)
end
525 μs

Misc

221 μs
d_values_small (generic function with 1 method)
d_values_small(n) = filter(<=(n), [5,10,20])
424 μs
d_values (generic function with 1 method)
d_values(n) = filter(<=(n), [5,10,20,50,100])
437 μs
linestyles = [:solid, :dash, :dashdot, :dashdotdot, :dot]
26.0 μs
markers = [:circle, :star5, :rect, :utriangle, :cross]
34.9 μs

Correctness

219 μs

Jacobian

202 μs

Some tests did not pass: 0 passed, 0 failed, 2 errored, 6 broken.

Stack trace

Here is what happened, the most recent locations are first:

  1. finish(ts::Test.DefaultTestSet; print_results::Bool)Test.jl:1195
  2. finishTest.jl:1170
  3. macro expansionThis cell: line 1593
  4. Show more...
@testset "Column coloring" begin
@testset "n=$n - d=$d" for n in 10 .^ (1:3), d in d_values_small(n)
J = sprand(n, n + 1, d/n)
color1 = smc_column_coloring(J)
color2 = colpack_column_coloring(J)
@test_broken color1 == color2
end
end
❔
---
Loading more cells...