Tensor Arithmetics on Minimal Amount of Domains

[mjungmath]

If I get the code correctly, operations between two tensor fields on non-parallelizable manifolds are performed as follows:

1. get common domains from the _restrictions dictionary,
2. perform the corresponding operation on each of those domains.

However, in most cases not all domains are necessary to fully determine the result. It is enough to find a minimal set of common domains which cover the manifold and perform the computation on those. The wanted restrictions of the result can then be computed on demand.

Allow me an example:

sage: M = Manifold(2, 'S^2') # the 2-dimensional sphere S^2
sage: U = M.open_subset('U') # complement of the North pole
sage: c_xy.<x,y> = U.chart() # stereographic coordinates from the North pole
sage: V = M.open_subset('V') # complement of the South pole
sage: c_uv.<u,v> = V.chart() # stereographic coordinates from the South pole
sage: M.declare_union(U,V)   # S^2 is the union of U and V
sage: xy_to_uv = c_xy.transition_map(c_uv, (x/(x^2+y^2), y/(x^2+y^2)),
....:                                intersection_name='W',
....:                                restrictions1=x^2+y^2!=0,
....:                                restrictions2=u^2+v^2!=0)
sage: uv_to_xy = xy_to_uv.inverse()
sage: W = U.intersection(V)
sage: eU = c_xy.frame()
sage: eV = c_uv.frame()
sage: v = M.vector_field(name='v')
sage: v[eU,:] = [1, -2]
sage: v.add_comp_by_continuation(eV, W, chart=c_uv)
sage: v._restrictions
{Open subset U of the 2-dimensional differentiable manifold S^2: Vector field v on the Open subset U of the 2-dimensional differentiable manifold S^2,
 Open subset W of the 2-dimensional differentiable manifold S^2: Vector field v on the Open subset W of the 2-dimensional differentiable manifold S^2,
 Open subset V of the 2-dimensional differentiable manifold S^2: Vector field v on the Open subset V of the 2-dimensional differentiable manifold S^2}

Now, if you add v and another vector field defined similarly, the addition would be performed on U, V and W. Even though the computation on W is not necessary.

CC: @egourgoulhon @tscrim @mkoeppe

Component: manifolds

Issue created by migration from https://trac.sagemath.org/ticket/30714

[mkoeppe]

comment:1

This is an NP-hard optimization problem.

[egourgoulhon]

comment:2

Maybe one shall introduce the concept of "top restrictions", i.e. restrictions that are not restrictions of a larger restriction on a parallelizable domain (there are already similar concepts in TopologicalManifold._top_charts and DifferentiableManifold._top_frames). Then the method TensorField._common_subdomains(), which is invoked by _add_(), could deal only with these top restrictions.

[mjungmath]

comment:3

Replying to @mkoeppe:

This is an NP-hard optimization problem.

I'm sorry, I don't know what you mean. Can you explain please?

[mjungmath]

comment:4

Just for the records, I have introduced a method called _get_min_covering for characteristic forms and orientations (you can find it in manifold.py), which returns the minimal amount of objects necessary to cover the manifold. Maybe this is something we can use? I don't know how speedy it is compared to the computational cost we might save.

[mjungmath]

comment:5

Replying to @egourgoulhon:

Maybe one shall introduce the concept of "top restrictions", i.e. restrictions that are not restrictions of a larger restriction on a parallelizable domain (there are already similar concepts in TopologicalManifold._top_charts and DifferentiableManifold._top_frames). Then the method TensorField._common_subdomains(), which is invoked by _add_(), could deal only with these top restrictions.

This sounds like a great idea to me. I'm eager to hear what Matthias and Travis think about it.

[mkoeppe]

comment:7

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mjungmath]

comment:8

Possibly related: #31740, #31703.

[mkoeppe]

comment:10

A first step in line with #31740 could be to introduce methods TensorField.restriction_digraph, .restriction_poset etc. in analogy to ManifoldSubset.subset_{digraph,subset} (most recent version in #31736).
A generator of the top elements of the poset then comes for free - see #31766.

[mjungmath]

comment:11

Perhaps it is a good idea to implement that behavior into sheaves (#31703) first and then wrap this over tensors and vb sections etc.