How do you generate compact level-0 agglomerates (leaf nodes)?

[EssenFOAM]

I could not find the key codes for generating the level-0 nodes (groups of cells' AABBs): like a process of decomposing the mesh into N tiny partitions (10-20 cells).

Do you use the lib-boost RTree packing algorithms (STR or Hilbert curve indexing)?

By the way, I have installed deal.II successfully, but still could not compile the Polydeal codes.
Mostly related to example files:

/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:243:13:
error: static assertion failed: Target type is neither std::istreamable nor std::wistreamable
243 | BOOST_STATIC_ASSERT_MSG((result_t::value || boost::has_right_shift<std::basic_istream<wchar_t>, T >::value),

[fdrmrc]

Hi @EssenFOAM,

I could not find the key codes for generating the level-0 nodes (groups of cells' AABBs): like a process of decomposing the mesh into N tiny partitions (10-20 cells).

If I understand correctly, you are asking how to extract the coarsest level of the tree. Is this correct? If so, I can attach here a minimal working example, adapting one of the examples program you can find in the examples/ folder.

Do you use the lib-boost RTree packing algorithms (STR or Hilbert curve indexing)?

The R-tree generation is done through boost. The hierarchy traversal, instead, is not natively supported in boost and was done through a suitable visitor.

By the way, I have installed deal.II successfully, but still could not compile the Polydeal codes. Mostly related to example files:

I assume you are using a deal.II version greater than or equal to 9.7. You mentioned that the example files are not compiling, but you did not specify which ones. Could you please share the full compiler log so that I can better understand the issue and help you diagnose the problem, along with your detailed.log deal.II configuration file?

[EssenFOAM]

Thanks for the reply.

1. So the whole mesh agglomeration process is handled by the Boost geometry library? I am particularly interested in how the leaf nodes (consisting of cell AABBs) are constructed, such that leaf nodes have compact shapes and a near-uniform number of cells.

The face-area-based mesh agglomeration algorithm (e.g., in OpenFOAM) is complex to implement. I would appreciate it if you could attach a minimal working code to show multi-layer agglomerates using R*-tree (vtk format), so we can compare it to the mesh agglomerates generated in OpenFOAM, which are not great intuitively (non-compact, and irregularly shaped) for a non-box-like mesh domain.

E.g. Pseudo 2D mesh agglomeration, level 6

and 3D mesh agglomeration

3D mesh agglomeration - level 13

2. I compiled deal.II 9.7.1, for Polydeal

[examples]$ make
[ 0%] Building CXX object source/CMakeFiles/polydeal.dir/agglomeration_handler.cc.o
[ 0%] Linking CXX shared library libpolydeal.so
[ 13%] Built target polydeal
[ 13%] Building CXX object examples/CMakeFiles/3D_piston.dir/3D_piston.cc.o
[ 13%] Linking CXX executable 3D_piston
[ 13%] Built target 3D_piston
Consolidate compiler generated dependencies of target agglo_amg
[ 20%] Building CXX object examples/CMakeFiles/agglo_amg.dir/agglo_amg.cc.o
In file included from /usr/include/boost/geometry/core/coordinate_dimension.hpp:21,
from /usr/include/boost/geometry/geometries/point.hpp:33,
from /usr/local/dealII/include/deal.II/base/point.h:27,
from /usr/local/dealII/include/deal.II/base/function.h:25,
from /usr/local/dealII/include/deal.II/base/function_lib.h:21,
from /home/dao/FEM_codes/R3MG_Agglo/examples/agglo_amg.cc:18:
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp: In instantiation of ‘struct boost::detail::deduce_target_char_impl<boost::detail::deduce_character_type_later<__float128> >’:
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:270:89: required from ‘struct boost::detail::deduce_target_char<__float128>’
270 | typedef BOOST_DEDUCED_TYPENAME deduce_target_char_impl< stage1_type >::type stage2_type;
| ^~~~~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:407:92: required from ‘struct boost::detail::lexical_cast_stream_traits<std::__cxx11::basic_string, __float128>’
407 | typedef BOOST_DEDUCED_TYPENAME boost::detail::deduce_target_char::type target_char_t;
| ^~~~~~~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:468:15: required from ‘struct boost::detail::lexical_converter_impl<__float128, std::__cxx11::basic_string >’
468 | > i_interpreter_type;
| ^~~~~~~~~~~~~~~~~~
/usr/include/boost/lexical_cast/try_lexical_convert.hpp:201:44: required from ‘bool boost::conversion::detail::try_lexical_convert(const Source&, Target&) [with Target = __float128; Source = std::__cxx11::basic_string]’
201 | return caster_type::try_convert(arg, result);
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/boost/lexical_cast.hpp:41:60: required from ‘Target boost::lexical_cast(const Source&) [with Target = float128; Source = std::cxx11::basic_string]’
41 | if (!boost::conversion::detail::try_lexical_convert(arg, result)) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/boost/multiprecision/detail/default_ops.hpp:975:45: required from ‘void boost::multiprecision::default_ops::last_chance_eval_convert_to(terminal*, const B&, const mpl::false&) [with R = float128; B = boost::multiprecision::backends::gmp_int; mpl::false = mpl::bool]’
975 | result->value = boost::lexical_cast(backend.str(0, std::ios_base::fmtflags(0)));
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/multiprecision/detail/default_ops.hpp:1019:31: required from ‘constexpr void boost::multiprecision::default_ops::eval_convert_to(terminal, const B&) [with R = __float128; B = boost::multiprecision::backends::gmp_int]’
1019 | last_chance_eval_convert_to(result, backend, tag_type());
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/multiprecision/detail/default_ops.hpp:955:19: required from ‘constexpr typename boost::disable_if_c<boost::is_integral::value>::type boost::multiprecision::default_ops::eval_convert_to(R, const B&) [with R = __float128; B = boost::multiprecision::backends::gmp_int; typename boost::disable_if_c<boost::is_integral::value>::type = void]’
955 | eval_convert_to(&n, backend);
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/boost/multiprecision/gmp.hpp:2223:19: required from here
2223 | eval_convert_to(&fn, n);
| ~~~~~~~~~~~~~~~^~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:243:13: error: static assertion failed: Target type is neither std::istreamable nor std::wistreamable
243 | BOOST_STATIC_ASSERT_MSG((result_t::value || boost::has_right_shift<std::basic_istream<wchar_t>, T >::value),
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:243:13: note: ‘(((bool)boost::integral_constant<bool, false>::value) || ((bool)boost::integral_constant<bool, false>::value))’ evaluates to false
make[2]: *** [examples/CMakeFiles/agglo_amg.dir/build.make:76: examples/CMakeFiles/agglo_amg.dir/agglo_amg.cc.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:339: examples/CMakeFiles/agglo_amg.dir/all] Error 2
make: *** [Makefile:146: all] Error 2

By patching this: I could successfully compiled few test cases. But could not eliminate all BOOST_STATIC_ASSERT_MSG errors.

#include <string> #include <quadmath.h> // Required for strtoflt128 namespace std { inline istream& operator>>(istream& is, __float128& f) { std::string s; if (is >> s) { f = strtoflt128(s.c_str(), nullptr); } return is; } }

[fdrmrc]

Hi @EssenFOAM,

So the whole mesh agglomeration process is handled by the Boost geometry library? I am particularly interested in how the leaf nodes (consisting of cell AABBs) are constructed, such that leaf nodes have compact shapes and a near-uniform number of cells.

The tree data structure is generated by Boost. We then traverse the tree using a custom visitor, which is used to agglomerate cells.
Therefore, the agglomeration itself is not something that Boost provides.

I would appreciate it if you could attach a minimal working code to show multi-layer agglomerates using R*-tree (vtk format), so we can compare [...]

I would be happy to show here results using the geometries you provided. Could you please let me know where I can find the corresponding mesh files?

I compiled deal.II 9.7.1, for Polydeal

Could you please attach the detailed.log file generated by deal.II before the installation process? It should be located in the directory where you installed deal.II.

[EssenFOAM]

2D_Agglomeration_VTK.zip

3D_agglomeration_L13.zip

Attached is the vtk format of the agglomerations.

There is the detailed.log from deal.II/build
detailed.log

Could you please give a minimal working code of R3MG such that we can directly output agglomerations (multi-layers) to vtk files? Thanks a lot!

[fdrmrc]

Hi @EssenFOAM,

I have applied the R-tree-based agglomeration to generate a hierarchy from the 3D mesh you sent. Please let me know if you find the results satisfactory. If so, I am happy to provide a self-contained MWE.

Below are the results for two of the generated levels. They appear visually identical, but note the different range of agglo_idx.

1250 agglomerates	10000 agglomerates

To better appreciate the nestedness between levels and the shape of the partitions:

On the left, one coarser element of the hierarchy. On the right, the eight sub-agglomerates (not all of them are visible).

A typical output of the program gives:

Size of original triangulation: 640000
Total number of available tree levels: 6
R-tree agglomerates built in 0.24136 seconds [Wall Clock]
N agglomerates = 10000

[EssenFOAM]

It looks pretty neat! I want to try your self-contained MWE - the R*-tree agglomerations vs face-area (pair-wise) agglomerations for the Geometric AMG solver, and compare the performance on the pressure equation in CFD.

Thanks!

[fdrmrc]

We have a series of examples that exploit agglomeration to perform Geometric-AMG for elliptic-like problems. To simplify the discussion and share the relevant details, could you please reach out to me by email?

For instance, it would be helpful to discuss the geometry, boundary conditions, right-hand side, solver tolerances, and related parameters.

[fdrmrc]

Concerning the deal.II installation:

• does that error occur also with a random simple tutorial program?
• the issue could be related to the Boost version you are using. Could you try using the bundled version of Boost instead? To do so, specify the following flag at configuration time: -DDEAL_II_FORCE_BUNDLED_BOOST=ON (or edit it via ccmake)

Let me know if this solves the problem

[EssenFOAM]

System Boost version is 1.74 (Ubuntu 22.04)

[build]$ cmake -DDEAL_II_DIR=/usr/local/dealII -DDEAL_II_FORCE_BUNDLED_BOOST=ON ..
-- Found deal.II version: 9.7.1
-- deal.II installation path: /usr/local/dealII/lib/cmake/deal.II
-- deal.II version 9.7.1 meets the minimum requirement (>= 9.7.0)
-- The C compiler identification is GNU 15.2.0
-- The CXX compiler identification is GNU 15.2.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found Release version of deal.II.
-- Configuring library polydeal
-- Found Release version of deal.II.
-- Configuring executable 3D_piston (/home/dao/FEM_codes/R3MG_Agglo/examples/./3D_piston.cc)
-- Configuring executable agglo_amg (/home/dao/FEM_codes/R3MG_Agglo/examples/./agglo_amg.cc)
-- Configuring executable benchmarks_3D (/home/dao/FEM_codes/R3MG_Agglo/examples/./benchmarks_3D.cc)
-- Configuring executable benchmarks_3D_vtu (/home/dao/FEM_codes/R3MG_Agglo/examples/./benchmarks_3D_vtu.cc)
-- Configuring executable classical_dg_assembly (/home/dao/FEM_codes/R3MG_Agglo/examples/./classical_dg_assembly.cc)
-- Configuring executable darcy_stokes (/home/dao/FEM_codes/R3MG_Agglo/examples/./darcy_stokes.cc)
-- Configuring executable diffusion_reaction (/home/dao/FEM_codes/R3MG_Agglo/examples/./diffusion_reaction.cc)
-- Configuring executable matrix_free_agglo (/home/dao/FEM_codes/R3MG_Agglo/examples/./matrix_free_agglo.cc)
-- Configuring executable metrics (/home/dao/FEM_codes/R3MG_Agglo/examples/./metrics.cc)
-- Configuring executable minimal_SIP (/home/dao/FEM_codes/R3MG_Agglo/examples/./minimal_SIP.cc)
-- MUMPS support detected for monodomain_DG2D
-- Configuring executable monodomain_DG2D (/home/dao/FEM_codes/R3MG_Agglo/examples/./monodomain_DG2D.cc)
-- MUMPS support detected for monodomain_DG3D
-- Configuring executable monodomain_DG3D (/home/dao/FEM_codes/R3MG_Agglo/examples/./monodomain_DG3D.cc)
-- Configuring executable oseen (/home/dao/FEM_codes/R3MG_Agglo/examples/./oseen.cc)
-- Configuring executable poisson (/home/dao/FEM_codes/R3MG_Agglo/examples/./poisson.cc)
-- Configuring executable repairing (/home/dao/FEM_codes/R3MG_Agglo/examples/./repairing.cc)
-- Configuring executable simplex_agglomerated_multigrid (/home/dao/FEM_codes/R3MG_Agglo/examples/./simplex_agglomerated_multigrid.cc)
-- Found Release version of deal.II.
-- Configuring test for polydeal
-- Found UnixCommands: /usr/bin/bash
-- Found Perl: /usr/bin/perl (found version "5.34.0")
-- Test category polydeal : 52 tests (and 19 test dependencies)
-- Configuring done
-- Generating done
CMake Warning:
**Manually-specified variables were not used by the project:

DEAL_II_FORCE_BUNDLED_BOOST**

-- Build files have been written to: /home/dao/FEM_codes/R3MG_Agglo/build

[build]$ make -j 6
[ 0%] Building CXX object source/CMakeFiles/polydeal.dir/agglomeration_handler.cc.o
[ 0%] Building CXX object source/CMakeFiles/polydeal.dir/mapping_box.cc.o
[ 13%] Building CXX object source/CMakeFiles/polydeal.dir/fe_agglodgp.cc.o
[ 13%] Building CXX object source/CMakeFiles/polydeal.dir/multigrid_amg.cc.o
[ 13%] Linking CXX shared library libpolydeal.so
[ 13%] Built target polydeal
[ 20%] Building CXX object examples/CMakeFiles/agglo_amg.dir/agglo_amg.cc.o
[ 20%] Building CXX object examples/CMakeFiles/benchmarks_3D_vtu.dir/benchmarks_3D_vtu.cc.o
[ 20%] Building CXX object examples/CMakeFiles/3D_piston.dir/3D_piston.cc.o
[ 26%] Building CXX object examples/CMakeFiles/benchmarks_3D.dir/benchmarks_3D.cc.o
In file included from /usr/include/boost/geometry/core/coordinate_dimension.hpp:21,
from /usr/include/boost/geometry/geometries/point.hpp:33,
from /usr/local/dealII/include/deal.II/base/point.h:27,
from /usr/local/dealII/include/deal.II/base/function.h:25,
from /usr/local/dealII/include/deal.II/base/function_lib.h:21,
from /home/dao/FEM_codes/R3MG_Agglo/examples/agglo_amg.cc:18:
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp: In instantiation of ‘struct boost::detail::deduce_target_char_impl<boost::detail::deduce_character_type_later<__float128> >’:
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:270:89: required from ‘struct boost::detail::deduce_target_char<__float128>’
270 | typedef BOOST_DEDUCED_TYPENAME deduce_target_char_impl< stage1_type >::type stage2_type;
| ^~~~~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:407:92: required from ‘struct boost::detail::lexical_cast_stream_traits<std::__cxx11::basic_string, __float128>’
407 | typedef BOOST_DEDUCED_TYPENAME boost::detail::deduce_target_char::type target_char_t;
| ^~~~~~~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:468:15: required from ‘struct boost::detail::lexical_converter_impl<__float128, std::__cxx11::basic_string >’
468 | > i_interpreter_type;
| ^~~~~~~~~~~~~~~~~~
/usr/include/boost/lexical_cast/try_lexical_convert.hpp:201:44: required from ‘bool boost::conversion::detail::try_lexical_convert(const Source&, Target&) [with Target = __float128; Source = std::__cxx11::basic_string]’
201 | return caster_type::try_convert(arg, result);
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/boost/lexical_cast.hpp:41:60: required from ‘Target boost::lexical_cast(const Source&) [with Target = float128; Source = std::cxx11::basic_string]’
41 | if (!boost::conversion::detail::try_lexical_convert(arg, result)) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/boost/multiprecision/detail/default_ops.hpp:975:45: required from ‘void boost::multiprecision::default_ops::last_chance_eval_convert_to(terminal*, const B&, const mpl::false&) [with R = float128; B = boost::multiprecision::backends::gmp_int; mpl::false = mpl::bool]’
975 | result->value = boost::lexical_cast(backend.str(0, std::ios_base::fmtflags(0)));
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/multiprecision/detail/default_ops.hpp:1019:31: required from ‘constexpr void boost::multiprecision::default_ops::eval_convert_to(terminal, const B&) [with R = __float128; B = boost::multiprecision::backends::gmp_int]’
1019 | last_chance_eval_convert_to(result, backend, tag_type());
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/multiprecision/detail/default_ops.hpp:955:19: required from ‘constexpr typename boost::disable_if_c<boost::is_integral::value>::type boost::multiprecision::default_ops::eval_convert_to(R, const B&) [with R = __float128; B = boost::multiprecision::backends::gmp_int; typename boost::disable_if_c<boost::is_integral::value>::type = void]’
955 | eval_convert_to(&n, backend);
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/boost/multiprecision/gmp.hpp:2223:19: required from here
2223 | eval_convert_to(&fn, n);
| ~~~~~~~~~~~~~~~^~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:243:13: error: static assertion failed: Target type is neither std::istreamable nor std::wistreamable
243 | BOOST_STATIC_ASSERT_MSG((result_t::value || boost::has_right_shift<std::basic_istream<wchar_t>, T >::value),
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:243:13: note: ‘(((bool)boost::integral_constant<bool, false>::value) || ((bool)boost::integral_constant<bool, false>::value))’ evaluates to false
make[2]: *** [examples/CMakeFiles/agglo_amg.dir/build.make:76: examples/CMakeFiles/agglo_amg.dir/agglo_amg.cc.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:339: examples/CMakeFiles/agglo_amg.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs....
[ 26%] Linking CXX executable benchmarks_3D
[ 33%] Linking CXX executable benchmarks_3D_vtu
[ 33%] Built target benchmarks_3D
[ 33%] Built target benchmarks_3D_vtu
[ 33%] Linking CXX executable 3D_piston
[ 33%] Built target 3D_piston
make: *** [Makefile:146: all] Error 2

If we repeat:

[build]$ make -j 6
[ 13%] Built target polydeal
Consolidate compiler generated dependencies of target agglo_amg
[ 13%] Built target 3D_piston
[ 20%] Built target benchmarks_3D
[ 26%] Built target benchmarks_3D_vtu
Consolidate compiler generated dependencies of target classical_dg_assembly
Consolidate compiler generated dependencies of target darcy_stokes
Consolidate compiler generated dependencies of target diffusion_reaction
[ 33%] Building CXX object examples/CMakeFiles/agglo_amg.dir/agglo_amg.cc.o
[ 40%] Built target classical_dg_assembly
Consolidate compiler generated dependencies of target matrix_free_agglo
[ 46%] Built target diffusion_reaction
[ 46%] Building CXX object examples/CMakeFiles/darcy_stokes.dir/darcy_stokes.cc.o
[ 46%] Building CXX object examples/CMakeFiles/metrics.dir/metrics.cc.o
[ 53%] Building CXX object examples/CMakeFiles/matrix_free_agglo.dir/matrix_free_agglo.cc.o
+
similar errors as above.

we have more examples compiled. Weird behavior.

[fdrmrc]

Sorry for not being precise earlier. The flag DEAL_II_FORCE_BUNDLED_BOOST was meant to be used during the configuration phase of deal.II.