TemplateGroupTheory.h
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2013 Christian Seiler <christian@iwakd.de>
00005 //
00006 // This Source Code Form is subject to the terms of the Mozilla
00007 // Public License v. 2.0. If a copy of the MPL was not distributed
00008 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
00009 
00010 #ifndef EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
00011 #define EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
00012 
00013 namespace Eigen {
00014 
00015 namespace internal {
00016 
00017 namespace group_theory {
00018 
00031 /**********************************************************************
00032  *                "Ok kid, here is where it gets complicated."
00033  *                         - Amelia Pond in the "Doctor Who" episode
00034  *                           "The Big Bang"
00035  *
00036  * Dimino's algorithm
00037  * ==================
00038  *
00039  * The following is Dimino's algorithm in sequential form:
00040  *
00041  * Input: identity element, list of generators, equality check,
00042  *        multiplication operation
00043  * Output: list of group elements
00044  *
00045  * 1. add identity element
00046  * 2. remove identities from list of generators
00047  * 3. add all powers of first generator that aren't the
00048  *    identity element
00049  * 4. go through all remaining generators:
00050  *        a. if generator is already in the list of elements
00051  *                -> do nothing
00052  *        b. otherwise
00053  *                i.   remember current # of elements
00054  *                     (i.e. the size of the current subgroup)
00055  *                ii.  add all current elements (which includes
00056  *                     the identity) each multiplied from right
00057  *                     with the current generator to the group
00058  *                iii. add all remaining cosets that are generated
00059  *                     by products of the new generator with itself
00060  *                     and all other generators seen so far
00061  *
00062  * In functional form, this is implemented as a long set of recursive
00063  * templates that have a complicated relationship.
00064  *
00065  * The main interface for Dimino's algorithm is the template
00066  * enumerate_group_elements. All lists are implemented as variadic
00067  * type_list<typename...> and numeric_list<typename = int, int...>
00068  * templates.
00069  *
00070  * 'Calling' templates is usually done via typedefs.
00071  *
00072  * This algorithm is an extended version of the basic version. The
00073  * extension consists in the fact that each group element has a set
00074  * of flags associated with it. Multiplication of two group elements
00075  * with each other results in a group element whose flags are the
00076  * XOR of the flags of the previous elements. Each time the algorithm
00077  * notices that a group element it just calculated is already in the
00078  * list of current elements, the flags of both will be compared and
00079  * added to the so-called 'global flags' of the group.
00080  *
00081  * The rationale behind this extension is that this allows not only
00082  * for the description of symmetries between tensor indices, but
00083  * also allows for the description of hermiticity, antisymmetry and
00084  * antihermiticity. Negation and conjugation each are specific bit
00085  * in the flags value and if two different ways to reach a group
00086  * element lead to two different flags, this poses a constraint on
00087  * the allowed values of the resulting tensor. For example, if a
00088  * group element is reach both with and without the conjugation
00089  * flags, it is clear that the resulting tensor has to be real.
00090  *
00091  * Note that this flag mechanism is quite generic and may have other
00092  * uses beyond tensor properties.
00093  *
00094  * IMPORTANT: 
00095  *     This algorithm assumes the group to be finite. If you try to
00096  *     run it with a group that's infinite, the algorithm will only
00097  *     terminate once you hit a compiler limit (max template depth).
00098  *     Also note that trying to use this implementation to create a
00099  *     very large group will probably either make you hit the same
00100  *     limit, cause the compiler to segfault or at the very least
00101  *     take a *really* long time (hours, days, weeks - sic!) to
00102  *     compile. It is not recommended to plug in more than 4
00103  *     generators, unless they are independent of each other.
00104  */
00105 
00119 template<template<typename, typename> class Equality, typename id, typename L> struct strip_identities;
00120 
00121 template<
00122   template<typename, typename> class Equality,
00123   typename id,
00124   typename t,
00125   typename... ts
00126 >
00127 struct strip_identities<Equality, id, type_list<t, ts...>>
00128 {
00129   typedef typename conditional<
00130     Equality<id, t>::value,
00131     typename strip_identities<Equality, id, type_list<ts...>>::type,
00132     typename concat<type_list<t>, typename strip_identities<Equality, id, type_list<ts...>>::type>::type
00133   >::type type;
00134   constexpr static int global_flags = Equality<id, t>::global_flags | strip_identities<Equality, id, type_list<ts...>>::global_flags;
00135 };
00136 
00137 template<
00138   template<typename, typename> class Equality,
00139   typename id
00140   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, ts)
00141 >
00142 struct strip_identities<Equality, id, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(ts)>>
00143 {
00144   typedef type_list<> type;
00145   constexpr static int global_flags = 0;
00146 };
00147 
00161 template<
00162   template<typename, typename> class Multiply,
00163   template<typename, typename> class Equality,
00164   typename id,
00165   typename g,
00166   typename current_element,
00167   typename elements,
00168   bool dont_add_current_element   // = false
00169 >
00170 struct dimino_first_step_elements_helper :
00171   public dimino_first_step_elements_helper<
00172     Multiply,
00173     Equality,
00174     id,
00175     g,
00176     typename Multiply<current_element, g>::type,
00177     typename concat<elements, type_list<current_element>>::type,
00178     Equality<typename Multiply<current_element, g>::type, id>::value
00179   > {};
00180 
00181 template<
00182   template<typename, typename> class Multiply,
00183   template<typename, typename> class Equality,
00184   typename id,
00185   typename g,
00186   typename current_element,
00187   typename elements
00188 >
00189 struct dimino_first_step_elements_helper<Multiply, Equality, id, g, current_element, elements, true>
00190 {
00191   typedef elements type;
00192   constexpr static int global_flags = Equality<current_element, id>::global_flags;
00193 };
00194 
00208 template<
00209   template<typename, typename> class Multiply,
00210   template<typename, typename> class Equality,
00211   typename id,
00212   typename generators
00213 >
00214 struct dimino_first_step_elements
00215 {
00216   typedef typename get<0, generators>::type first_generator;
00217   typedef typename skip<1, generators>::type next_generators;
00218   typedef type_list<first_generator> generators_done;
00219 
00220   typedef dimino_first_step_elements_helper<
00221     Multiply,
00222     Equality,
00223     id,
00224     first_generator,
00225     first_generator,
00226     type_list<id>,
00227     false
00228   > helper;
00229   typedef typename helper::type type;
00230   constexpr static int global_flags = helper::global_flags;
00231 };
00232 
00253 template<
00254   template<typename, typename> class Multiply,
00255   typename sub_group_elements,
00256   typename new_coset_rep,
00257   bool generate_coset      // = true
00258 >
00259 struct dimino_get_coset_elements
00260 {
00261   typedef typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type type;
00262 };
00263 
00264 template<
00265   template<typename, typename> class Multiply,
00266   typename sub_group_elements,
00267   typename new_coset_rep
00268 >
00269 struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false>
00270 {
00271   typedef type_list<> type;
00272 };
00273 
00288 template<
00289   template<typename, typename> class Multiply,
00290   template<typename, typename> class Equality,
00291   typename id,
00292   typename sub_group_elements,
00293   typename elements,
00294   typename generators,
00295   typename rep_element,
00296   int sub_group_size
00297 >
00298 struct dimino_add_cosets_for_rep;
00299 
00300 template<
00301   template<typename, typename> class Multiply,
00302   template<typename, typename> class Equality,
00303   typename id,
00304   typename sub_group_elements,
00305   typename elements,
00306   typename g,
00307   typename... gs,
00308   typename rep_element,
00309   int sub_group_size
00310 >
00311 struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element, sub_group_size>
00312 {
00313   typedef typename Multiply<rep_element, g>::type new_coset_rep;
00314   typedef contained_in_list_gf<Equality, new_coset_rep, elements> _cil;
00315   constexpr static bool add_coset = !_cil::value;
00316 
00317   typedef typename dimino_get_coset_elements<
00318     Multiply,
00319     sub_group_elements,
00320     new_coset_rep,
00321     add_coset
00322   >::type coset_elements;
00323 
00324   typedef dimino_add_cosets_for_rep<
00325     Multiply,
00326     Equality,
00327     id,
00328     sub_group_elements,
00329     typename concat<elements, coset_elements>::type,
00330     type_list<gs...>,
00331     rep_element,
00332     sub_group_size
00333   > _helper;
00334 
00335   typedef typename _helper::type type;
00336   constexpr static int global_flags = _cil::global_flags | _helper::global_flags;
00337 
00338   /* Note that we don't have to update global flags here, since
00339    * we will only add these elements if they are not part of
00340    * the group already. But that only happens if the coset rep
00341    * is not already in the group, so the check for the coset rep
00342    * will catch this.
00343    */
00344 };
00345 
00346 template<
00347   template<typename, typename> class Multiply,
00348   template<typename, typename> class Equality,
00349   typename id,
00350   typename sub_group_elements,
00351   typename elements
00352   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
00353   typename rep_element,
00354   int sub_group_size
00355 >
00356 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>
00357 {
00358   typedef elements type;
00359   constexpr static int global_flags = 0;
00360 };
00361 
00376 template<
00377   template<typename, typename> class Multiply,
00378   template<typename, typename> class Equality,
00379   typename id,
00380   typename sub_group_elements,
00381   typename elements,
00382   typename generators,
00383   int sub_group_size,
00384   int rep_pos,
00385   bool stop_condition        // = false
00386 >
00387 struct dimino_add_all_coset_spaces
00388 {
00389   typedef typename get<rep_pos, elements>::type rep_element;
00390   typedef dimino_add_cosets_for_rep<
00391     Multiply,
00392     Equality,
00393     id,
00394     sub_group_elements,
00395     elements,
00396     generators,
00397     rep_element,
00398     sub_group_elements::count
00399   > _ac4r;
00400   typedef typename _ac4r::type new_elements;
00401   
00402   constexpr static int new_rep_pos = rep_pos + sub_group_elements::count;
00403   constexpr static bool new_stop_condition = new_rep_pos >= new_elements::count;
00404 
00405   typedef dimino_add_all_coset_spaces<
00406     Multiply,
00407     Equality,
00408     id,
00409     sub_group_elements,
00410     new_elements,
00411     generators,
00412     sub_group_size,
00413     new_rep_pos,
00414     new_stop_condition
00415   > _helper;
00416 
00417   typedef typename _helper::type type;
00418   constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
00419 };
00420 
00421 template<
00422   template<typename, typename> class Multiply,
00423   template<typename, typename> class Equality,
00424   typename id,
00425   typename sub_group_elements,
00426   typename elements,
00427   typename generators,
00428   int sub_group_size,
00429   int rep_pos
00430 >
00431 struct dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, elements, generators, sub_group_size, rep_pos, true>
00432 {
00433   typedef elements type;
00434   constexpr static int global_flags = 0;
00435 };
00436 
00449 template<
00450   template<typename, typename> class Multiply,
00451   template<typename, typename> class Equality,
00452   typename id,
00453   typename elements,
00454   typename generators_done,
00455   typename current_generator,
00456   bool redundant          // = false
00457 >
00458 struct dimino_add_generator
00459 {
00460   /* this template is only called if the generator is not redundant
00461    * => all elements of the group multiplied with the new generator
00462    *    are going to be new elements of the most trivial coset space
00463    */
00464   typedef typename apply_op_from_right<Multiply, current_generator, elements>::type multiplied_elements;
00465   typedef typename concat<elements, multiplied_elements>::type new_elements;
00466 
00467   constexpr static int rep_pos = elements::count;
00468 
00469   typedef dimino_add_all_coset_spaces<
00470     Multiply,
00471     Equality,
00472     id,
00473     elements, // elements of previous subgroup
00474     new_elements,
00475     typename concat<generators_done, type_list<current_generator>>::type,
00476     elements::count, // size of previous subgroup
00477     rep_pos,
00478     false // don't stop (because rep_pos >= new_elements::count is always false at this point)
00479   > _helper;
00480   typedef typename _helper::type type;
00481   constexpr static int global_flags = _helper::global_flags;
00482 };
00483 
00484 template<
00485   template<typename, typename> class Multiply,
00486   template<typename, typename> class Equality,
00487   typename id,
00488   typename elements,
00489   typename generators_done,
00490   typename current_generator
00491 >
00492 struct dimino_add_generator<Multiply, Equality, id, elements, generators_done, current_generator, true>
00493 {
00494   // redundant case
00495   typedef elements type;
00496   constexpr static int global_flags = 0;
00497 };
00498 
00511 template<
00512   template<typename, typename> class Multiply,
00513   template<typename, typename> class Equality,
00514   typename id,
00515   typename generators_done,
00516   typename remaining_generators,
00517   typename elements
00518 >
00519 struct dimino_add_remaining_generators
00520 {
00521   typedef typename get<0, remaining_generators>::type first_generator;
00522   typedef typename skip<1, remaining_generators>::type next_generators;
00523 
00524   typedef contained_in_list_gf<Equality, first_generator, elements> _cil;
00525 
00526   typedef dimino_add_generator<
00527     Multiply,
00528     Equality,
00529     id,
00530     elements,
00531     generators_done,
00532     first_generator,
00533     _cil::value
00534   > _helper;
00535 
00536   typedef typename _helper::type new_elements;
00537 
00538   typedef dimino_add_remaining_generators<
00539     Multiply,
00540     Equality,
00541     id,
00542     typename concat<generators_done, type_list<first_generator>>::type,
00543     next_generators,
00544     new_elements
00545   > _next_iter;
00546 
00547   typedef typename _next_iter::type type;
00548   constexpr static int global_flags =
00549     _cil::global_flags |
00550     _helper::global_flags |
00551     _next_iter::global_flags;
00552 };
00553 
00554 template<
00555   template<typename, typename> class Multiply,
00556   template<typename, typename> class Equality,
00557   typename id,
00558   typename generators_done,
00559   typename elements
00560 >
00561 struct dimino_add_remaining_generators<Multiply, Equality, id, generators_done, type_list<>, elements>
00562 {
00563   typedef elements type;
00564   constexpr static int global_flags = 0;
00565 };
00566 
00581 template<
00582   template<typename, typename> class Multiply,
00583   template<typename, typename> class Equality,
00584   typename id,
00585   typename generators,
00586   int initial_global_flags = 0
00587 >
00588 struct enumerate_group_elements_noid
00589 {
00590   typedef dimino_first_step_elements<Multiply, Equality, id, generators> first_step;
00591   typedef typename first_step::type first_step_elements;
00592 
00593   typedef dimino_add_remaining_generators<
00594     Multiply,
00595     Equality,
00596     id,
00597     typename first_step::generators_done,
00598     typename first_step::next_generators, // remaining_generators
00599     typename first_step::type // first_step elements
00600   > _helper;
00601 
00602   typedef typename _helper::type type;
00603   constexpr static int global_flags =
00604     initial_global_flags |
00605     first_step::global_flags |
00606     _helper::global_flags;
00607 };
00608 
00609 // in case when no generators are specified
00610 template<
00611   template<typename, typename> class Multiply,
00612   template<typename, typename> class Equality,
00613   typename id,
00614   int initial_global_flags
00615 >
00616 struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags>
00617 {
00618   typedef type_list<id> type;
00619   constexpr static int global_flags = initial_global_flags;
00620 };
00621 
00639 template<
00640   template<typename, typename> class Multiply,
00641   template<typename, typename> class Equality,
00642   typename id,
00643   typename _generators
00644 >
00645 struct enumerate_group_elements
00646   : public enumerate_group_elements_noid<
00647       Multiply,
00648       Equality,
00649       id,
00650       typename strip_identities<Equality, id, _generators>::type,
00651       strip_identities<Equality, id, _generators>::global_flags
00652     >
00653 {
00654 };
00655 
00656 } // end namespace group_theory
00657 
00658 } // end namespace internal
00659 
00660 } // end namespace Eigen
00661 
00662 #endif // EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
00663 
00664 /*
00665  * kate: space-indent on; indent-width 2; mixedindent off; indent-mode cstyle;
00666  */
 All Classes Functions Variables Typedefs Enumerator