![]() |
Eigen-unsupported
3.3.3
|
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 */