TensorSymmetry/util/TemplateGroupTheory.h

0001 // This file is part of Eigen, a lightweight C++ template library
0002 // for linear algebra.
0003 //
0004 // Copyright (C) 2013 Christian Seiler <christian@iwakd.de>
0005 //
0006 // This Source Code Form is subject to the terms of the Mozilla
0007 // Public License v. 2.0. If a copy of the MPL was not distributed
0008 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
0009
0010 #ifndef EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
0011 #define EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
0012
0013 namespace Eigen {
0014
0015 namespace internal {
0016
0017 namespace group_theory {
0018
0019 /** \internal
0020   * \file CXX11/src/TensorSymmetry/util/TemplateGroupTheory.h
0021   * This file contains C++ templates that implement group theory algorithms.
0022   *
0023   * The algorithms allow for a compile-time analysis of finite groups.
0024   *
0025   * Currently only Dimino's algorithm is implemented, which returns a list
0026   * of all elements in a group given a set of (possibly redundant) generators.
0027   * (One could also do that with the so-called orbital algorithm, but that
0028   * is much more expensive and usually has no advantages.)
0029   */
0030
0031 /**********************************************************************
0032  *                "Ok kid, here is where it gets complicated."
0033  *                         - Amelia Pond in the "Doctor Who" episode
0034  *                           "The Big Bang"
0035  *
0036  * Dimino's algorithm
0037  * ==================
0038  *
0039  * The following is Dimino's algorithm in sequential form:
0040  *
0041  * Input: identity element, list of generators, equality check,
0042  *        multiplication operation
0043  * Output: list of group elements
0044  *
0045  * 1. add identity element
0046  * 2. remove identities from list of generators
0047  * 3. add all powers of first generator that aren't the
0048  *    identity element
0049  * 4. go through all remaining generators:
0050  *        a. if generator is already in the list of elements
0051  *                -> do nothing
0052  *        b. otherwise
0053  *                i.   remember current # of elements
0054  *                     (i.e. the size of the current subgroup)
0055  *                ii.  add all current elements (which includes
0056  *                     the identity) each multiplied from right
0057  *                     with the current generator to the group
0058  *                iii. add all remaining cosets that are generated
0059  *                     by products of the new generator with itself
0060  *                     and all other generators seen so far
0061  *
0062  * In functional form, this is implemented as a long set of recursive
0063  * templates that have a complicated relationship.
0064  *
0065  * The main interface for Dimino's algorithm is the template
0066  * enumerate_group_elements. All lists are implemented as variadic
0067  * type_list<typename...> and numeric_list<typename = int, int...>
0068  * templates.
0069  *
0070  * 'Calling' templates is usually done via typedefs.
0071  *
0072  * This algorithm is an extended version of the basic version. The
0073  * extension consists in the fact that each group element has a set
0074  * of flags associated with it. Multiplication of two group elements
0075  * with each other results in a group element whose flags are the
0076  * XOR of the flags of the previous elements. Each time the algorithm
0077  * notices that a group element it just calculated is already in the
0078  * list of current elements, the flags of both will be compared and
0079  * added to the so-called 'global flags' of the group.
0080  *
0081  * The rationale behind this extension is that this allows not only
0082  * for the description of symmetries between tensor indices, but
0083  * also allows for the description of hermiticity, antisymmetry and
0084  * antihermiticity. Negation and conjugation each are specific bit
0085  * in the flags value and if two different ways to reach a group
0086  * element lead to two different flags, this poses a constraint on
0087  * the allowed values of the resulting tensor. For example, if a
0088  * group element is reach both with and without the conjugation
0089  * flags, it is clear that the resulting tensor has to be real.
0090  *
0091  * Note that this flag mechanism is quite generic and may have other
0092  * uses beyond tensor properties.
0093  *
0094  * IMPORTANT:
0095  *     This algorithm assumes the group to be finite. If you try to
0096  *     run it with a group that's infinite, the algorithm will only
0097  *     terminate once you hit a compiler limit (max template depth).
0098  *     Also note that trying to use this implementation to create a
0099  *     very large group will probably either make you hit the same
0100  *     limit, cause the compiler to segfault or at the very least
0101  *     take a *really* long time (hours, days, weeks - sic!) to
0102  *     compile. It is not recommended to plug in more than 4
0103  *     generators, unless they are independent of each other.
0104  */
0105
0106 /** \internal
0107   *
0108   * \class strip_identities
0109   * \ingroup CXX11_TensorSymmetry_Module
0110   *
0111   * \brief Cleanse a list of group elements of the identity element
0112   *
0113   * This template is used to make a first pass through all initial
0114   * generators of Dimino's algorithm and remove the identity
0115   * elements.
0116   *
0117   * \sa enumerate_group_elements
0118   */
0119 template<template<typename, typename> class Equality, typename id, typename L> struct strip_identities;
0120
0121 template<
0122   template<typename, typename> class Equality,
0123   typename id,
0124   typename t,
0125   typename... ts
0126 >
0127 struct strip_identities<Equality, id, type_list<t, ts...>>
0128 {
0129   typedef typename conditional<
0130     Equality<id, t>::value,
0131     typename strip_identities<Equality, id, type_list<ts...>>::type,
0132     typename concat<type_list<t>, typename strip_identities<Equality, id, type_list<ts...>>::type>::type
0133   >::type type;
0134   constexpr static int global_flags = Equality<id, t>::global_flags | strip_identities<Equality, id, type_list<ts...>>::global_flags;
0135 };
0136
0137 template<
0138   template<typename, typename> class Equality,
0139   typename id
0140   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, ts)
0141 >
0142 struct strip_identities<Equality, id, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(ts)>>
0143 {
0144   typedef type_list<> type;
0145   constexpr static int global_flags = 0;
0146 };
0147
0148 /** \internal
0149   *
0150   * \class dimino_first_step_elements_helper
0151   * \ingroup CXX11_TensorSymmetry_Module
0152   *
0153   * \brief Recursive template that adds powers of the first generator to the list of group elements
0154   *
0155   * This template calls itself recursively to add powers of the first
0156   * generator to the list of group elements. It stops if it reaches
0157   * the identity element again.
0158   *
0159   * \sa enumerate_group_elements, dimino_first_step_elements
0160   */
0161 template<
0162   template<typename, typename> class Multiply,
0163   template<typename, typename> class Equality,
0164   typename id,
0165   typename g,
0166   typename current_element,
0167   typename elements,
0168   bool dont_add_current_element   // = false
0169 >
0170 struct dimino_first_step_elements_helper
0171 #ifndef EIGEN_PARSED_BY_DOXYGEN
0172   : // recursive inheritance is too difficult for Doxygen
0173   public dimino_first_step_elements_helper<
0174     Multiply,
0175     Equality,
0176     id,
0177     g,
0178     typename Multiply<current_element, g>::type,
0179     typename concat<elements, type_list<current_element>>::type,
0180     Equality<typename Multiply<current_element, g>::type, id>::value
0181   > {};
0182
0183 template<
0184   template<typename, typename> class Multiply,
0185   template<typename, typename> class Equality,
0186   typename id,
0187   typename g,
0188   typename current_element,
0189   typename elements
0190 >
0191 struct dimino_first_step_elements_helper<Multiply, Equality, id, g, current_element, elements, true>
0192 #endif // EIGEN_PARSED_BY_DOXYGEN
0193 {
0194   typedef elements type;
0195   constexpr static int global_flags = Equality<current_element, id>::global_flags;
0196 };
0197
0198 /** \internal
0199   *
0200   * \class dimino_first_step_elements
0201   * \ingroup CXX11_TensorSymmetry_Module
0202   *
0203   * \brief Add all powers of the first generator to the list of group elements
0204   *
0205   * This template takes the first non-identity generator and generates the initial
0206   * list of elements which consists of all powers of that generator. For a group
0207   * with just one generated, it would be enumerated after this.
0208   *
0209   * \sa enumerate_group_elements
0210   */
0211 template<
0212   template<typename, typename> class Multiply,
0213   template<typename, typename> class Equality,
0214   typename id,
0215   typename generators
0216 >
0217 struct dimino_first_step_elements
0218 {
0219   typedef typename get<0, generators>::type first_generator;
0220   typedef typename skip<1, generators>::type next_generators;
0221   typedef type_list<first_generator> generators_done;
0222
0223   typedef dimino_first_step_elements_helper<
0224     Multiply,
0225     Equality,
0226     id,
0227     first_generator,
0228     first_generator,
0229     type_list<id>,
0230     false
0231   > helper;
0232   typedef typename helper::type type;
0233   constexpr static int global_flags = helper::global_flags;
0234 };
0235
0236 /** \internal
0237   *
0238   * \class dimino_get_coset_elements
0239   * \ingroup CXX11_TensorSymmetry_Module
0240   *
0241   * \brief Generate all elements of a specific coset
0242   *
0243   * This template generates all the elements of a specific coset by
0244   * multiplying all elements in the given subgroup with the new
0245   * coset representative. Note that the first element of the
0246   * subgroup is always the identity element, so the first element of
0247   * the result of this template is going to be the coset
0248   * representative itself.
0249   *
0250   * Note that this template accepts an additional boolean parameter
0251   * that specifies whether to actually generate the coset (true) or
0252   * just return an empty list (false).
0253   *
0254   * \sa enumerate_group_elements, dimino_add_cosets_for_rep
0255   */
0256 template<
0257   template<typename, typename> class Multiply,
0258   typename sub_group_elements,
0259   typename new_coset_rep,
0260   bool generate_coset      // = true
0261 >
0262 struct dimino_get_coset_elements
0263 {
0264   typedef typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type type;
0265 };
0266
0267 template<
0268   template<typename, typename> class Multiply,
0269   typename sub_group_elements,
0270   typename new_coset_rep
0271 >
0272 struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false>
0273 {
0274   typedef type_list<> type;
0275 };
0276
0277 /** \internal
0278   *
0279   * \class dimino_add_cosets_for_rep
0280   * \ingroup CXX11_TensorSymmetry_Module
0281   *
0282   * \brief Recursive template for adding coset spaces
0283   *
0284   * This template multiplies the coset representative with a generator
0285   * from the list of previous generators. If the new element is not in
0286   * the group already, it adds the corresponding coset. Finally it
0287   * proceeds to call itself with the next generator from the list.
0288   *
0289   * \sa enumerate_group_elements, dimino_add_all_coset_spaces
0290   */
0291 template<
0292   template<typename, typename> class Multiply,
0293   template<typename, typename> class Equality,
0294   typename id,
0295   typename sub_group_elements,
0296   typename elements,
0297   typename generators,
0298   typename rep_element,
0299   int sub_group_size
0300 >
0301 struct dimino_add_cosets_for_rep;
0302
0303 template<
0304   template<typename, typename> class Multiply,
0305   template<typename, typename> class Equality,
0306   typename id,
0307   typename sub_group_elements,
0308   typename elements,
0309   typename g,
0310   typename... gs,
0311   typename rep_element,
0312   int sub_group_size
0313 >
0314 struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element, sub_group_size>
0315 {
0316   typedef typename Multiply<rep_element, g>::type new_coset_rep;
0317   typedef contained_in_list_gf<Equality, new_coset_rep, elements> _cil;
0318   constexpr static bool add_coset = !_cil::value;
0319
0320   typedef typename dimino_get_coset_elements<
0321     Multiply,
0322     sub_group_elements,
0323     new_coset_rep,
0324     add_coset
0325   >::type coset_elements;
0326
0327   typedef dimino_add_cosets_for_rep<
0328     Multiply,
0329     Equality,
0330     id,
0331     sub_group_elements,
0332     typename concat<elements, coset_elements>::type,
0333     type_list<gs...>,
0334     rep_element,
0335     sub_group_size
0336   > _helper;
0337
0338   typedef typename _helper::type type;
0339   constexpr static int global_flags = _cil::global_flags | _helper::global_flags;
0340
0341   /* Note that we don't have to update global flags here, since
0342    * we will only add these elements if they are not part of
0343    * the group already. But that only happens if the coset rep
0344    * is not already in the group, so the check for the coset rep
0345    * will catch this.
0346    */
0347 };
0348
0349 template<
0350   template<typename, typename> class Multiply,
0351   template<typename, typename> class Equality,
0352   typename id,
0353   typename sub_group_elements,
0354   typename elements
0355   EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
0356   typename rep_element,
0357   int sub_group_size
0358 >
0359 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>
0360 {
0361   typedef elements type;
0362   constexpr static int global_flags = 0;
0363 };
0364
0365 /** \internal
0366   *
0367   * \class dimino_add_all_coset_spaces
0368   * \ingroup CXX11_TensorSymmetry_Module
0369   *
0370   * \brief Recursive template for adding all coset spaces for a new generator
0371   *
0372   * This template tries to go through the list of generators (with
0373   * the help of the dimino_add_cosets_for_rep template) as long as
0374   * it still finds elements that are not part of the group and add
0375   * the corresponding cosets.
0376   *
0377   * \sa enumerate_group_elements, dimino_add_cosets_for_rep
0378   */
0379 template<
0380   template<typename, typename> class Multiply,
0381   template<typename, typename> class Equality,
0382   typename id,
0383   typename sub_group_elements,
0384   typename elements,
0385   typename generators,
0386   int sub_group_size,
0387   int rep_pos,
0388   bool stop_condition        // = false
0389 >
0390 struct dimino_add_all_coset_spaces
0391 {
0392   typedef typename get<rep_pos, elements>::type rep_element;
0393   typedef dimino_add_cosets_for_rep<
0394     Multiply,
0395     Equality,
0396     id,
0397     sub_group_elements,
0398     elements,
0399     generators,
0400     rep_element,
0401     sub_group_elements::count
0402   > _ac4r;
0403   typedef typename _ac4r::type new_elements;
0404
0405   constexpr static int new_rep_pos = rep_pos + sub_group_elements::count;
0406   constexpr static bool new_stop_condition = new_rep_pos >= new_elements::count;
0407
0408   typedef dimino_add_all_coset_spaces<
0409     Multiply,
0410     Equality,
0411     id,
0412     sub_group_elements,
0413     new_elements,
0414     generators,
0415     sub_group_size,
0416     new_rep_pos,
0417     new_stop_condition
0418   > _helper;
0419
0420   typedef typename _helper::type type;
0421   constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
0422 };
0423
0424 template<
0425   template<typename, typename> class Multiply,
0426   template<typename, typename> class Equality,
0427   typename id,
0428   typename sub_group_elements,
0429   typename elements,
0430   typename generators,
0431   int sub_group_size,
0432   int rep_pos
0433 >
0434 struct dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, elements, generators, sub_group_size, rep_pos, true>
0435 {
0436   typedef elements type;
0437   constexpr static int global_flags = 0;
0438 };
0439
0440 /** \internal
0441   *
0442   * \class dimino_add_generator
0443   * \ingroup CXX11_TensorSymmetry_Module
0444   *
0445   * \brief Enlarge the group by adding a new generator.
0446   *
0447   * It accepts a boolean parameter that determines if the generator is redundant,
0448   * i.e. was already seen in the group. In that case, it reduces to a no-op.
0449   *
0450   * \sa enumerate_group_elements, dimino_add_all_coset_spaces
0451   */
0452 template<
0453   template<typename, typename> class Multiply,
0454   template<typename, typename> class Equality,
0455   typename id,
0456   typename elements,
0457   typename generators_done,
0458   typename current_generator,
0459   bool redundant          // = false
0460 >
0461 struct dimino_add_generator
0462 {
0463   /* this template is only called if the generator is not redundant
0464    * => all elements of the group multiplied with the new generator
0465    *    are going to be new elements of the most trivial coset space
0466    */
0467   typedef typename apply_op_from_right<Multiply, current_generator, elements>::type multiplied_elements;
0468   typedef typename concat<elements, multiplied_elements>::type new_elements;
0469
0470   constexpr static int rep_pos = elements::count;
0471
0472   typedef dimino_add_all_coset_spaces<
0473     Multiply,
0474     Equality,
0475     id,
0476     elements, // elements of previous subgroup
0477     new_elements,
0478     typename concat<generators_done, type_list<current_generator>>::type,
0479     elements::count, // size of previous subgroup
0480     rep_pos,
0481     false // don't stop (because rep_pos >= new_elements::count is always false at this point)
0482   > _helper;
0483   typedef typename _helper::type type;
0484   constexpr static int global_flags = _helper::global_flags;
0485 };
0486
0487 template<
0488   template<typename, typename> class Multiply,
0489   template<typename, typename> class Equality,
0490   typename id,
0491   typename elements,
0492   typename generators_done,
0493   typename current_generator
0494 >
0495 struct dimino_add_generator<Multiply, Equality, id, elements, generators_done, current_generator, true>
0496 {
0497   // redundant case
0498   typedef elements type;
0499   constexpr static int global_flags = 0;
0500 };
0501
0502 /** \internal
0503   *
0504   * \class dimino_add_remaining_generators
0505   * \ingroup CXX11_TensorSymmetry_Module
0506   *
0507   * \brief Recursive template that adds all remaining generators to a group
0508   *
0509   * Loop through the list of generators that remain and successively
0510   * add them to the group.
0511   *
0512   * \sa enumerate_group_elements, dimino_add_generator
0513   */
0514 template<
0515   template<typename, typename> class Multiply,
0516   template<typename, typename> class Equality,
0517   typename id,
0518   typename generators_done,
0519   typename remaining_generators,
0520   typename elements
0521 >
0522 struct dimino_add_remaining_generators
0523 {
0524   typedef typename get<0, remaining_generators>::type first_generator;
0525   typedef typename skip<1, remaining_generators>::type next_generators;
0526
0527   typedef contained_in_list_gf<Equality, first_generator, elements> _cil;
0528
0529   typedef dimino_add_generator<
0530     Multiply,
0531     Equality,
0532     id,
0533     elements,
0534     generators_done,
0535     first_generator,
0536     _cil::value
0537   > _helper;
0538
0539   typedef typename _helper::type new_elements;
0540
0541   typedef dimino_add_remaining_generators<
0542     Multiply,
0543     Equality,
0544     id,
0545     typename concat<generators_done, type_list<first_generator>>::type,
0546     next_generators,
0547     new_elements
0548   > _next_iter;
0549
0550   typedef typename _next_iter::type type;
0551   constexpr static int global_flags =
0552     _cil::global_flags |
0553     _helper::global_flags |
0554     _next_iter::global_flags;
0555 };
0556
0557 template<
0558   template<typename, typename> class Multiply,
0559   template<typename, typename> class Equality,
0560   typename id,
0561   typename generators_done,
0562   typename elements
0563 >
0564 struct dimino_add_remaining_generators<Multiply, Equality, id, generators_done, type_list<>, elements>
0565 {
0566   typedef elements type;
0567   constexpr static int global_flags = 0;
0568 };
0569
0570 /** \internal
0571   *
0572   * \class enumerate_group_elements_noid
0573   * \ingroup CXX11_TensorSymmetry_Module
0574   *
0575   * \brief Helper template that implements group element enumeration
0576   *
0577   * This is a helper template that implements the actual enumeration
0578   * of group elements. This has been split so that the list of
0579   * generators can be cleansed of the identity element before
0580   * performing the actual operation.
0581   *
0582   * \sa enumerate_group_elements
0583   */
0584 template<
0585   template<typename, typename> class Multiply,
0586   template<typename, typename> class Equality,
0587   typename id,
0588   typename generators,
0589   int initial_global_flags = 0
0590 >
0591 struct enumerate_group_elements_noid
0592 {
0593   typedef dimino_first_step_elements<Multiply, Equality, id, generators> first_step;
0594   typedef typename first_step::type first_step_elements;
0595
0596   typedef dimino_add_remaining_generators<
0597     Multiply,
0598     Equality,
0599     id,
0600     typename first_step::generators_done,
0601     typename first_step::next_generators, // remaining_generators
0602     typename first_step::type // first_step elements
0603   > _helper;
0604
0605   typedef typename _helper::type type;
0606   constexpr static int global_flags =
0607     initial_global_flags |
0608     first_step::global_flags |
0609     _helper::global_flags;
0610 };
0611
0612 // in case when no generators are specified
0613 template<
0614   template<typename, typename> class Multiply,
0615   template<typename, typename> class Equality,
0616   typename id,
0617   int initial_global_flags
0618 >
0619 struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags>
0620 {
0621   typedef type_list<id> type;
0622   constexpr static int global_flags = initial_global_flags;
0623 };
0624
0625 /** \internal
0626   *
0627   * \class enumerate_group_elements
0628   * \ingroup CXX11_TensorSymmetry_Module
0629   *
0630   * \brief Enumerate all elements in a finite group
0631   *
0632   * This template enumerates all elements in a finite group. It accepts
0633   * the following template parameters:
0634   *
0635   * \tparam Multiply      The multiplication operation that multiplies two group elements
0636   *                       with each other.
0637   * \tparam Equality      The equality check operation that checks if two group elements
0638   *                       are equal to another.
0639   * \tparam id            The identity element
0640   * \tparam _generators   A list of (possibly redundant) generators of the group
0641   */
0642 template<
0643   template<typename, typename> class Multiply,
0644   template<typename, typename> class Equality,
0645   typename id,
0646   typename _generators
0647 >
0648 struct enumerate_group_elements
0649   : public enumerate_group_elements_noid<
0650       Multiply,
0651       Equality,
0652       id,
0653       typename strip_identities<Equality, id, _generators>::type,
0654       strip_identities<Equality, id, _generators>::global_flags
0655     >
0656 {
0657 };
0658
0659 } // end namespace group_theory
0660
0661 } // end namespace internal
0662
0663 } // end namespace Eigen
0664
0665 #endif // EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
0666
0667 /*
0668  * kate: space-indent on; indent-width 2; mixedindent off; indent-mode cstyle;
0669  */