Module: Algebra::Groebner

Included in:
MPolynomial
Defined in:
lib/algebra/groebner-basis.rb,
lib/algebra/groebner-basis-coeff.rb

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

._ct(fm, b, i, j) ⇒ Object 



103
104
105
106
107
108
109
110
111
112
 
# File 'lib/algebra/groebner-basis.rb', line 103

def self._ct(fm, b, i, j)
  0.upto fm.size-1 do |k|
    next if k == i or
	k == j or
	i < k ? b.include?([i, k]) : b.include?([k, i]) or
	j < k ? b.include?([j, k]) : b.include?([k, j])
    return true if fm[k].divide_or?(fm[i], fm[j])
  end
  false
end

.basis(g) ⇒ Object 



139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/algebra/groebner-basis.rb', line 139

def self.basis(g)
  gbasis = nil

#    gbasis = basis_132D(g)
  gbasis = basis_159A(g)

  gbasis = minimal_basis(gbasis)
  gbasis = reduced_basis(gbasis)
  gbasis.sort!{|x, y| y <=> x}
  gbasis
end

.basis?(f) ⇒ Boolean

Returns:

  • (Boolean) 


26
27
28
29
30
31
32
33
 
# File 'lib/algebra/groebner-basis.rb', line 26

def self.basis?(f)
  f.each_pair do |x, y|
    unless ((x|y) % f).zero?
	return false
    end
  end
  true
end

.basis_132D(f) ⇒ Object 



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/algebra/groebner-basis.rb', line 61

def self.basis_132D(f)
  gbasis = f.dup
  pairs = []
  gbasis.each_pair do |x, y|
    pairs.push [x, y]
  end
  while pair = pairs.shift
    x, y = pair
    s = (x|y) % gbasis
    unless s.zero?
	gbasis.each do |z| pairs.push([z, s]) end
	gbasis.push s
    end
  end
  gbasis
end

.basis_159A(f) ⇒ Object 



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/algebra/groebner-basis.rb', line 78

def self.basis_159A(f)
  gbasis = f.sort # little effort
  glm = gbasis.collect{|x| x.lm}
  pairs = []
  (0...glm.size).to_a.each_pair do |i, j|
    pairs.push [i, j]
  end

  until pairs.empty?
    i, j = pairs.first
    if !glm[i].prime_to?(glm[j]) && !_ct(glm, pairs, i, j)
	s = (gbasis[i]|gbasis[j]) % gbasis
	unless s.zero?
 0.upto glm.size-1 do |k|
   pairs.push [k, glm.size]
 end
 gbasis.push s
 glm.push s.lm
	end
    end
    pairs.shift
  end
  gbasis
end

.basis_coeff(g) ⇒ Object 



132
133
134
135
136
137
138
139
140
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 132

def self.basis_coeff(g)
  #    coeff, gbasis = basis_coeff_132D(g)
  coeff, gbasis = basis_coeff_159A(g)
  coeff, gbasis = minimal_basis_coeff(coeff, gbasis)
  coeff, gbasis = reduced_basis_coeff(coeff, gbasis)
  ind = (0...gbasis.size).to_a
  ind.sort! { |i, j| gbasis[j] <=> gbasis[i] }
  [coeff.values_at(*ind), gbasis.values_at(*ind)]
end

.basis_coeff_132D(g) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 17

def self.basis_coeff_132D(g)
  gbasis = g.dup
  n0 = g.size
  #    coeff = (0...n0).collect{|k| [0]*k+[1]+[0]*(n0-k-1)}
  zero = f.first.zero
  unity = f.first.unity
  coeff = (0...n0).collect { |k| [zero] * k + [unity] + [zero] * (n0 - k - 1) }
  pairs = []
  g.each_pair_with_index do |x, y, i, j|
    pairs.push [x, y, i, j]
  end
  while pair = pairs.shift
    x, y, i, j = pair
    t, a, b = x.S_pair_coeff(y)
    q, s = t.divmod(*gbasis)
    next if s.zero?
    n1 = gbasis.size
    gbasis.each_with_index { |z, k| pairs.push([z, s, k, n1]) }
    u = (0...n0).collect do |k|
      sum = 0
      (0...gbasis.size).each do |m|
        sum += (m == i ? a - q[m] : (m == j ? b - q[m] : -q[m])) * coeff[m][k]
      end
      sum
    end
    coeff.push u
    gbasis.push s
  end
  [coeff, gbasis]
end

.basis_coeff_159A(f) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 48

def self.basis_coeff_159A(f)
  n0 = f.size
  glm = f.collect(&:lm)
  #    fc = (0...n0).collect{|k| [0]*k+[1]+[0]*(n0-k-1)}
  zero = f.first.zero
  unity = f.first.unity
  fc = (0...n0).collect { |k| [zero] * k + [unity] + [zero] * (n0 - k - 1) }

  indexes = (0...n0).sort { |i, j| glm[i] <=> glm[j] }
  glm = glm.values_at(*indexes)
  gbasis = f.values_at(*indexes)
  coeff = fc.values_at(*indexes)

  pairs = []
  (0...n0).to_a.each_pair do |i, j|
    pairs.push [i, j]
  end

  until pairs.empty?
    i, j = pairs.first
    if !glm[i].prime_to?(glm[j]) && !_ct(glm, pairs, i, j)
      t, a, b = gbasis[i].S_pair_coeff(gbasis[j])
      q, s = t.divmod(*gbasis)
      unless s.zero?
        0.upto glm.size - 1 do |k|
          pairs.push [k, glm.size]
        end
        u = (0...n0).collect do |k|
          sum = 0
          (0...gbasis.size).each do |m|
            sum += (m == i ? a - q[m] : (m == j ? b - q[m] : -q[m])) * coeff[m][k]
          end
          sum
        end
        coeff.push u
        gbasis.push s
        glm.push s.lm
      end
    end
    pairs.shift
  end

  [coeff, gbasis]
end

.minimal_basis(gbasis) ⇒ Object 



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/algebra/groebner-basis.rb', line 114

def self.minimal_basis(gbasis)
#    p [200, gbasis]
  glm = gbasis.collect{|x| x.lm}
  indexes = (0...gbasis.size).sort{|i, j| glm[j] <=> glm[i]}
  indexes.each_with_index do |i, s|
    (s+1).upto indexes.size-1 do |k| j = indexes[k]
#	p [glm[j], glm[i],  glm[j].divide? glm[i]]
	if glm[j].divide? glm[i]
 indexes[s] = nil
 break
	end
    end
  end
  indexes.compact!
  gbasis.values_at(*indexes)
end

.minimal_basis?(f) ⇒ Boolean

Returns:

  • (Boolean) 


35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/algebra/groebner-basis.rb', line 35

def self.minimal_basis?(f)
  return false unless basis?(f)
  indexes = (0...f.size).to_a
  indexes.each do |i|
    others = f.values_at(*(indexes-[i])).collect{|x| x.lt}
    if (f[i].lt % others).zero?
	return false
    end
  end
  true
end

.minimal_basis_coeff(coeff, gbasis) ⇒ Object 



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 93

def self.minimal_basis_coeff(coeff, gbasis)
  glm = gbasis.collect(&:lm)
  indexes = (0...gbasis.size).sort { |i, j| glm[j] <=> glm[i] }
  indexes.each_with_index do |i, s|
    (s + 1).upto indexes.size - 1 do |k|
      j = indexes[k]
      if glm[j].divide? glm[i]
        indexes[s] = nil
        break
      end
    end
  end
  indexes.compact!
  b = gbasis.values_at(*indexes)
  c = coeff.values_at(*indexes)
  [c, b]
end

.reduced_basis(gbasis) ⇒ Object 



131
132
133
134
135
136
137
 
# File 'lib/algebra/groebner-basis.rb', line 131

def self.reduced_basis(gbasis)
  gbasis.each_with_index do |x, i|
    (g = gbasis.dup).delete_at(i)
    gbasis[i] = x % g
  end
  gbasis.collect{|t| t / t.lc}
end

.reduced_basis?(f) ⇒ Boolean

Returns:

  • (Boolean) 


47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/algebra/groebner-basis.rb', line 47

def self.reduced_basis?(f)
  return false unless basis?(f)
  indexes = (0...f.size).to_a
  indexes.each do |i|
    others = f.values_at(*(indexes-[i])).collect{|x| x.lt}
    f[i].each_term do |t|
	if (t % others).zero?
 return false
	end
    end
  end
  true
end

.reduced_basis_coeff(coeff, gbasis) ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 111

def self.reduced_basis_coeff(coeff, gbasis)
  gbasis.each_with_index do |x, i|
    (g = gbasis.dup).delete_at(i)
    q, gbasis[i] = x.divmod(*g)
    coeff[i] = (0...coeff[i].size).collect do |k|
      sum = 0
      (0...gbasis.size).each do |m|
        d = (m < i ? -q[m] : m == i ? 1 : -q[m - 1])
        sum += d * coeff[m][k]
      end
      sum
    end
  end
  gbasis.each_with_index do |x, i|
    c = x.lc
    coeff[i].collect! { |v| v / c }
    gbasis[i] = x / c
  end
  [coeff, gbasis]
end

Instance Method Details

#div_cg(f, cg = nil) ⇒ Object 



160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 160

def div_cg(f, cg = nil)
  cg = Groebner.basis_coeff(f) unless cg
  coeff, gbasis = cg
  q, r = divmod(*gbasis)
  q0 = (0...f.size).collect do |i|
    sum = 0
    (0...q.size).each do |j|
      sum += q[j] * coeff[j][i]
    end
    sum
  end
  [q0, r]
end

#divmod_s(*f) ⇒ Object 



155
156
157
158
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 155

def divmod_s(*f)
  cg = Groebner.basis_coeff(f)
  div_cg(f, cg)
end

#divmod_s0(*f) ⇒ Object 



142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 142

def divmod_s0(*f)
  coeff, gbasis = Groebner.basis_coeff(f)
  q, r = divmod(*gbasis)
  q0 = (0...f.size).collect do |i|
    sum = 0
    (0...q.size).each do |j|
      sum += q[j] * coeff[j][i]
    end
    sum
  end
  [q0, r]
end

#S_pair(other) ⇒ Object Also known as: | 



19
20
21
22
 
# File 'lib/algebra/groebner-basis.rb', line 19

def S_pair(other)
  x = lm.lcm(other.lm)
  x / lt * rt - x / other.lt * other.rt
end

#S_pair_coeff(other) ⇒ Object 



9
10
11
12
13
14
15
 
# File 'lib/algebra/groebner-basis-coeff.rb', line 9

def S_pair_coeff(other)
  x = lm.lcm(other.lm)
  a = x / lt
  b = x / other.lt
  y = a * rt - b * other.rt
  [y, a, -b]
end