Module: Matrix::Householder

Defined in:
lib/extendmatrix.rb

Class Method Summary collapse

Class Method Details

.bidiag(mat) ⇒ Object

Householder Bidiagonalization algorithm. MC, Golub, pg 252, Algorithm 5.4.2 Returns the matrices U_B and V_B such that: U_B^T * A * V_B = B, where B is upper bidiagonal.



748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
 
# File 'lib/extendmatrix.rb', line 748

def self.bidiag(mat)
a = mat.clone
m = a.row_size
n = a.column_size
ub = Matrix.I(m)
vb = Matrix.I(n)
n.times{|j|
  v, beta = a[j..m-1,j].house
  a[j..m-1, j..n-1] = (Matrix.I(m-j) - beta * (v * v.t)) * a[j..m-1, j..n-1]
  a[j+1..m-1, j] = v[1..(m-j-1)]
  ub *= bidiagUV(a[j+1..m-1,j], m, beta) #Ub = U_1 * U_2 * ... * U_n
  if j < n - 2
    v, beta = (a[j, j+1..n-1]).house
    a[j..m-1, j+1..n-1] = a[j..m-1, j+1..n-1] * (Matrix.I(n-j-1) - beta * (v * v.t))
    a[j, j+2..n-1] = v[1..n-j-2]
    vb  *= bidiagUV(a[j, j+2..n-1], n, beta) #Vb = V_1 * U_2 * ... * V_n-2
  end	}
  return ub, vb
end

.bidiagUV(essential, dim, beta) ⇒ Object

From the essential part of Householder vector it returns the coresponding upper(U_j)/lower(V_j) matrix



735
736
737
738
739
740
741
 
# File 'lib/extendmatrix.rb', line 735

def self.bidiagUV(essential, dim, beta)
  v = Vector.concat(Vector[1], essential)
  dimv = v.size
  
  
  Matrix.diag(Matrix.robust_I(dim - dimv), Matrix.I(dimv) - beta * (v * v.t) )
end

.QR(mat) ⇒ Object

a QR factorization that uses Householder transformation Q^T * A = R MC, Golub & van Loan, pg 224, 5.2.1 Householder QR



717
718
719
720
721
722
723
724
725
726
727
728
729
730
 
# File 'lib/extendmatrix.rb', line 717

def self.QR(mat)
  h = []
  a = mat.clone
  m = a.row_size
  n = a.column_size
  n.times do |j|
    v, beta = a[j..m - 1, j].house
    h[j] = Matrix.diag(Matrix.robust_I(j), Matrix.I(m-j)- beta * (v * v.t))
    
    a[j..m-1, j..n-1] = (Matrix.I(m-j) - beta * (v * v.t)) * a[j..m-1, j..n-1]
    a[(j+1)..m-1,j] = v[2..(m-j)] if j < m - 1 
  end
  h
end

.toHessenberg(mat) ⇒ Object

Householder Reduction to Hessenberg Form



771
772
773
774
775
776
777
778
779
780
781
782
783
 
# File 'lib/extendmatrix.rb', line 771

def self.toHessenberg(mat)
  h = mat.clone
  n = h.row_size
  u0 = Matrix.I(n)
  for k in (0...n - 2)
    v, beta = h[k+1..n-1, k].house #the householder matrice part
    houseV = Matrix.I(n-k-1) - beta * (v * v.t)
    u0 *= Matrix.diag(Matrix.I(k+1), houseV)
    h[k+1..n-1, k..n-1] = houseV * h[k+1..n-1, k..n-1]
    h[0..n-1, k+1..n-1] = h[0..n-1, k+1..n-1] * houseV
  end
  return h, u0
end