atlas  0.6
mod2_system.h
Go to the documentation of this file.
1 /*
2  This is mod2_system.h: Solving linear systems over the two-element field
3
4  Copyright (C) 2014, Marc van Leeuwen
5  part of the Atlas of Lie Groups and Representations
6
8 */
9
10 #ifndef MOD2_SYSTEM_H /* guard against multiple inclusions */
11 #define MOD2_SYSTEM_H
12
13 #include <vector>
14 #include <iostream>
15 #include "bitmap.h"
16
17 namespace atlas {
18
19 namespace mod2_system {
20
21 // We solve systems incrementally, feeding unknowns an equations into a system
22
24 {
25  typedef std::vector<unsigned long> linear_combination;
26  struct equation {
27  linear_combination lhs; unsigned int rhs; // only for its parity
28  equation(unsigned int val) : lhs(), rhs(val&1u) {}
29  std::ostream& print(std::ostream& f) const;
30  };
31
32  std::vector<equation> eqn; // equations in permuted echelon form
33  std::vector<unsigned long> pivot_index; // which |eqn| solves each unknown
34  enum { no_pivot=~0ul };
35
36  public:
37  // the incremental nature of solving means we only have a default constructor
38  Mod2_System() : eqn(), pivot_index() {}
39
40  private:
41  Mod2_System(const Mod2_System&); // copy forbidden
42  Mod2_System& operator=(const Mod2_System&); // assignment forbidden
43  public:
44
45  // manipulators
46
47  // add $n$ unknowns, return \emph{old} size (number of first new unknown)
48  unsigned long extend(unsigned int n=1);
49
50  // add an equation, with nonzero LHS terms from begin..end
51  template <typename I> // input iterator with unsigned value type
52  bool add (I begin, I end, unsigned int rhs); // returns whether consistent
53
54  void reduce(); // simplify system to eliminate all pivot unknowns from |eqn|
55
56  // accessors
57
58  unsigned long size() const; // current number of indeterminates
59  bool consistent() const; // whether at least one solution exists
60
61  // the following two methods return |~0ul| in case of an inconsistent system
62  unsigned long rank() const; // effective number of equations
63  unsigned long dimension() const; // dimension of solution space
64
65  bitmap::BitMap a_solution() const; // sample solution, set of nonzero unknowns
66
67  // the following calls |reduce| for efficiency, hence is a manipulator
68  std::vector<bitmap::BitMap> solution_basis(); // kernel of homogenous system
69
70  private:
71  // eliminate set pivot variable of |eqn[inx]| from |dst|, return its |rhs|
72  unsigned int eliminate (unsigned long inx, bitmap::BitMap& dst) const;
73 }; // |Mod2_System|
74
75 } // |namespace mod2_system|
76
77 } // |namespace atlas|
78
79 #endif
Definition: mod2_system.h:34
equation(unsigned int val)
Definition: mod2_system.h:28
bool consistent() const
Definition: mod2_system.cpp:71
unsigned int eliminate(unsigned long inx, bitmap::BitMap &dst) const
Definition: mod2_system.cpp:77
linear_combination lhs
Definition: mod2_system.h:27
unsigned long dimension() const
Definition: mod2_system.cpp:93
Mod2_System & operator=(const Mod2_System &)
unsigned long size() const
Definition: mod2_system.cpp:32
std::vector< bitmap::BitMap > solution_basis()
Definition: mod2_system.cpp:145
unsigned long extend(unsigned int n=1)
Definition: mod2_system.cpp:35
unsigned long rank() const
Definition: mod2_system.cpp:88
std::ostream & print(std::ostream &f) const
Definition: mod2_system.cpp:18
void reduce()
Definition: mod2_system.cpp:117
Mod2_System()
Definition: mod2_system.h:38
std::vector< equation > eqn
Definition: mod2_system.h:32
Definition: mod2_system.h:26
Definitions and declarations for the BitMap class.
std::vector< unsigned long > linear_combination
Definition: mod2_system.h:25
unsigned int rhs
Definition: mod2_system.h:27
Definition: mod2_system.h:23
bitmap::BitMap a_solution() const
Definition: mod2_system.cpp:99
unsigned long n
Definition: axis.cpp:77
simple_list< T, Alloc >::const_iterator end(const simple_list< T, Alloc > &l)
Definition: sl_list.h:650
Definition: Atlas.h:38
Container of a large (more than twice the machine word size) set of bits.
Definition: bitmap.h:52
Definition: common.h:36
bool add(I begin, I end, unsigned int rhs)
Definition: mod2_system.cpp:44
std::vector< unsigned long > pivot_index
Definition: mod2_system.h:33