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 
19 /** \internal
20   * \file CXX11/Tensor/util/TemplateGroupTheory.h
21   * This file contains C++ templates that implement group theory algorithms.
22   *
23   * The algorithms allow for a compile-time analysis of finite groups.
24   *
25   * Currently only Dimino's algorithm is implemented, which returns a list
26   * of all elements in a group given a set of (possibly redundant) generators.
27   * (One could also do that with the so-called orbital algorithm, but that
28   * is much more expensive and usually has no advantages.)
29   */
30 
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 
106 /** \internal
107   *
108   * \class strip_identities
109   * \ingroup CXX11_TensorSymmetry_Module
110   *
111   * \brief Cleanse a list of group elements of the identity element
112   *
113   * This template is used to make a first pass through all initial
114   * generators of Dimino's algorithm and remove the identity
115   * elements.
116   *
117   * \sa enumerate_group_elements
118   */
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<
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 
137 template<
138   template<typename, typename> class Equality,
139   typename id
140   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, ts)
141 >
142 struct 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 
148 /** \internal
149   *
150   * \class dimino_first_step_elements_helper
151   * \ingroup CXX11_TensorSymmetry_Module
152   *
153   * \brief Recursive template that adds powers of the first generator to the list of group elements
154   *
155   * This template calls itself recursively to add powers of the first
156   * generator to the list of group elements. It stops if it reaches
157   * the identity element again.
158   *
159   * \sa enumerate_group_elements, dimino_first_step_elements
160   */
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 >
170 struct dimino_first_step_elements_helper :
171   public dimino_first_step_elements_helper<
172     Multiply,
173     Equality,
174     id,
175     g,
176     typename Multiply<current_element, g>::type,
177     typename concat<elements, type_list<current_element>>::type,
178     Equality<typename Multiply<current_element, g>::type, id>::value
179   > {};
180 
181 template<
182   template<typename, typename> class Multiply,
183   template<typename, typename> class Equality,
184   typename id,
185   typename g,
186   typename current_element,
187   typename elements
188 >
189 struct dimino_first_step_elements_helper<Multiply, Equality, id, g, current_element, elements, true>
190 {
191   typedef elements type;
192   constexpr static int global_flags = Equality<current_element, id>::global_flags;
193 };
194 
195 /** \internal
196   *
197   * \class dimino_first_step_elements
198   * \ingroup CXX11_TensorSymmetry_Module
199   *
200   * \brief Add all powers of the first generator to the list of group elements
201   *
202   * This template takes the first non-identity generator and generates the initial
203   * list of elements which consists of all powers of that generator. For a group
204   * with just one generated, it would be enumerated after this.
205   *
206   * \sa enumerate_group_elements
207   */
208 template<
209   template<typename, typename> class Multiply,
210   template<typename, typename> class Equality,
211   typename id,
212   typename generators
213 >
214 struct dimino_first_step_elements
215 {
216   typedef typename get<0, generators>::type first_generator;
217   typedef typename skip<1, generators>::type next_generators;
218   typedef type_list<first_generator> generators_done;
219 
220   typedef dimino_first_step_elements_helper<
221     Multiply,
222     Equality,
223     id,
224     first_generator,
225     first_generator,
226     type_list<id>,
227     false
228   > helper;
229   typedef typename helper::type type;
230   constexpr static int global_flags = helper::global_flags;
231 };
232 
233 /** \internal
234   *
235   * \class dimino_get_coset_elements
236   * \ingroup CXX11_TensorSymmetry_Module
237   *
238   * \brief Generate all elements of a specific coset
239   *
240   * This template generates all the elements of a specific coset by
241   * multiplying all elements in the given subgroup with the new
242   * coset representative. Note that the first element of the
243   * subgroup is always the identity element, so the first element of
244   * ther result of this template is going to be the coset
245   * representative itself.
246   *
247   * Note that this template accepts an additional boolean parameter
248   * that specifies whether to actually generate the coset (true) or
249   * just return an empty list (false).
250   *
251   * \sa enumerate_group_elements, dimino_add_cosets_for_rep
252   */
253 template<
254   template<typename, typename> class Multiply,
255   typename sub_group_elements,
256   typename new_coset_rep,
257   bool generate_coset      // = true
258 >
259 struct dimino_get_coset_elements
260 {
261   typedef typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type type;
262 };
263 
264 template<
265   template<typename, typename> class Multiply,
266   typename sub_group_elements,
267   typename new_coset_rep
268 >
269 struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false>
270 {
271   typedef type_list<> type;
272 };
273 
274 /** \internal
275   *
276   * \class dimino_add_cosets_for_rep
277   * \ingroup CXX11_TensorSymmetry_Module
278   *
279   * \brief Recursive template for adding coset spaces
280   *
281   * This template multiplies the coset representative with a generator
282   * from the list of previous generators. If the new element is not in
283   * the group already, it adds the corresponding coset. Finally it
284   * proceeds to call itself with the next generator from the list.
285   *
286   * \sa enumerate_group_elements, dimino_add_all_coset_spaces
287   */
288 template<
289   template<typename, typename> class Multiply,
290   template<typename, typename> class Equality,
291   typename id,
292   typename sub_group_elements,
293   typename elements,
294   typename generators,
295   typename rep_element,
296   int sub_group_size
297 >
298 struct dimino_add_cosets_for_rep;
299 
300 template<
301   template<typename, typename> class Multiply,
302   template<typename, typename> class Equality,
303   typename id,
304   typename sub_group_elements,
305   typename elements,
306   typename g,
307   typename... gs,
308   typename rep_element,
309   int sub_group_size
310 >
311 struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element, sub_group_size>
312 {
313   typedef typename Multiply<rep_element, g>::type new_coset_rep;
314   typedef contained_in_list_gf<Equality, new_coset_rep, elements> _cil;
315   constexpr static bool add_coset = !_cil::value;
316 
317   typedef typename dimino_get_coset_elements<
318     Multiply,
319     sub_group_elements,
320     new_coset_rep,
321     add_coset
322   >::type coset_elements;
323 
324   typedef dimino_add_cosets_for_rep<
325     Multiply,
326     Equality,
327     id,
328     sub_group_elements,
329     typename concat<elements, coset_elements>::type,
330     type_list<gs...>,
331     rep_element,
332     sub_group_size
333   > _helper;
334 
335   typedef typename _helper::type type;
336   constexpr static int global_flags = _cil::global_flags | _helper::global_flags;
337 
338   /* Note that we don't have to update global flags here, since
339    * we will only add these elements if they are not part of
340    * the group already. But that only happens if the coset rep
341    * is not already in the group, so the check for the coset rep
342    * will catch this.
343    */
344 };
345 
346 template<
347   template<typename, typename> class Multiply,
348   template<typename, typename> class Equality,
349   typename id,
350   typename sub_group_elements,
351   typename elements
352   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
353   typename rep_element,
354   int sub_group_size
355 >
356 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>
357 {
358   typedef elements type;
359   constexpr static int global_flags = 0;
360 };
361 
362 /** \internal
363   *
364   * \class dimino_add_all_coset_spaces
365   * \ingroup CXX11_TensorSymmetry_Module
366   *
367   * \brief Recursive template for adding all coset spaces for a new generator
368   *
369   * This template tries to go through the list of generators (with
370   * the help of the dimino_add_cosets_for_rep template) as long as
371   * it still finds elements that are not part of the group and add
372   * the corresponding cosets.
373   *
374   * \sa enumerate_group_elements, dimino_add_cosets_for_rep
375   */
376 template<
377   template<typename, typename> class Multiply,
378   template<typename, typename> class Equality,
379   typename id,
380   typename sub_group_elements,
381   typename elements,
382   typename generators,
383   int sub_group_size,
384   int rep_pos,
385   bool stop_condition        // = false
386 >
387 struct dimino_add_all_coset_spaces
388 {
389   typedef typename get<rep_pos, elements>::type rep_element;
390   typedef dimino_add_cosets_for_rep<
391     Multiply,
392     Equality,
393     id,
394     sub_group_elements,
395     elements,
396     generators,
397     rep_element,
398     sub_group_elements::count
399   > _ac4r;
400   typedef typename _ac4r::type new_elements;
401 
402   constexpr static int new_rep_pos = rep_pos + sub_group_elements::count;
403   constexpr static bool new_stop_condition = new_rep_pos >= new_elements::count;
404 
405   typedef dimino_add_all_coset_spaces<
406     Multiply,
407     Equality,
408     id,
409     sub_group_elements,
410     new_elements,
411     generators,
412     sub_group_size,
413     new_rep_pos,
414     new_stop_condition
415   > _helper;
416 
417   typedef typename _helper::type type;
418   constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
419 };
420 
421 template<
422   template<typename, typename> class Multiply,
423   template<typename, typename> class Equality,
424   typename id,
425   typename sub_group_elements,
426   typename elements,
427   typename generators,
428   int sub_group_size,
429   int rep_pos
430 >
431 struct dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, elements, generators, sub_group_size, rep_pos, true>
432 {
433   typedef elements type;
434   constexpr static int global_flags = 0;
435 };
436 
437 /** \internal
438   *
439   * \class dimino_add_generator
440   * \ingroup CXX11_TensorSymmetry_Module
441   *
442   * \brief Enlarge the group by adding a new generator.
443   *
444   * It accepts a boolean parameter that determines if the generator is redundant,
445   * i.e. was already seen in the group. In that case, it reduces to a no-op.
446   *
447   * \sa enumerate_group_elements, dimino_add_all_coset_spaces
448   */
449 template<
450   template<typename, typename> class Multiply,
451   template<typename, typename> class Equality,
452   typename id,
453   typename elements,
454   typename generators_done,
455   typename current_generator,
456   bool redundant          // = false
457 >
458 struct dimino_add_generator
459 {
460   /* this template is only called if the generator is not redundant
461    * => all elements of the group multiplied with the new generator
462    *    are going to be new elements of the most trivial coset space
463    */
464   typedef typename apply_op_from_right<Multiply, current_generator, elements>::type multiplied_elements;
465   typedef typename concat<elements, multiplied_elements>::type new_elements;
466 
467   constexpr static int rep_pos = elements::count;
468 
469   typedef dimino_add_all_coset_spaces<
470     Multiply,
471     Equality,
472     id,
473     elements, // elements of previous subgroup
474     new_elements,
475     typename concat<generators_done, type_list<current_generator>>::type,
476     elements::count, // size of previous subgroup
477     rep_pos,
478     false // don't stop (because rep_pos >= new_elements::count is always false at this point)
479   > _helper;
480   typedef typename _helper::type type;
481   constexpr static int global_flags = _helper::global_flags;
482 };
483 
484 template<
485   template<typename, typename> class Multiply,
486   template<typename, typename> class Equality,
487   typename id,
488   typename elements,
489   typename generators_done,
490   typename current_generator
491 >
492 struct dimino_add_generator<Multiply, Equality, id, elements, generators_done, current_generator, true>
493 {
494   // redundant case
495   typedef elements type;
496   constexpr static int global_flags = 0;
497 };
498 
499 /** \internal
500   *
501   * \class dimino_add_remaining_generators
502   * \ingroup CXX11_TensorSymmetry_Module
503   *
504   * \brief Recursive template that adds all remaining generators to a group
505   *
506   * Loop through the list of generators that remain and successively
507   * add them to the group.
508   *
509   * \sa enumerate_group_elements, dimino_add_generator
510   */
511 template<
512   template<typename, typename> class Multiply,
513   template<typename, typename> class Equality,
514   typename id,
515   typename generators_done,
516   typename remaining_generators,
517   typename elements
518 >
519 struct dimino_add_remaining_generators
520 {
521   typedef typename get<0, remaining_generators>::type first_generator;
522   typedef typename skip<1, remaining_generators>::type next_generators;
523 
524   typedef contained_in_list_gf<Equality, first_generator, elements> _cil;
525 
526   typedef dimino_add_generator<
527     Multiply,
528     Equality,
529     id,
530     elements,
531     generators_done,
532     first_generator,
533     _cil::value
534   > _helper;
535 
536   typedef typename _helper::type new_elements;
537 
538   typedef dimino_add_remaining_generators<
539     Multiply,
540     Equality,
541     id,
542     typename concat<generators_done, type_list<first_generator>>::type,
543     next_generators,
544     new_elements
545   > _next_iter;
546 
547   typedef typename _next_iter::type type;
548   constexpr static int global_flags =
549     _cil::global_flags |
550     _helper::global_flags |
551     _next_iter::global_flags;
552 };
553 
554 template<
555   template<typename, typename> class Multiply,
556   template<typename, typename> class Equality,
557   typename id,
558   typename generators_done,
559   typename elements
560 >
561 struct dimino_add_remaining_generators<Multiply, Equality, id, generators_done, type_list<>, elements>
562 {
563   typedef elements type;
564   constexpr static int global_flags = 0;
565 };
566 
567 /** \internal
568   *
569   * \class enumerate_group_elements_noid
570   * \ingroup CXX11_TensorSymmetry_Module
571   *
572   * \brief Helper template that implements group element enumeration
573   *
574   * This is a helper template that implements the actual enumeration
575   * of group elements. This has been split so that the list of
576   * generators can be cleansed of the identity element before
577   * performing the actual operation.
578   *
579   * \sa enumerate_group_elements
580   */
581 template<
582   template<typename, typename> class Multiply,
583   template<typename, typename> class Equality,
584   typename id,
585   typename generators,
586   int initial_global_flags = 0
587 >
588 struct enumerate_group_elements_noid
589 {
590   typedef dimino_first_step_elements<Multiply, Equality, id, generators> first_step;
591   typedef typename first_step::type first_step_elements;
592 
593   typedef dimino_add_remaining_generators<
594     Multiply,
595     Equality,
596     id,
597     typename first_step::generators_done,
598     typename first_step::next_generators, // remaining_generators
599     typename first_step::type // first_step elements
600   > _helper;
601 
602   typedef typename _helper::type type;
603   constexpr static int global_flags =
604     initial_global_flags |
605     first_step::global_flags |
606     _helper::global_flags;
607 };
608 
609 // in case when no generators are specified
610 template<
611   template<typename, typename> class Multiply,
612   template<typename, typename> class Equality,
613   typename id,
614   int initial_global_flags
615 >
616 struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags>
617 {
618   typedef type_list<id> type;
619   constexpr static int global_flags = initial_global_flags;
620 };
621 
622 /** \internal
623   *
624   * \class enumerate_group_elements
625   * \ingroup CXX11_TensorSymmetry_Module
626   *
627   * \brief Enumerate all elements in a finite group
628   *
629   * This template enumerates all elements in a finite group. It accepts
630   * the following template parameters:
631   *
632   * \tparam Multiply      The multiplication operation that multiplies two group elements
633   *                       with each other.
634   * \tparam Equality      The equality check operation that checks if two group elements
635   *                       are equal to another.
636   * \tparam id            The identity element
637   * \tparam _generators   A list of (possibly redundant) generators of the group
638   */
639 template<
640   template<typename, typename> class Multiply,
641   template<typename, typename> class Equality,
642   typename id,
643   typename _generators
644 >
645 struct enumerate_group_elements
646   : public enumerate_group_elements_noid<
647       Multiply,
648       Equality,
649       id,
650       typename strip_identities<Equality, id, _generators>::type,
651       strip_identities<Equality, id, _generators>::global_flags
652     >
653 {
654 };
655 
656 } // end namespace group_theory
657 
658 } // end namespace internal
659 
660 } // end namespace Eigen
661 
662 #endif // EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
663 
664 /*
665  * kate: space-indent on; indent-width 2; mixedindent off; indent-mode cstyle;
666  */
667