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