module Algebra::Groebner
Public Class Methods
_ct(fm, b, i, j)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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
Public Instance Methods
S_pair(other)
click to toggle source
# 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
Also aliased as: |
S_pair_coeff(other)
click to toggle source
# 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
div_cg(f, cg = nil)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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