module Algebra::GaussianElimination

Public Instance Methods

divide_c(j, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 61
def divide_c(j, c)
  dup.divide_c!(j, c)
end
divide_c!(j, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 57
def divide_c!(j, c)
  set_column(j, column(j).collect{|x| x / c})
end
divide_r(i, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 53
def divide_r(i, c)
  dup.divide_r!(i, c)
end
divide_r!(i, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 49
def divide_r!(i, c)
  set_row(i, row(i).collect{|x| x / c})
end
kernel_basis() click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 189
def kernel_basis
  if pivots =  step_matrix?
    m = self
  else
    m = left_sweep
    pivots = m.step_matrix?
  end
  basis = []

  v = Algebra.Vector(ground, csize)
  (0...csize).each do |i|
    unless pivots.include? i
      base = v.vector{|j|
        if j == i
          ground.unity
        elsif k = pivots.index(j)
          -m[k, i] / m[k, j] #m[k, j] may not be an unit.
        else
          ground.zero
        end
      }
      basis.push base
    end
  end
  basis
end
left_eliminate!() click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 92
def left_eliminate!
  inv = Algebra.SquareMatrix(ground, rsize).unity
  k = ground.unity
  pi = 0
  each_j do |j|
    if i = (pi...rsize).find{|i1| !self[i1, j].zero?}
      #       pivots.push j
      if i != pi
        swap_r!(pi, i); inv.swap_r!(pi, i)
        k = -k
      end
      ##### this lets the entries be in ground #####
      c = ground.unity / self[pi, j]
      ##############################################
      multiply_r!(pi, c); inv.multiply_r!(pi, c)
      k = k * c
      each_i do |i0|
        next if i0 == pi
        d = self[i0, j]# / self[pi, j]
        mix_r!(i0, pi, -d); inv.mix_r!(i0, pi, -d)
      end
      pi += 1
    end
  end
  [inv, k, pi]
end
left_eliminate_euclidian!() click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 130
def left_eliminate_euclidian!
  inv = Algebra.SquareMatrix(ground, rsize).unity
  k = ground.unity
  pi = 0
  each_j do |j|
    if i = (pi...rsize).find{|i1| !self[i1, j].zero?}
      #       pivots.push j
      if i != pi
        swap_r!(pi, i); inv.swap_r!(pi, i)
        k = -k
      end
      k *= _normalize!(pi, j, inv)
      (pi+1...rsize).each do |i0|
        #   each_i do |i0|;  next if i0 == pi
        d = self[i0, j] / self[pi, j]
        mix_r!(i0, pi, -d); inv.mix_r!(i0, pi, -d)
        if !self[i0, j].zero? && i0 > pi
          swap_r!(i0, pi); inv.swap_r!(i0, pi);
          k = -k
          k *= _normalize!(pi, j, inv)
          redo
        end
      end

      pi += 1
    end
  end
  [inv, k, pi]
end
left_inverse() click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 160
def left_inverse
  dup.left_eliminate![0]
end
left_sweep() click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 164
def left_sweep
  m = dup
  m.left_eliminate!
  m
end
mix_c(i, j, c = nil) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 88
def mix_c(i, j, c = nil)
  dup.mix_c!(i, j, c)
end
mix_c!(i, j, c = nil) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 79
def mix_c!(i, j, c = nil)
  column_i = column(i)
  column_j = column(j)
  set_column(i, (0...rsize).collect{|k|
    column_i[k] + (c ? column_j[k]*c : column_j[k])
  }
  )
end
mix_r(i, j, c = nil) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 75
def mix_r(i, j, c = nil)
  dup.mix_r!(i, j, c)
end
mix_r!(i, j, c = nil) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 65
def mix_r!(i, j, c = nil)
  row_i = row(i)
  row_j = row(j)
  set_row(i,
  (0...csize).collect {|k|
    row_i[k] + (c ? row_j[k]*c : row_j[k])
  }
  )
end
multiply_c(j, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 45
def multiply_c(j, c)
  dup.multiply_c!(j, c)
end
multiply_c!(j, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 41
def multiply_c!(j, c)
  set_column(j, column(j).collect{|x| x * c})
end
multiply_r(i, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 37
def multiply_r(i, c)
  dup.multiply_r!(i, c)
end
multiply_r!(i, c) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 33
def multiply_r!(i, c)
  set_row(i, row(i).collect{|x| x * c})
end
sswap_r!(i, j) click to toggle source

ElementaryOpeartion

# File lib/algebra/gaussian-elimination.rb, line 10
def sswap_r!(i, j)
  a, b = row!(i), row!(j)
  set_row(i, b).set_row(j, a)
end
step_matrix?() click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 170
def step_matrix?
  pivots = []
  i = j = 0
  each_j do |j|
    if !self[i, j].zero?
      0.upto rsize - 1 do |i0|
        return nil if i0 != i && !self[i0, j].zero?
      end
      pivots << j
      return pivots if (i += 1) >= rsize
    else
      (i+1).upto rsize - 1 do |i0|
        return nil if i0 != i && !self[i0, j].zero?
      end
    end
  end
  pivots
end
swap_c(i, j) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 29
def swap_c(i, j)
  dup.swap_c!(i, j)
end
swap_c!(i, j) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 24
def swap_c!(i, j)
  a, b = column(i), column(j)
  set_column(i, b).set_column(j, a)
end
swap_r(i, j) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 20
def swap_r(i, j)
  dup.swap_r!(i, j)
end
swap_r!(i, j) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 15
def swap_r!(i, j)
  a, b = row(i), row(j)
  set_row(i, b).set_row(j, a)
end

Private Instance Methods

_normalize!(pi, j, inv) click to toggle source
# File lib/algebra/gaussian-elimination.rb, line 119
def _normalize!(pi, j, inv)
  c = ground.unity
  e = self[pi, j]
  if !e.unity? && e.unit?
    c /= e
    multiply_r!(pi, c); inv.multiply_r!(pi, c)
  end
  c
end