TemplateGroupTheory.h
Go to the documentation of this file.
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 
10 #ifndef EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
11 #define EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
12 
13 namespace Eigen {
14 
15 namespace internal {
16 
17 namespace group_theory {
18 
31 /**********************************************************************
32  * "Ok kid, here is where it gets complicated."
33  * - Amelia Pond in the "Doctor Who" episode
34  * "The Big Bang"
35  *
36  * Dimino's algorithm
37  * ==================
38  *
39  * The following is Dimino's algorithm in sequential form:
40  *
41  * Input: identity element, list of generators, equality check,
42  * multiplication operation
43  * Output: list of group elements
44  *
45  * 1. add identity element
46  * 2. remove identities from list of generators
47  * 3. add all powers of first generator that aren't the
48  * identity element
49  * 4. go through all remaining generators:
50  * a. if generator is already in the list of elements
51  * -> do nothing
52  * b. otherwise
53  * i. remember current # of elements
54  * (i.e. the size of the current subgroup)
55  * ii. add all current elements (which includes
56  * the identity) each multiplied from right
57  * with the current generator to the group
58  * iii. add all remaining cosets that are generated
59  * by products of the new generator with itself
60  * and all other generators seen so far
61  *
62  * In functional form, this is implemented as a long set of recursive
63  * templates that have a complicated relationship.
64  *
65  * The main interface for Dimino's algorithm is the template
66  * enumerate_group_elements. All lists are implemented as variadic
67  * type_list<typename...> and numeric_list<typename = int, int...>
68  * templates.
69  *
70  * 'Calling' templates is usually done via typedefs.
71  *
72  * This algorithm is an extended version of the basic version. The
73  * extension consists in the fact that each group element has a set
74  * of flags associated with it. Multiplication of two group elements
75  * with each other results in a group element whose flags are the
76  * XOR of the flags of the previous elements. Each time the algorithm
77  * notices that a group element it just calculated is already in the
78  * list of current elements, the flags of both will be compared and
79  * added to the so-called 'global flags' of the group.
80  *
81  * The rationale behind this extension is that this allows not only
82  * for the description of symmetries between tensor indices, but
83  * also allows for the description of hermiticity, antisymmetry and
84  * antihermiticity. Negation and conjugation each are specific bit
85  * in the flags value and if two different ways to reach a group
86  * element lead to two different flags, this poses a constraint on
87  * the allowed values of the resulting tensor. For example, if a
88  * group element is reach both with and without the conjugation
89  * flags, it is clear that the resulting tensor has to be real.
90  *
91  * Note that this flag mechanism is quite generic and may have other
92  * uses beyond tensor properties.
93  *
94  * IMPORTANT:
95  * This algorithm assumes the group to be finite. If you try to
96  * run it with a group that's infinite, the algorithm will only
97  * terminate once you hit a compiler limit (max template depth).
98  * Also note that trying to use this implementation to create a
99  * very large group will probably either make you hit the same
100  * limit, cause the compiler to segfault or at the very least
101  * take a *really* long time (hours, days, weeks - sic!) to
102  * compile. It is not recommended to plug in more than 4
103  * generators, unless they are independent of each other.
104  */
105 
119 template<template<typename, typename> class Equality, typename id, typename L> struct strip_identities;
120 
121 template<
122  template<typename, typename> class Equality,
123  typename id,
124  typename t,
125  typename... ts
126 >
127 struct strip_identities<Equality, id, type_list<t, ts...>>
128 {
129  typedef typename conditional<
131  typename strip_identities<Equality, id, type_list<ts...>>::type,
132  typename concat<type_list<t>, typename strip_identities<Equality, id, type_list<ts...>>::type>::type
134  constexpr static int global_flags = Equality<id, t>::global_flags | strip_identities<Equality, id, type_list<ts...>>::global_flags;
135 };
136 
137 template<
138  template<typename, typename> class Equality,
139  typename id
140  EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, ts)
141 >
143 {
144  typedef type_list<> type;
145  constexpr static int global_flags = 0;
146 };
147 
161 template<
162  template<typename, typename> class Multiply,
163  template<typename, typename> class Equality,
164  typename id,
165  typename g,
166  typename current_element,
167  typename elements,
168  bool dont_add_current_element // = false
169 >
171 #ifndef EIGEN_PARSED_BY_DOXYGEN
172  : // recursive inheritance is too difficult for Doxygen
174  Multiply,
175  Equality,
176  id,
177  g,
178  typename Multiply<current_element, g>::type,
179  typename concat<elements, type_list<current_element>>::type,
180  Equality<typename Multiply<current_element, g>::type, id>::value
181  > {};
182 
183 template<
184  template<typename, typename> class Multiply,
185  template<typename, typename> class Equality,
186  typename id,
187  typename g,
188  typename current_element,
189  typename elements
190 >
191 struct dimino_first_step_elements_helper<Multiply, Equality, id, g, current_element, elements, true>
192 #endif // EIGEN_PARSED_BY_DOXYGEN
193 {
194  typedef elements type;
195  constexpr static int global_flags = Equality<current_element, id>::global_flags;
196 };
197 
211 template<
212  template<typename, typename> class Multiply,
213  template<typename, typename> class Equality,
214  typename id,
215  typename generators
216 >
218 {
222 
224  Multiply,
225  Equality,
226  id,
227  first_generator,
228  first_generator,
230  false
232  typedef typename helper::type type;
233  constexpr static int global_flags = helper::global_flags;
234 };
235 
256 template<
257  template<typename, typename> class Multiply,
258  typename sub_group_elements,
259  typename new_coset_rep,
260  bool generate_coset // = true
261 >
263 {
265 };
266 
267 template<
268  template<typename, typename> class Multiply,
269  typename sub_group_elements,
270  typename new_coset_rep
271 >
272 struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false>
273 {
274  typedef type_list<> type;
275 };
276 
291 template<
292  template<typename, typename> class Multiply,
293  template<typename, typename> class Equality,
294  typename id,
295  typename sub_group_elements,
296  typename elements,
297  typename generators,
298  typename rep_element,
299  int sub_group_size
300 >
302 
303 template<
304  template<typename, typename> class Multiply,
305  template<typename, typename> class Equality,
306  typename id,
307  typename sub_group_elements,
308  typename elements,
309  typename g,
310  typename... gs,
311  typename rep_element,
312  int sub_group_size
313 >
314 struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element, sub_group_size>
315 {
318  constexpr static bool add_coset = !_cil::value;
319 
320  typedef typename dimino_get_coset_elements<
321  Multiply,
322  sub_group_elements,
323  new_coset_rep,
324  add_coset
326 
328  Multiply,
329  Equality,
330  id,
331  sub_group_elements,
333  type_list<gs...>,
334  rep_element,
335  sub_group_size
337 
338  typedef typename _helper::type type;
339  constexpr static int global_flags = _cil::global_flags | _helper::global_flags;
340 
341  /* Note that we don't have to update global flags here, since
342  * we will only add these elements if they are not part of
343  * the group already. But that only happens if the coset rep
344  * is not already in the group, so the check for the coset rep
345  * will catch this.
346  */
347 };
348 
349 template<
350  template<typename, typename> class Multiply,
351  template<typename, typename> class Equality,
352  typename id,
353  typename sub_group_elements,
354  typename elements
356  typename rep_element,
357  int sub_group_size
358 >
359 struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(empty)>, rep_element, sub_group_size>
360 {
361  typedef elements type;
362  constexpr static int global_flags = 0;
363 };
364 
379 template<
380  template<typename, typename> class Multiply,
381  template<typename, typename> class Equality,
382  typename id,
383  typename sub_group_elements,
384  typename elements,
385  typename generators,
386  int sub_group_size,
387  int rep_pos,
388  bool stop_condition // = false
389 >
391 {
394  Multiply,
395  Equality,
396  id,
397  sub_group_elements,
398  elements,
399  generators,
400  rep_element,
401  sub_group_elements::count
402  > _ac4r;
403  typedef typename _ac4r::type new_elements;
404 
405  constexpr static int new_rep_pos = rep_pos + sub_group_elements::count;
406  constexpr static bool new_stop_condition = new_rep_pos >= new_elements::count;
407 
409  Multiply,
410  Equality,
411  id,
412  sub_group_elements,
413  new_elements,
414  generators,
415  sub_group_size,
416  new_rep_pos,
417  new_stop_condition
419 
420  typedef typename _helper::type type;
421  constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
422 };
423 
424 template<
425  template<typename, typename> class Multiply,
426  template<typename, typename> class Equality,
427  typename id,
428  typename sub_group_elements,
429  typename elements,
430  typename generators,
431  int sub_group_size,
432  int rep_pos
433 >
434 struct dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, elements, generators, sub_group_size, rep_pos, true>
435 {
436  typedef elements type;
437  constexpr static int global_flags = 0;
438 };
439 
452 template<
453  template<typename, typename> class Multiply,
454  template<typename, typename> class Equality,
455  typename id,
456  typename elements,
457  typename generators_done,
458  typename current_generator,
459  bool redundant // = false
460 >
462 {
463  /* this template is only called if the generator is not redundant
464  * => all elements of the group multiplied with the new generator
465  * are going to be new elements of the most trivial coset space
466  */
469 
470  constexpr static int rep_pos = elements::count;
471 
473  Multiply,
474  Equality,
475  id,
476  elements, // elements of previous subgroup
477  new_elements,
479  elements::count, // size of previous subgroup
480  rep_pos,
481  false // don't stop (because rep_pos >= new_elements::count is always false at this point)
483  typedef typename _helper::type type;
484  constexpr static int global_flags = _helper::global_flags;
485 };
486 
487 template<
488  template<typename, typename> class Multiply,
489  template<typename, typename> class Equality,
490  typename id,
491  typename elements,
492  typename generators_done,
493  typename current_generator
494 >
495 struct dimino_add_generator<Multiply, Equality, id, elements, generators_done, current_generator, true>
496 {
497  // redundant case
498  typedef elements type;
499  constexpr static int global_flags = 0;
500 };
501 
514 template<
515  template<typename, typename> class Multiply,
516  template<typename, typename> class Equality,
517  typename id,
518  typename generators_done,
519  typename remaining_generators,
520  typename elements
521 >
523 {
526 
528 
529  typedef dimino_add_generator<
530  Multiply,
531  Equality,
532  id,
533  elements,
534  generators_done,
535  first_generator,
538 
539  typedef typename _helper::type new_elements;
540 
542  Multiply,
543  Equality,
544  id,
546  next_generators,
547  new_elements
549 
550  typedef typename _next_iter::type type;
551  constexpr static int global_flags =
552  _cil::global_flags |
553  _helper::global_flags |
554  _next_iter::global_flags;
555 };
556 
557 template<
558  template<typename, typename> class Multiply,
559  template<typename, typename> class Equality,
560  typename id,
561  typename generators_done,
562  typename elements
563 >
564 struct dimino_add_remaining_generators<Multiply, Equality, id, generators_done, type_list<>, elements>
565 {
566  typedef elements type;
567  constexpr static int global_flags = 0;
568 };
569 
584 template<
585  template<typename, typename> class Multiply,
586  template<typename, typename> class Equality,
587  typename id,
588  typename generators,
589  int initial_global_flags = 0
590 >
592 {
595 
597  Multiply,
598  Equality,
599  id,
601  typename first_step::next_generators, // remaining_generators
602  typename first_step::type // first_step elements
604 
605  typedef typename _helper::type type;
606  constexpr static int global_flags =
607  initial_global_flags |
608  first_step::global_flags |
609  _helper::global_flags;
610 };
611 
612 // in case when no generators are specified
613 template<
614  template<typename, typename> class Multiply,
615  template<typename, typename> class Equality,
616  typename id,
617  int initial_global_flags
618 >
619 struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags>
620 {
622  constexpr static int global_flags = initial_global_flags;
623 };
624 
642 template<
643  template<typename, typename> class Multiply,
644  template<typename, typename> class Equality,
645  typename id,
646  typename _generators
647 >
650  Multiply,
651  Equality,
652  id,
653  typename strip_identities<Equality, id, _generators>::type,
654  strip_identities<Equality, id, _generators>::global_flags
655  >
656 {
657 };
658 
659 } // end namespace group_theory
660 
661 } // end namespace internal
662 
663 } // end namespace Eigen
664 
665 #endif // EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
666 
667 /*
668  * kate: space-indent on; indent-width 2; mixedindent off; indent-mode cstyle;
669  */
dimino_add_cosets_for_rep< Multiply, Equality, id, sub_group_elements, typename concat< elements, coset_elements >::type, type_list< gs... >, rep_element, sub_group_size > _helper
contained_in_list_gf< Equality, first_generator, elements > _cil
Namespace containing all symbols from the Eigen library.
Definition: jet.h:637
MatrixXd L
Definition: LLT_example.cpp:6
static const Similarity3 id
void g(const string &key, int i)
Definition: testBTree.cpp:41
apply_op_from_right< Multiply, current_generator, elements >::type multiplied_elements
dimino_first_step_elements_helper< Multiply, Equality, id, first_generator, first_generator, type_list< id >, false > helper
conditional< Equality< id, t >::value, typename strip_identities< Equality, id, type_list< ts... > >::type, typename concat< type_list< t >, typename strip_identities< Equality, id, type_list< ts... > >::type >::type >::type type
dimino_add_remaining_generators< Multiply, Equality, id, typename first_step::generators_done, typename first_step::next_generators, typename first_step::type > _helper
dimino_add_cosets_for_rep< Multiply, Equality, id, sub_group_elements, elements, generators, rep_element, sub_group_elements::count > _ac4r
#define EIGEN_TPL_PP_SPEC_HACK_DEFC(mt, n)
concat< elements, multiplied_elements >::type new_elements
dimino_add_generator< Multiply, Equality, id, elements, generators_done, first_generator, _cil::value > _helper
dimino_add_remaining_generators< Multiply, Equality, id, typename concat< generators_done, type_list< first_generator > >::type, next_generators, new_elements > _next_iter
#define EIGEN_TPL_PP_SPEC_HACK_USE(n)
dimino_add_all_coset_spaces< Multiply, Equality, id, sub_group_elements, new_elements, generators, sub_group_size, new_rep_pos, new_stop_condition > _helper
Generic expression where a coefficient-wise unary operator is applied to an expression.
Definition: CwiseUnaryOp.h:55
apply_op_from_right< Multiply, new_coset_rep, sub_group_elements >::type type
dimino_add_all_coset_spaces< Multiply, Equality, id, elements, new_elements, typename concat< generators_done, type_list< current_generator > >::type, elements::count, rep_pos, false > _helper
Point2 t(10, 10)
dimino_first_step_elements< Multiply, Equality, id, generators > first_step


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:36:35