Computational Category Theory in Applied Mathematics

Owen Lynch and James Fairbanks

Overview

  1. Why is AlgebraicJulia?
  2. Who is AlgebraicJulia?
  3. What is AlgebraicJulia?
  4. How is AlgebraicJulia?
  5. Why again is AlgebraicJulia?

Part 1: Why is AlgebraicJulia?

Compositional modeling

Halter et al. (2020)

“Informal diagrams that should be String Diagrams”

Figure 1: Informal diagrams in the wild

The high-level picture

Part 2: Who is AlgebraicJulia?

History

  • Evan Patterson started Catlab in 2017 to be a computer algebra system for applied category theory
  • James Fairbanks started SemanticModels.jl in 2018 to achieve this “high-level modeling” dream
  • In 2019, they started collaborating and created the AlgebraicJulia organization to maintain a variety of packages (often prefixed by “Algebraic”) around scientific modeling with applied category theory
  • I joined in 2020 (the inflection point)
  • Companies like Merck now hire based on “experience with AlgebraicJulia”

Collaborators

(made with Semagrams)

Part 3: What is AlgebraicJulia

The landscape of AlgebraicJulia

Package Description
Catlab.jl Data structures, algorithms, visualization, computer algebra
AlgebraicDynamics.jl Open dynamical systems
AlgebraicPetri.jl Petri nets operations, including rate equation simulation
AlgebraicRewriting.jl Rewriting systems for combinatorial data structures
AlgebraicRelations.jl Database integration
CombinatorialSpaces.jl Meshes for PDEs
Decapodes.jl Discrete Exterior Calculus
StockFlow.jl Stockflow diagrams and simulations
Semagrams.jl User interfaces built around graphical syntax (Scala.js+Julia)

Open dynamical systems overview

Libkind, Baas, Patterson, et al. (2022)

A hierarchical model of an ecosystem

Solving the dynamics for that ecosystem

Figure 2: Ecosystem modeling in AlgebraicJulia.

The math of open dynamical systems

(Vagner, Spivak, and Lerman (2015)) An open dynamical system consists of a state manifold \(X\), an input manifold \(X_{in}\), an output manifold \(X_{out}\), a readout function \(X \to X_{out}\) and an evolution function \(X \times X_{in} \to T X\).

Open dynamical systems form an operad algebra of the operad of undirected wiring diagrams.

Multiphysics

Patterson et al. (2022)

Conjugate heat transfer

Heat transfer between a solid and a fluid

Part 4: How is AlgebraicJulia?

What does it mean to “do category theory” on a computer?

The problem: pushouts in FinSet

Figure 3: A pushout in \(\mathsf{FinSet}\)

In the category \(\mathsf{FinSet}\), the pushout of the above diagram is given by:

\[ X \sqcup_Z Y = (X + Y)/\sim \]

where \(\sim\) is the equivalence relation generated by \(f(z) \sim g(z)\) for all \(z \in Z\).

We want to actually compute pushouts!

FinSet in Julia

We first need to represent finite sets on the computer

# The finite set {1,...,n}
struct FinSet
  n::Int
end

# The function i ↦ values[i]
struct FinFunction
  dom::FinSet
  codom::FinSet
  values::Vector{Int}
end


A, B = FinSet(3), FinSet(2)
f = FinFunction(A, B, [1,2,2])

A data structure for partitions

Julia has a data structure for representing a partition of \(\{1,\ldots,n\}\).

using DataStructures

const Partition = IntDisjointSets

# A partition of {1,...,10}
a = Partition(10)
# Mutate a to make 3 and 5 be in the same equivalence class
union!(a, 3, 5)
union!(a, 5, 7)
# Compute representative of equivalence class
find_root!(a, 3) == find_root!(a, 7)
true

Pushouts in Julia

function pushout(X::FinSet, Y::FinSet, Z::FinSet,
                 f::FinFunction, g::FinFunction)
  # Start with the singleton partition of {1,...,|X|+|Y|}
  a = Partition(X.n + Y.n)

  # Construct the partition we want: f(z) ~ g(z) for all z ∈ Z
  for z in 1:Z.n
    union!(a, f.values[z], g.values[z])
  end

  # Return a FinSet of size the number of unique roots
  FinSet(length(unique!([find_root!(i) for i in 1:length(a)])))
end

This runs in time \(\mathcal{O}(m \log m)\), where m = X.n + Y.n.

Exercise: extend this code to also compute the legs of the cocone for pushout!

Part 5: Again, why is AlgebraicJulia?

Technical wins: data structures for free from C-sets

Patterson, Lynch, and Fairbanks (2022)

Figure 4: One data structure implementation, many data structures. Graphs, simplicial sets, petri nets, and undirected wiring diagrams.

Technical wins: algorithms for free from limits/colimits

  • Compute connected components for a graph by coequalizing src and tgt
  • Split up a population in a Petri net by (age group/vaccination status/region/etc.) using limits (Libkind, Baas, Halter, et al. (2022))

Technical wins: algorithms for free from limits/colimits

  • Compose structured cospans (c.f. Baez and Courser (2020)) of Petri nets

  • Compose operations in the operad of (directed/undirected) wiring diagrams

Compositional modeling

Halter et al. (2020)

The Future of AlgebraicJulia

  1. Deliver high-quality results for individual domain-specific grants.
  2. Along the way, carefully develop and refine general-purpose open-source tools for scientists solving the world’s problems.
Domain Funders and Collaborators
Epidemiology ASKEM DARPA Project, University of Saskatchewan, DARPA YFA award (PI: Fairbanks)
Multiphysics ASKEM DARPA Project
Task modeling and planning PTG DARPA Project
Industrial process and data management CMU, NIST, Chevron
Compositional statistical modeling AFOSR YIP award (PI: Patterson)
Education and outreach Mozilla

What can you do…

  • …if you will be on the job market soon:

    Topos Institute and James’s lab at University of Florida are growing and will be looking for researchers over the next couple years. There may not be positions lining up precisely with the timing of when you are looking, but keep in touch with us if this is something you are interested in.

  • …if you want to use AlgebraicJulia?

    Read papers and blog posts on algebraicjulia.org, and then ask us questions in the Julia Zulip: julialang.zulipchat.com.

  • …if you want to make your math be useful for scientists?

    There’s no magic bullet, but the two things that will help are

    1. Keeping the end goal in mind: category theory as UI for high-level formal scientific modeling
    2. Talking to us (the AlgebraicJulia crew) about your research!

References

Baez, John C., and Kenny Courser. 2020. “Structured Cospans.” arXiv. https://doi.org/10.48550/arXiv.1911.04630.
Brown, Kristopher, Tyler Hanks, and James Fairbanks. 2022. “Compositional Exploration of Combinatorial Scientific Models.” arXiv. https://doi.org/10.48550/arXiv.2206.08755.
Halter, Micah, Evan Patterson, Andrew Baas, and James Fairbanks. 2020. “Compositional Scientific Computing with Catlab and SemanticModels.” arXiv. https://doi.org/10.48550/arXiv.2005.04831.
Libkind, Sophie, Andrew Baas, Micah Halter, Evan Patterson, and James Fairbanks. 2022. “An Algebraic Framework for Structured Epidemic Modeling.” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 380 (2233): 20210309. https://doi.org/10.1098/rsta.2021.0309.
Libkind, Sophie, Andrew Baas, Evan Patterson, and James Fairbanks. 2022. “Operadic Modeling of Dynamical Systems: Mathematics and Computation.” Electronic Proceedings in Theoretical Computer Science 372 (November): 192–206. https://doi.org/10.4204/EPTCS.372.14.
Patterson, Evan, Andrew Baas, Timothy Hosgood, and James Fairbanks. 2022. “A Diagrammatic View of Differential Equations in Physics.” Mathematics in Engineering 5 (2): 1–59. https://doi.org/10.3934/mine.2023036.
Patterson, Evan, Owen Lynch, and James Fairbanks. 2022. “Categorical Data Structures for Technical Computing.” Compositionality 4 (December): 5. https://doi.org/10.32408/compositionality-4-5.
Vagner, Dmitry, David I. Spivak, and Eugene Lerman. 2015. “Algebras of Open Dynamical Systems on the Operad of Wiring Diagrams.” arXiv. https://doi.org/10.48550/arXiv.1408.1598.