Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TemplateGroupTheory.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2013 Christian Seiler <christian@iwakd.de>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
12#define EIGEN_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
13
14// IWYU pragma: private
15#include "../InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21namespace group_theory {
22
34
35/**********************************************************************
36 * "Ok kid, here is where it gets complicated."
37 * - Amelia Pond in the "Doctor Who" episode
38 * "The Big Bang"
39 *
40 * Dimino's algorithm
41 * ==================
42 *
43 * The following is Dimino's algorithm in sequential form:
44 *
45 * Input: identity element, list of generators, equality check,
46 * multiplication operation
47 * Output: list of group elements
48 *
49 * 1. add identity element
50 * 2. remove identities from list of generators
51 * 3. add all powers of first generator that aren't the
52 * identity element
53 * 4. go through all remaining generators:
54 * a. if generator is already in the list of elements
55 * -> do nothing
56 * b. otherwise
57 * i. remember current # of elements
58 * (i.e. the size of the current subgroup)
59 * ii. add all current elements (which includes
60 * the identity) each multiplied from right
61 * with the current generator to the group
62 * iii. add all remaining cosets that are generated
63 * by products of the new generator with itself
64 * and all other generators seen so far
65 *
66 * In functional form, this is implemented as a long set of recursive
67 * templates that have a complicated relationship.
68 *
69 * The main interface for Dimino's algorithm is the template
70 * enumerate_group_elements. All lists are implemented as variadic
71 * type_list<typename...> and std::integer_sequence<int, ...>
72 * templates.
73 *
74 * 'Calling' templates is usually done via typedefs.
75 *
76 * This algorithm is an extended version of the basic version. The
77 * extension consists in the fact that each group element has a set
78 * of flags associated with it. Multiplication of two group elements
79 * with each other results in a group element whose flags are the
80 * XOR of the flags of the previous elements. Each time the algorithm
81 * notices that a group element it just calculated is already in the
82 * list of current elements, the flags of both will be compared and
83 * added to the so-called 'global flags' of the group.
84 *
85 * The rationale behind this extension is that this allows not only
86 * for the description of symmetries between tensor indices, but
87 * also allows for the description of hermiticity, antisymmetry and
88 * antihermiticity. Negation and conjugation each are specific bit
89 * in the flags value and if two different ways to reach a group
90 * element lead to two different flags, this poses a constraint on
91 * the allowed values of the resulting tensor. For example, if a
92 * group element is reached both with and without the conjugation
93 * flags, it is clear that the resulting tensor has to be real.
94 *
95 * Note that this flag mechanism is quite generic and may have other
96 * uses beyond tensor properties.
97 *
98 * IMPORTANT:
99 * This algorithm assumes the group to be finite. If you try to
100 * run it with a group that's infinite, the algorithm will only
101 * terminate once you hit a compiler limit (max template depth).
102 * Also note that trying to use this implementation to create a
103 * very large group will probably either make you hit the same
104 * limit, cause the compiler to segfault or at the very least
105 * take a *really* long time (hours, days, weeks - sic!) to
106 * compile. It is not recommended to plug in more than 4
107 * generators, unless they are independent of each other.
108 */
109
123template <template <typename, typename> class Equality, typename id, typename L>
124struct strip_identities;
125
126template <template <typename, typename> class Equality, typename id, typename t, typename... ts>
127struct strip_identities<Equality, id, type_list<t, ts...>> {
128 using type = std::conditional_t<
129 Equality<id, t>::value, typename strip_identities<Equality, id, type_list<ts...>>::type,
130 typename concat<type_list<t>, typename strip_identities<Equality, id, type_list<ts...>>::type>::type>;
131 constexpr static int global_flags =
132 Equality<id, t>::global_flags | strip_identities<Equality, id, type_list<ts...>>::global_flags;
133};
134
135template <template <typename, typename> class Equality, typename id>
136struct strip_identities<Equality, id, type_list<>> {
137 using type = type_list<>;
138 constexpr static int global_flags = 0;
139};
140
154template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
155 typename g, typename current_element, typename elements,
156 bool dont_add_current_element // = false
157 >
158struct dimino_first_step_elements_helper
159#ifndef EIGEN_PARSED_BY_DOXYGEN
160 : // recursive inheritance is too difficult for Doxygen
161 public dimino_first_step_elements_helper<Multiply, Equality, id, g, typename Multiply<current_element, g>::type,
162 typename concat<elements, type_list<current_element>>::type,
163 Equality<typename Multiply<current_element, g>::type, id>::value> {
164};
165
166template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
167 typename g, typename current_element, typename elements>
168struct dimino_first_step_elements_helper<Multiply, Equality, id, g, current_element, elements, true>
169#endif // EIGEN_PARSED_BY_DOXYGEN
170{
171 using type = elements;
172 constexpr static int global_flags = Equality<current_element, id>::global_flags;
173};
174
188template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
189 typename generators>
190struct dimino_first_step_elements {
191 using first_generator = typename get<0, generators>::type;
192 using next_generators = typename skip<1, generators>::type;
193 using generators_done = type_list<first_generator>;
194
195 using helper =
196 dimino_first_step_elements_helper<Multiply, Equality, id, first_generator, first_generator, type_list<id>, false>;
197 using type = typename helper::type;
198 constexpr static int global_flags = helper::global_flags;
199};
200
221template <template <typename, typename> class Multiply, typename sub_group_elements, typename new_coset_rep,
222 bool generate_coset // = true
223 >
224struct dimino_get_coset_elements {
225 using type = typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type;
226};
227
228template <template <typename, typename> class Multiply, typename sub_group_elements, typename new_coset_rep>
229struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false> {
230 using type = type_list<>;
231};
232
247template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
248 typename sub_group_elements, typename elements, typename generators, typename rep_element, int sub_group_size>
249struct dimino_add_cosets_for_rep;
250
251template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
252 typename sub_group_elements, typename elements, typename g, typename... gs, typename rep_element,
253 int sub_group_size>
254struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element,
255 sub_group_size> {
256 using new_coset_rep = typename Multiply<rep_element, g>::type;
257 using _cil = contained_in_list_gf<Equality, new_coset_rep, elements>;
258 constexpr static bool add_coset = !_cil::value;
259
260 using coset_elements =
261 typename dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, add_coset>::type;
262
263 using _helper = dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements,
264 typename concat<elements, coset_elements>::type, type_list<gs...>,
265 rep_element, sub_group_size>;
266
267 using type = typename _helper::type;
268 constexpr static int global_flags = _cil::global_flags | _helper::global_flags;
269
270 /* Note that we don't have to update global flags here, since
271 * we will only add these elements if they are not part of
272 * the group already. But that only happens if the coset rep
273 * is not already in the group, so the check for the coset rep
274 * will catch this.
275 */
276};
277
278template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
279 typename sub_group_elements, typename elements, typename rep_element, int sub_group_size>
280struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<>, rep_element,
281 sub_group_size> {
282 using type = elements;
283 constexpr static int global_flags = 0;
284};
285
300template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
301 typename sub_group_elements, typename elements, typename generators, int sub_group_size, int rep_pos,
302 bool stop_condition // = false
303 >
304struct dimino_add_all_coset_spaces {
305 using rep_element = typename get<rep_pos, elements>::type;
306 using _ac4r = dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, generators, rep_element,
307 sub_group_elements::count>;
308 using new_elements = typename _ac4r::type;
309
310 constexpr static int new_rep_pos = rep_pos + sub_group_elements::count;
311 constexpr static bool new_stop_condition = new_rep_pos >= new_elements::count;
312
313 using _helper = dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, new_elements, generators,
314 sub_group_size, new_rep_pos, new_stop_condition>;
315
316 using type = typename _helper::type;
317 constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
318};
319
320template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
321 typename sub_group_elements, typename elements, typename generators, int sub_group_size, int rep_pos>
322struct dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, elements, generators, sub_group_size,
323 rep_pos, true> {
324 using type = elements;
325 constexpr static int global_flags = 0;
326};
327
340template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
341 typename elements, typename generators_done, typename current_generator,
342 bool redundant // = false
343 >
344struct dimino_add_generator {
345 /* this template is only called if the generator is not redundant
346 * => all elements of the group multiplied with the new generator
347 * are going to be new elements of the most trivial coset space
348 */
349 using multiplied_elements = typename apply_op_from_right<Multiply, current_generator, elements>::type;
350 using new_elements = typename concat<elements, multiplied_elements>::type;
351
352 constexpr static int rep_pos = elements::count;
353
354 using _helper =
355 dimino_add_all_coset_spaces<Multiply, Equality, id,
356 elements, // elements of previous subgroup
357 new_elements, typename concat<generators_done, type_list<current_generator>>::type,
358 elements::count, // size of previous subgroup
359 rep_pos,
360 false // don't stop (because rep_pos >= new_elements::count is always false at this
361 // point)
362 >;
363 using type = typename _helper::type;
364 constexpr static int global_flags = _helper::global_flags;
365};
366
367template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
368 typename elements, typename generators_done, typename current_generator>
369struct dimino_add_generator<Multiply, Equality, id, elements, generators_done, current_generator, true> {
370 // redundant case
371 using type = elements;
372 constexpr static int global_flags = 0;
373};
374
387template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
388 typename generators_done, typename remaining_generators, typename elements>
389struct dimino_add_remaining_generators {
390 using first_generator = typename get<0, remaining_generators>::type;
391 using next_generators = typename skip<1, remaining_generators>::type;
392
393 using _cil = contained_in_list_gf<Equality, first_generator, elements>;
394
395 using _helper = dimino_add_generator<Multiply, Equality, id, elements, generators_done, first_generator, _cil::value>;
396
397 using new_elements = typename _helper::type;
398
399 using _next_iter = dimino_add_remaining_generators<Multiply, Equality, id,
400 typename concat<generators_done, type_list<first_generator>>::type,
401 next_generators, new_elements>;
402
403 using type = typename _next_iter::type;
404 constexpr static int global_flags = _cil::global_flags | _helper::global_flags | _next_iter::global_flags;
405};
406
407template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
408 typename generators_done, typename elements>
409struct dimino_add_remaining_generators<Multiply, Equality, id, generators_done, type_list<>, elements> {
410 using type = elements;
411 constexpr static int global_flags = 0;
412};
413
428template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
429 typename generators, int initial_global_flags = 0>
430struct enumerate_group_elements_noid {
431 using first_step = dimino_first_step_elements<Multiply, Equality, id, generators>;
432
433 using _helper = dimino_add_remaining_generators<Multiply, Equality, id, typename first_step::generators_done,
434 typename first_step::next_generators, // remaining_generators
435 typename first_step::type // first_step elements
436 >;
437
438 using type = typename _helper::type;
439 constexpr static int global_flags = initial_global_flags | first_step::global_flags | _helper::global_flags;
440};
441
442// in case when no generators are specified
443template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
444 int initial_global_flags>
445struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags> {
446 using type = type_list<id>;
447 constexpr static int global_flags = initial_global_flags;
448};
449
467template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
468 typename Generators_>
469struct enumerate_group_elements
470 : public enumerate_group_elements_noid<Multiply, Equality, id,
471 typename strip_identities<Equality, id, Generators_>::type,
472 strip_identities<Equality, id, Generators_>::global_flags> {};
473
474} // end namespace group_theory
475
476} // end namespace internal
477
478} // end namespace Eigen
479
480#endif // EIGEN_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
481
482/*
483 * kate: space-indent on; indent-width 2; mixedindent off; indent-mode cstyle;
484 */
Namespace containing all symbols from the Eigen library.