non-deterministic matrix assembly for multiple domains

[stevengj]

@mochen4 pointed out via email that Gridap's matrix assembly yields non-deterministic roundoff errors, e.g. the matrices from this tutorial change on the order of machine precision from run to run. This makes debugging harder, and is especially inconvenient if the Gridap outputs are fed into some calculation exhibiting chaos or instability (e.g. we noticed it in optimization problems exhibiting spontaneous symmetry breaking, which converge to a local optimum that is sensitively affected by tiny discrepancies).

@fverdugo wrote to explain:

we use a Dict to store the contributions of several domains to an integral. This can definitely be a cause of operations being done in non deterministic order.

and indeed the issue arises in problems involving multiple domains. Essentially, Dict iteration depends on the hashing algorithm, and Julia's default hashing algorithm for a struct uses the pointer address (objectid), which is effectively non-deterministic. Changing iteration order can change the floating-point roundoff errors of a sum.

The solution is, in principle, simple — just implement a custom hash function (and ==) that is deterministic for any object that is used as a Dict key. Question: which data structures in Gridap need this?

[JordiManyer]

This would only affect the DomainContribution structure, which stores a dictionary of Triangulation objects. So the hash would be on the triangulations.

[fverdugo]

Another option is to use another dict type that preserves insertion order, e.g.:

https://juliacollections.github.io/DataStructures.jl/stable/ordered_containers/#OrderedDicts-and-OrderedSets-1

@mochen4 can you try to use an OrderedDict here?

Gridap.jl/src/CellData/DomainContributions.jl

Line 5 in 532e8de

dict::IdDict{Triangulation,AbstractArray}

[stevengj]

Using an OrderedDict makes a lot of sense here.

Otherwise, you'd have to switch to an ordinary Dict (not IdDict, which always hashes based on the pointer), and implement a hash for the triangulation, which would make lookup more expensive (because it would have to look at the whole triangulation to hash it). Does performance matter here? Of course, a simple workaround would be to store a hash of the Triangulation object in the object itself, so that you'd only pay the hash cost once when the object is constructed.

[mochen4]

@mochen4 can you try to use an OrderedDict here?

Gridap.jl/src/CellData/DomainContributions.jl

Line 5 in 532e8de

dict::IdDict{Triangulation,AbstractArray}

Using OrderedDict fixes the issue for me.

[stevengj]

@mochen4, can you make a pull request that makes this 1-line change (also changing the Project.toml to add the DataStructures dependency)?

[mochen4]

@mochen4, can you make a pull request that makes this 1-line change (also changing the Project.toml to add the DataStructures dependency)?

The DataStructures dependency is already specified in Project.toml

Gridap.jl/Project.toml

Line 11 in 632d695

DataStructures = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"

So I simply added using dataStrutures in DomainContributions.jl