TemplateGroupTheory.h (21046B)
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 * the 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 */