Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: Euler's Method as a Free Category

Jade Master (Oct 13 2020 at 05:18):

I blogged about how you can get runs of Euler's method by taking free categories:

• https://jadeedenstarmaster.wordpress.com/2020/10/13/eulers-method-as-a-free-category/

Morgan Rogers (he/him) (Oct 13 2020 at 09:56):

That was fun to read. Is it true that a [stationary point or cycle] corresponds to a faithful inclusion of $\mathbb{N}$ into the resulting free category; if not, in what ways can that fail?

Matteo Capucci (he/him) (Oct 13 2020 at 11:08):

Very cool! :) this begs the question: what happens as $h \to 0$? Euler's method converges to the true solution, does the category $F(A_h)$ 'converge' to a category where

• objects are points of $\Bbb{R}^n$ and
• morphisms $x \to y$ are 'arcs of solutions' from $x$ to $y$?

It seems reasonable!
On a related note (which might help to answer the above question of mine), one might also construct the category $F(A_h)$ as the 'actor category' of a discretized version of the flow of the vector field defining the ODE on $\Bbb{R}^n$.
Let me explain.
The actor category associated to an action of a monoid $G$ on a set $X$ is the category whose set of objects is $X$ and whose morphisms $x \to y$ are elements $g \in G$ such that $g.x = y$.
If one starts with a nice enough ODE, its flow $\varphi_t$ is a monoidal action of $\Bbb{R}^+$ on $\Bbb{R}^n$: it brings a point $x$ to the point $y$ you get if you let the ODE start at $x$ and then 'wait' for $t$ units of time. This action can easily be discretized: choose a stepsize $h$, you get an action $\varphi^h_k$ of $\N$ on $\Bbb{R}^n$ generated by posing $\varphi^h_1(x) = x + h v(x)$, as in your blog post. In fact, we could call these the 'Euler's actions' associated to a given ODE.

Matteo Capucci (he/him) (Oct 13 2020 at 11:20):

Actually, once $h$ is chosen, there a lot of possible discretizations, each encoded by a functor between the (sub)category of $\Bbb{R}^+$-actions and the (sub)category of $\Bbb{N}$-actions on $\Bbb{R}^n$. I conjecture each corresponds to a numerical integration method with fixed stepsize.

Jacques Carette (Oct 13 2020 at 12:14):

Sorry to be skeptical here, but since the core of Euler's method, i.e. $x(t+h)=x(t)+h v(x(t))$ is taken as given, this just amounts to saying you can do iteration via the Free Category construction - which is quite well-known. I came here to find out a categorical construction of that 'core'. That would have been quite fascinating indeed.

It might be more honest to rephrase this as 'Iterative Method as a Free Category', with Euler's Method as an application.

Jade Master (Oct 13 2020 at 15:09):

[Mod] Morgan Rogers said:

That was fun to read. Is it true that a [stationary point or cycle] corresponds to a faithful inclusion of $\mathbb{N}$ into the resulting free category; if not, in what ways can that fail?

Yes that sounds right to me! I'm not sure your very likely to get cycles which line up exactly...but if you did it would look like a copy of $\mathbb{N}$.

Jade Master (Oct 13 2020 at 15:19):

Matteo Capucci said:

Very cool! :) this begs the question: what happens as $h \to 0$? Euler's method converges to the true solution, does the category $F(A_h)$ 'converge' to a category where

• objects are points of $\Bbb{R}^n$ and
• morphisms $x \to y$ are 'arcs of solutions' from $x$ to $y$?

It seems reasonable!
On a related note (which might help to answer the above question of mine), one might also construct the category $F(A_h)$ as the 'actor category' of a discretized version of the flow of the vector field defining the ODE on $\Bbb{R}^n$.
Let me explain.
The actor category associated to an action of a monoid $G$ on a set $X$ is the category whose set of objects is $X$ and whose morphisms $x \to y$ are elements $g \in G$ such that $g.x = y$.
If one starts with a nice enough ODE, its flow $\varphi_t$ is a monoidal action of $\Bbb{R}^+$ on $\Bbb{R}^n$: it brings a point $x$ to the point $y$ you get if you let the ODE start at $x$ and then 'wait' for $t$ units of time. This action can easily be discretized: choose a stepsize $h$, you get an action $\varphi^h_k$ of $\N$ on $\Bbb{R}^n$ generated by posing $\varphi^h_1(x) = x + h v(x)$, as in your blog post. In fact, we could call these the 'Euler's actions' associated to a given ODE.

Yeah this is a really nice question. If you let h go to 0 you also get a sequence of spans...but that sequence of spans converges to the identity so there's no way that the free category construction could preserve this sort of limit. I'm still thinking about it.

Regarding the action category stuff. Yes that's very interesting it does seem like you get the same category. That's a nice observation that you can really use any integration method you like. I'm not sure that every functor from $\mathbb{R}$-actions to $\mathbb{N}$-actions is an integration method but regardless there's something interesting going on.

Jade Master (Oct 13 2020 at 15:20):

Jacques Carette said:

Sorry to be skeptical here, but since the core of Euler's method, i.e. $x(t+h)=x(t)+h v(x(t))$ is taken as given, this just amounts to saying you can do iteration via the Free Category construction - which is quite well-known. I came here to find out a categorical construction of that 'core'. That would have been quite fascinating indeed.

It might be more honest to rephrase this as 'Iterative Method as a Free Category', with Euler's Method as an application.

Yes true. This is not a derivation of Euler's method by any means. Just a representation.

Matteo Capucci (he/him) (Oct 13 2020 at 16:20):

Jade Master said:

Yeah this is a really nice question. If you let h go to 0 you also get a sequence of spans...but that sequence of spans converges to the identity so there's no way that the free category construction could preserve this sort of limit. I'm still thinking about it.

Can you elaborate on this? I'd be interested to know the details

Jade Master said:

Regarding the action category stuff. Yes that's very interesting it does seem like you get the same category. That's a nice observation that you can really use any integration method you like. I'm not sure that every functor from $\mathbb{R}$-actions to $\mathbb{N}$-actions is an integration method but regardless there's something interesting going on.

Indeed, some are silly/useless integration algorithms. Some even presuppose the solution to be known in advance. So everything gives you something which behaves like one, but calling every one of them an 'integration algorithm' might be unfair, I concede.

Jade Master (Oct 14 2020 at 17:36):

Matteo Capucci said:

Jade Master said:

Yeah this is a really nice question. If you let h go to 0 you also get a sequence of spans...but that sequence of spans converges to the identity so there's no way that the free category construction could preserve this sort of limit. I'm still thinking about it.

Can you elaborate on this? I'd be interested to know the details

Jade Master said:

Regarding the action category stuff. Yes that's very interesting it does seem like you get the same category. That's a nice observation that you can really use any integration method you like. I'm not sure that every functor from $\mathbb{R}$-actions to $\mathbb{N}$-actions is an integration method but regardless there's something interesting going on.

Indeed, some are silly/useless integration algorithms. Some even presuppose the solution to be known in advance. So everything gives you something which behaves like one, but calling every one of them an 'integration algorithm' might be unfair, I concede.

I mean that you can take the span $\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + hv} \mathbb{R}^n$ and take a sequence $h_n \to 0$ to get a sequence of spans $A_n = \mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + h_n v} \mathbb{R}^n$ which converge to $\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1} \mathbb{R}^n$. On the the other hand the categories $F(A_n)$ converge to the true solution as you noted.

Jade Master (Oct 14 2020 at 17:40):

But $F(\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1} \mathbb{R}^n)$ is the stationary flow so there's no way that F could preserve this limit.

Jade Master (Oct 14 2020 at 17:42):

I might be confused about something...

Jade Master (Oct 14 2020 at 17:43):

btw I don't mean the categorical limit. Just the standard analysis one.

Jade Master (Oct 14 2020 at 17:44):

You could try to tweak the categories a bit so the analysis limit is actually a categorical one though.

Jade Master (Oct 14 2020 at 17:44):

Or more likely a colimit.

Matteo Capucci (he/him) (Oct 14 2020 at 17:44):

Mmmh I see

Matteo Capucci (he/him) (Oct 14 2020 at 17:44):

Jade Master said:

You could try to tweak the categories a bit so the analysis limit is actually a categorical one though.

How? :O

Jade Master (Oct 14 2020 at 17:52):

Matteo Capucci said:

Jade Master said:

You could try to tweak the categories a bit so the analysis limit is actually a categorical one though.

How? :O

One thing you could do is weaken the definition of morphism in $\mathsf{Span}(\mathbb{R}^n,\mathbb{R}^n)$ to the following:

A morphism from a span $\mathbb{R}^n \xleftarrow{f} A \xrightarrow{g} \mathbb{R}^n$ to $\mathbb{R}^n \xleftarrow{h} g \xrightarrow{k} \mathbb{R}^n$ is a function $l : A \to B$ commuting with the legs up to inequality. That is the inequalities
$|f (x)| \leq | h \circ l(x)|$ and
$|g(x)| \leq | k \circ l(x) |$
hold for all points $x \in \mathbb{R}^n$.

Jade Master (Oct 14 2020 at 17:55):

Then the identity function $1 : \mathbb{R}^n \to \mathbb{R}^n$ is a morphism from $\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + h v} \mathbb{R}^n$ to $\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + h'v} \mathbb{R}^n$ whenever $h' \leq h$

Jade Master (Oct 14 2020 at 17:55):

(sorry about the double use of h)

Jade Master (Oct 14 2020 at 17:58):

Then I'm pretty sure that taking the colimit of all the $A_n$ from before in this category gives the identity span on $\mathbb{R}^n$

Jade Master (Oct 14 2020 at 17:58):

I haven't worked out the details though.

Jade Master (Oct 14 2020 at 18:00):

But there's something that's not going to work because F is a left adjoint so it preserves colimits but we know this particular colimit is not preserved.

Jade Master (Oct 14 2020 at 18:01):

Maybe I'm wrong about the $F(A_n)$ converging to the true solution actually :thinking:

Jade Master (Oct 14 2020 at 18:03):

Please don't get mad at me for saying something incorrect in the above I know there's an error somewhere :grinning:

Jade Master (Oct 14 2020 at 18:08):

Yeah I think for the F(A_n) to converge to the true flow, you need the length of the morphisms to go to infinity at the same time.

Jade Master (Oct 14 2020 at 18:09):

So yay it preserves this colimit but we're still not doing analysis :/

John Baez (Oct 14 2020 at 18:31):

It's hard to blend analysis and category theory... I have a feeling they both need to be reworked a lot to do this well. I hope that something like Walter Tholen's notion of metagory will be useful someday - that's a "metric approximate category", where you can talk about how close one morphism comes to being the composite of two others.

John Baez (Oct 14 2020 at 18:37):

We may need a whole lot of new notions like this. But I like how Tholen gets to the bottom of things in this realm: we know the nerve of a category is a simplicial set where tetrahedra give associativity; he shows that in a metric approximate category a "tetrahedral inequality" should hold - sort of the next thing after the triangle inequality!

John Baez (Oct 14 2020 at 18:37):

This is the kind of surprising insight that may show up when we blend category theory and analysis.

Jason Erbele (Oct 14 2020 at 22:01):

Jade Master said:

I mean that you can take the span $\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + hv} \mathbb{R}^n$ and take a sequence $h_n \to 0$ to get a sequence of spans $A_n = \mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + h_n v} \mathbb{R}^n$ which converge to $\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1} \mathbb{R}^n$. On the the other hand the categories $F(A_n)$ converge to the true solution as you noted.

I'm only casually reading this conversation, so I'm probably missing something obvious (or likely, a lot of somethings), but this looks like an abuse of $n$, similar to the abuse of $h$ you apologized for later. Is that right, or do the $n$'s in $A_n$ and $\mathbb{R}^n$ really refer to the same thing?

Jade Master (Oct 14 2020 at 22:04):

Yes, it is a double use of n as well.