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/src/TensorSymmetry/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 #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 
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 
198 /** \internal
199   *
200   * \class dimino_first_step_elements
201   * \ingroup CXX11_TensorSymmetry_Module
202   *
203   * \brief Add all powers of the first generator to the list of group elements
204   *
205   * This template takes the first non-identity generator and generates the initial
206   * list of elements which consists of all powers of that generator. For a group
207   * with just one generated, it would be enumerated after this.
208   *
209   * \sa enumerate_group_elements
210   */
211 template<
212   template<typename, typename> class Multiply,
213   template<typename, typename> class Equality,
214   typename id,
215   typename generators
216 >
217 struct 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 
236 /** \internal
237   *
238   * \class dimino_get_coset_elements
239   * \ingroup CXX11_TensorSymmetry_Module
240   *
241   * \brief Generate all elements of a specific coset
242   *
243   * This template generates all the elements of a specific coset by
244   * multiplying all elements in the given subgroup with the new
245   * coset representative. Note that the first element of the
246   * subgroup is always the identity element, so the first element of
247   * ther result of this template is going to be the coset
248   * representative itself.
249   *
250   * Note that this template accepts an additional boolean parameter
251   * that specifies whether to actually generate the coset (true) or
252   * just return an empty list (false).
253   *
254   * \sa enumerate_group_elements, dimino_add_cosets_for_rep
255   */
256 template<
257   template<typename, typename> class Multiply,
258   typename sub_group_elements,
259   typename new_coset_rep,
260   bool generate_coset      // = true
261 >
262 struct dimino_get_coset_elements
263 {
264   typedef typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type type;
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 
277 /** \internal
278   *
279   * \class dimino_add_cosets_for_rep
280   * \ingroup CXX11_TensorSymmetry_Module
281   *
282   * \brief Recursive template for adding coset spaces
283   *
284   * This template multiplies the coset representative with a generator
285   * from the list of previous generators. If the new element is not in
286   * the group already, it adds the corresponding coset. Finally it
287   * proceeds to call itself with the next generator from the list.
288   *
289   * \sa enumerate_group_elements, dimino_add_all_coset_spaces
290   */
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 >
301 struct dimino_add_cosets_for_rep;
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 {
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 
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
355   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
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 
365 /** \internal
366   *
367   * \class dimino_add_all_coset_spaces
368   * \ingroup CXX11_TensorSymmetry_Module
369   *
370   * \brief Recursive template for adding all coset spaces for a new generator
371   *
372   * This template tries to go through the list of generators (with
373   * the help of the dimino_add_cosets_for_rep template) as long as
374   * it still finds elements that are not part of the group and add
375   * the corresponding cosets.
376   *
377   * \sa enumerate_group_elements, dimino_add_cosets_for_rep
378   */
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 >
390 struct 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 
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 
440 /** \internal
441   *
442   * \class dimino_add_generator
443   * \ingroup CXX11_TensorSymmetry_Module
444   *
445   * \brief Enlarge the group by adding a new generator.
446   *
447   * It accepts a boolean parameter that determines if the generator is redundant,
448   * i.e. was already seen in the group. In that case, it reduces to a no-op.
449   *
450   * \sa enumerate_group_elements, dimino_add_all_coset_spaces
451   */
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 >
461 struct 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 
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 
502 /** \internal
503   *
504   * \class dimino_add_remaining_generators
505   * \ingroup CXX11_TensorSymmetry_Module
506   *
507   * \brief Recursive template that adds all remaining generators to a group
508   *
509   * Loop through the list of generators that remain and successively
510   * add them to the group.
511   *
512   * \sa enumerate_group_elements, dimino_add_generator
513   */
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 >
522 struct 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 
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 
570 /** \internal
571   *
572   * \class enumerate_group_elements_noid
573   * \ingroup CXX11_TensorSymmetry_Module
574   *
575   * \brief Helper template that implements group element enumeration
576   *
577   * This is a helper template that implements the actual enumeration
578   * of group elements. This has been split so that the list of
579   * generators can be cleansed of the identity element before
580   * performing the actual operation.
581   *
582   * \sa enumerate_group_elements
583   */
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 >
591 struct 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
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 {
621   typedef type_list<id> type;
622   constexpr static int global_flags = initial_global_flags;
623 };
624 
625 /** \internal
626   *
627   * \class enumerate_group_elements
628   * \ingroup CXX11_TensorSymmetry_Module
629   *
630   * \brief Enumerate all elements in a finite group
631   *
632   * This template enumerates all elements in a finite group. It accepts
633   * the following template parameters:
634   *
635   * \tparam Multiply      The multiplication operation that multiplies two group elements
636   *                       with each other.
637   * \tparam Equality      The equality check operation that checks if two group elements
638   *                       are equal to another.
639   * \tparam id            The identity element
640   * \tparam _generators   A list of (possibly redundant) generators of the group
641   */
642 template<
643   template<typename, typename> class Multiply,
644   template<typename, typename> class Equality,
645   typename id,
646   typename _generators
647 >
648 struct 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  */
670