Please, help us to better know about our user community by answering the following short survey: https://forms.gle/wpyrxWi18ox9Z5ae9
 
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
10#ifndef EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
11#define EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
12
13namespace Eigen {
14
15namespace internal {
16
17namespace 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
119template<template<typename, typename> class Equality, typename id, typename L> struct strip_identities;
120
121template<
122 template<typename, typename> class Equality,
123 typename id,
124 typename t,
125 typename... ts
126>
127struct strip_identities<Equality, id, type_list<t, ts...>>
128{
129 typedef typename conditional<
130 Equality<id, t>::value,
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
133 >::type type;
134 constexpr static int global_flags = Equality<id, t>::global_flags | strip_identities<Equality, id, type_list<ts...>>::global_flags;
135};
136
137template<
138 template<typename, typename> class Equality,
139 typename id
140 EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, ts)
141>
142struct strip_identities<Equality, id, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(ts)>>
143{
144 typedef type_list<> type;
145 constexpr static int global_flags = 0;
146};
147
161template<
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>
170struct dimino_first_step_elements_helper
171#ifndef EIGEN_PARSED_BY_DOXYGEN
172 : // recursive inheritance is too difficult for Doxygen
173 public dimino_first_step_elements_helper<
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
183template<
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>
191struct 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
211template<
212 template<typename, typename> class Multiply,
213 template<typename, typename> class Equality,
214 typename id,
215 typename generators
216>
217struct dimino_first_step_elements
218{
219 typedef typename get<0, generators>::type first_generator;
220 typedef typename skip<1, generators>::type next_generators;
221 typedef type_list<first_generator> generators_done;
222
223 typedef dimino_first_step_elements_helper<
224 Multiply,
225 Equality,
226 id,
227 first_generator,
228 first_generator,
229 type_list<id>,
230 false
231 > helper;
232 typedef typename helper::type type;
233 constexpr static int global_flags = helper::global_flags;
234};
235
256template<
257 template<typename, typename> class Multiply,
258 typename sub_group_elements,
259 typename new_coset_rep,
260 bool generate_coset // = true
261>
262struct dimino_get_coset_elements
263{
264 typedef typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type type;
265};
266
267template<
268 template<typename, typename> class Multiply,
269 typename sub_group_elements,
270 typename new_coset_rep
271>
272struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false>
273{
274 typedef type_list<> type;
275};
276
291template<
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>
301struct dimino_add_cosets_for_rep;
302
303template<
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>
314struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element, sub_group_size>
315{
316 typedef typename Multiply<rep_element, g>::type new_coset_rep;
317 typedef contained_in_list_gf<Equality, new_coset_rep, elements> _cil;
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
325 >::type coset_elements;
326
327 typedef dimino_add_cosets_for_rep<
328 Multiply,
329 Equality,
330 id,
331 sub_group_elements,
332 typename concat<elements, coset_elements>::type,
333 type_list<gs...>,
334 rep_element,
335 sub_group_size
336 > _helper;
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
349template<
350 template<typename, typename> class Multiply,
351 template<typename, typename> class Equality,
352 typename id,
353 typename sub_group_elements,
354 typename elements
355 EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
356 typename rep_element,
357 int sub_group_size
358>
359struct 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
379template<
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>
390struct dimino_add_all_coset_spaces
391{
392 typedef typename get<rep_pos, elements>::type rep_element;
393 typedef dimino_add_cosets_for_rep<
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
408 typedef dimino_add_all_coset_spaces<
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
418 > _helper;
419
420 typedef typename _helper::type type;
421 constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
422};
423
424template<
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>
434struct 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
452template<
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>
461struct dimino_add_generator
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 */
467 typedef typename apply_op_from_right<Multiply, current_generator, elements>::type multiplied_elements;
468 typedef typename concat<elements, multiplied_elements>::type new_elements;
469
470 constexpr static int rep_pos = elements::count;
471
472 typedef dimino_add_all_coset_spaces<
473 Multiply,
474 Equality,
475 id,
476 elements, // elements of previous subgroup
477 new_elements,
478 typename concat<generators_done, type_list<current_generator>>::type,
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)
482 > _helper;
483 typedef typename _helper::type type;
484 constexpr static int global_flags = _helper::global_flags;
485};
486
487template<
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>
495struct 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
514template<
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>
522struct dimino_add_remaining_generators
523{
524 typedef typename get<0, remaining_generators>::type first_generator;
525 typedef typename skip<1, remaining_generators>::type next_generators;
526
527 typedef contained_in_list_gf<Equality, first_generator, elements> _cil;
528
529 typedef dimino_add_generator<
530 Multiply,
531 Equality,
532 id,
533 elements,
534 generators_done,
535 first_generator,
536 _cil::value
537 > _helper;
538
539 typedef typename _helper::type new_elements;
540
541 typedef dimino_add_remaining_generators<
542 Multiply,
543 Equality,
544 id,
545 typename concat<generators_done, type_list<first_generator>>::type,
546 next_generators,
547 new_elements
548 > _next_iter;
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
557template<
558 template<typename, typename> class Multiply,
559 template<typename, typename> class Equality,
560 typename id,
561 typename generators_done,
562 typename elements
563>
564struct 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
584template<
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>
591struct enumerate_group_elements_noid
592{
593 typedef dimino_first_step_elements<Multiply, Equality, id, generators> first_step;
594 typedef typename first_step::type first_step_elements;
595
596 typedef dimino_add_remaining_generators<
597 Multiply,
598 Equality,
599 id,
600 typename first_step::generators_done,
601 typename first_step::next_generators, // remaining_generators
602 typename first_step::type // first_step elements
603 > _helper;
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
613template<
614 template<typename, typename> class Multiply,
615 template<typename, typename> class Equality,
616 typename id,
617 int initial_global_flags
618>
619struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags>
620{
621 typedef type_list<id> type;
622 constexpr static int global_flags = initial_global_flags;
623};
624
642template<
643 template<typename, typename> class Multiply,
644 template<typename, typename> class Equality,
645 typename id,
646 typename _generators
647>
648struct enumerate_group_elements
649 : public enumerate_group_elements_noid<
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 */
Namespace containing all symbols from the Eigen library.