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
|(other)
Alias for: S_pair