HappyGastropod

Jacobi Iteration With Ruby

April 28 2010

When solving linear algebraic systems, it is often beneficial to use iterative methods. Iterative solvers are particularly useful when a matrix is diagonally dominant. One such iterative method that is particularly useful is Jacobi Iteration.

Given a matrix A, you first decompose it into 3 separate matrices: L, D, and U. These are the lower, diagonal, and upper sections of the matrix, respectively.

For example, let’s assume we’ve been given this matrix A:

We will then zero-out everything above and including the diagonal entries. This will give us our new L matrix.

Likewise, we’ll remove all entries below, and including the diagonal from matrix A to give us our matrix U.

Finally, we’ll zero-out all non-diagonal entries, to yield our new matrix D.

As stated previously, since A=L+D+U, we can deduce that Ax=Dx+(L+U)x. And since Ax=b, we can conclude that Dx=b-(L+U)x, which is the basis of Jacobi’s Method.

Given an estimate vector (x) (which is generally initialized to 0 if no educated guess can be provided), the next estimate is found by:

And since D is a diagonal matrix, the above equation can be rewritten in terms of the components of A and b.


So now that we understand how Jacobi Iteration works, we can write a program to do it for us! Ruby is not necessarily the best language to do this in, as these systems can often times be quite large. Compiled languages such as C++ are going to converge much faster.

To start out, we’re going to write a method that takes in our Matrix A, our right hand size b, the number of times we’d like to iterate, and our initial guess.

def jacobi_iteration(A, b, iterations, guess |= 0)

From here, we will need to fire up our estimate vector x. We’ll initialize its first element to be the initial “guess,” and the remaining entries to be 0.

  # Initialize
  x = Array.new(A.size)
  x[0] = guess
  1.upto(A.size) do |i|
    x[i] = 0
  end

Finally, we implement the equation above as nested loops to iteratively try to converge to a solution.

  0.upto(iterations-1) do |its|
    0.upto(A.size) do |i|
      sum = 0
      0.upto(A.size) do |j|
        unless j==i
          sum = A[i][j] * x[j]
        end
      end
      x[i] = 1.0/A[i][i] * (b[i] - sum)
    end
  end
end

NGINX Config: http to https

April 18 2010

I’ve recently installed a self-signed certificate on my server just for the login areas for my own peace of mind. After having a rough time trying to handle the redirection from Rack itself, I opted to do this through NGINX, which turned out to be quite a bit easier. Below is a snippet of the virtual host I used:

server {
            listen   80;
            server_name happygastropod.com;
            rewrite ^/admin https://happygastropod.com/admin permanent;
}

It’s pretty self explanatory. Takes a regular expression of the path you’d like to redirect, and simply redirect it off to the https alternative. Enjoy.

C++ Virtual Class Inheritance

March 11 2010

Virtual Class Inheritance is something many people (myself included) have a difficult time wrapping their heads around initially. It can be a useful tool, so I’m going to try to explain it a little bit here.

Let’s suppose we have a Garden with different kinds of plants growing in it (how original.) We can start out by creating a very general class called Plant. With generalization in mind, we can only specify attributes and functions that all plants share.

class Plant
{
public:
  virtual ~Plant();
  virtual Plant* clone() const = 0;
	
  string getColor() const
  {
    return color;
  }
	
  int getHeight() const
  {
    return height;
  }
	
  void grow(int n)
  {
    height = height + n;
  }
	
  virtual bool isRipe() const = 0;

protected:
  string color;
  int height; //inches
};

You’ll notice that the isRipe() function has the keyword “virtual” next to it, and it’s set to equal 0. This defines a virtual function that is not defined in the base class. There is no way of knowing whether a plant is ripe without knowing what kind of plant it is. So we will define this function in the sub-classes.

You should also notice that the destructor is virtual. This is because there may be additional private members in the sub classes that this base class doesn’t know about. Not declaring the destructor as virtual would likely lead to memory leaks.

We can now start coming up with plants we’d like to put in our garden. For this example, I’ve created Carrot, Potato, and Eggplant classes. Each of these classes has a unique implementation of the isRipe() function.

class Carrot : public Plant
{
public:
  Carrot()
  {
    color = "Orange";
    height = 0;
  }
	
  virtual bool isRipe() const
  {
    return height >= 10;
  }
};

class Potato : public Plant
{
  Potato()
  {
    color = "Brown";
    height = 0;
  }
	
  virtual bool isRipe() const
  {
    return height >= 7;
  }
};

class Eggplant : public Plant
{
  Eggplant()
  {
    color = "Purple";
    height = 0;
  }
	
  virtual bool isRipe() const
  {
    return height >= 13;
  }
};

Nothing too fancy here, but you can see that each class has a different (albeit simple) way of checking if the plant is ripe.

Moving forward, we can implement our Garden class. The Garden class is essentially a collection of plants. We’re going to store our plants in a vector. Well, really we’re storing pointers to our plants in a vector. Since there is no way of knowing how much memory each plant will use, we cannot store plants directly. We must store pointers to the plants, which could be of type potato, eggplant, or carrot.

class Garden
{
public:
  Garden();
  addPlant(Plant* p)
  {
    plants.push_back(p)
  }
	
  harvest()
  {
    for(int i=0; i<plants.size(); i++)
    {
      if(plants[i]->isRipe())
      {
        plants.delete(plants.begin() + i) //Remove ripe plants from garden
      }
    }
  }

private:
  vector<*Plant> plants;
};

And there you have it. We have a very simple, and fairly useless e-garden. I’ll leave it up to you to code the army of slugs and snails to destroy it. Oh, and be sure to make a virtual class gastropod.