Matrix Multiplication: 3x3 and 3x1

Formula:

| a11 a12 a13 |    | b1 |    | a11*b1 + a12*b2 + a13*b3 |
| a21 a22 a23 | x | b2 | = | a21*b1 + a22*b2 + a23*b3 |
| a31 a32 a33 |    | b3 |    | a31*b1 + a32*b2 + a33*b3 |

For arrays:

| a11 a12 a13 |      | a[0][0] a[0][1] a[0][2] |
| a21 a22 a23 |  =  | a[1][0] a[1][1] a[1][2] |
| a31 a32 a33 |      | a[2][0] a[2][1] a[2][2] |

| b1 |    | b[0] |
| b2 | = | b[1] |
| b3 |    | b[2] |

| c1 |    | a11 a12 a13 |    | b1 |    | a[0][0]*b[0] + a[0][1]*b[1] + a[0][2]*b[2] |
| c2 | = | a21 a22 a23 | x | b2 | = | a[1][0]*b[0] + a[1][1]*b[1] + a[1][2]*b[2] |
| c3 |    | a31 a32 a33 |    | b3 |    | a[2][0]*b[0] + a[2][1]*b[1] + a[2][2]*b[2] |

Code:   

c[0] = a[0][0]*b[0] + a[0][1]*b[1] + a[0][2]*b[2]
c[1] = a[1][0]*b[0] + a[1][1]*b[1] + a[1][2]*b[2]
c[2] = a[2][0]*b[0] + a[2][1]*b[1] + a[2][2]*b[2]

Matrix Inverse - 3x3

Operations of matrices of 3x3 are very common in day to day applications. Because the dimensions are already known, its better to avoid using a for-loop because of the extra computation involved in finding the subscript values.

Following is a quick formula for the inverse of a 3x3 matrix (implemented as a 2D array).

Formula

The inverse of a 3x3 matrix:
| a11 a12 a13 |-1                   |   a33a22-a32a23  -(a33a12-a32a13)   a23a12-a22a13   | 
| a21 a22 a23 |    =  1/DET *  | -(a33a21-a31a23)   a33a11-a31a13  -(a23a11-a21a13) |
| a31 a32 a33 |                      |   a32a21-a31a22  -(a32a11-a31a12)   a22a11-a21a12   |

where DET is the determinant of the matrix, i.e.

DET  =  a11(a33a22 - a32a23) - a21(a33a12 - a32a13) + a31(a23a12 - a22a13)

For 2D array

Moving on from matrices to 2D arrays

| a11 a12 a13 |        | mat[0][0] mat[0][1] mat[0][2] |

| a21 a22 a23 |   =   | mat[1][0] mat[1][1] mat[1][2] |

| a31 a32 a33 |        | mat[2][0] mat[2][1] mat[2][2] |

and,

| a11 a12 a13 |-1     | inv[0][0] inv[0][1] inv[0][2] |

| a21 a22 a23 |   =   | inv[1][0] inv[1][1] inv[1][2] |

| a31 a32 a33 |        | inv[2][0] inv[2][1] inv[2][2] |

Hence for code, the assignments are:

inv[0][0] = mat[2][2] * mat[1][1] - mat[2][1] * mat[1][2]

inv[0][1] = mat[2][1] * mat[0][2] - mat[2][2] * mat[0][1]

inv[0][2] = mat[1][2] * mat[0][1] - mat[1][1] * mat[0][2]

inv[1][0] = mat[2][0] * mat[1][2] - mat[2][2] * mat[1][0]

inv[1][1] = mat[2][2] * mat[0][0] - mat[2][0] * mat[0][2]

inv[1][2] = mat[1][0] * mat[0][2] - mat[1][2] * mat[0][0]

inv[2][0] = mat[2][1] * mat[1][0] - mat[2][0] * mat[1][1]

inv[2][1] = mat[2][0] * mat[0][1] - mat[2][1] * mat[0][0]

inv[2][2] = mat[1][1] * mat[0][0] - mat[1][0] * mat[0][1] 

DET =   mat[0][0]*inv[0][0] + mat[1][0]*inv[1][0] + mat[2][0]*inv[0][2]

Forgotten rules of C/C++: Part 1

Following is a list of important points people find very convenient to forget. This is the first article of a series

·   For bitwise operations, operand is promoted to "int" before evaluation.

unsigned char I = 0x80;
printf("%d", i<<1 nbsp="nbsp">  256

·   printf(5 + "intelligent");  => “ligent”

      Number specifies displacement to string pointer. This is the same as doing…

char *s = "intelligent";
s += 5;
printf("%s",s);

·    In a switch statement, initializations are allowed in the beginning, but they are NOT EXECUTED. The control is passed directly to an executable statement, i.e. matching case statement.

switch(1)
{
     printf("hello");                         => NOT PRINTED
     case 1:printf("case 1");break;
     case 2:printf("case 2");break;
}

·   The ++ operator means ``add one to a variable'' and DOES NOT work with constants.

int i = ++ 3 ;
printf("%d", i);                              =>  GARBAGE VALUE

·   Static arrays are constant! The base address cannot be modified. Any pointer arithmetic that attempts to do so causes a compilation error.

int arr[ 10 ] ;                     => “arr” is a constant. It is defined to be the address, &arr[ 0 ].

·   Array pointer logic for an array, “int a[10][10];”

      a+1
=> a[1]
=> &a[1][0]

·    In pointer arithmetic, addition and subtraction are valid operations, (as long as they don’t try to change the base address of the pointer) but pointer division and pointer multiplication are INVALID.

Code Snippet - Summed Area Table

SUMMED AREA TABLE
Using the method described here, I have written the following code to calculate a summed area table. A sample image table of 5x5 dimensions has been assumed for simplicity. The code snippet and its results are given below.

CODE
// assumed height and width of the input table
#define height 6
#define width 6

// input matrix - 5x5
long matrix[ height - 1][width -1] = {{5,2,3,4,1},{1,5,4,2,3},{2,2,1,3,4},{3,5,6,4,5},{4,1,3,2,6}};
// output matrix - 6x6
long sat[height][width];

void sat_matrix(){
 // formula variables
      int a=0, b=0, c=0, m=0;
      // matrix traversal loop for calculating the SAT
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
                     // following code picks up array elements within bounds and picks "zero"
                     // for values outside bounds.
a = (i-1>=0)?sat[i-1][j]:0;
b = (j-1>=0)?sat[i][j-1]:0;
c = ((i-1>=0)&&(j-1>=0))?sat[i-1][j-1]:0;
m = ((i-1>=0)&&(j-1>=0))?matrix[i-1][j-1]:0;
                      // ACTUAL FORMULA FOR SUMMED AREA TABLE
sat[i][j] = m + a + b - c;
}
}
}

PROCEDURE:
Use the function as it is and write supporting code. The code written was compiled using g++ compiler in cygwin environment

OUTPUT:

Summed Area Table

Definition

Summed Area Table is both an algorithm and data structure used in reference with the concept of Integral images. SAT is a name used to refer to both the method and the result of conversion of an image to an integral image.

SAT – The Algorithm

Summed Area Table (or Integral Image) is an algorithm applied on a 2-dimensional array of elements. It’s a simple, single pass algorithm to obtain the integral image values from the given pixel values of image.

SAT – The Data Structure

SAT also refers to the table of values generated after applying the conversion to Integral Image. This table of values is then used as input for improving the speed of more complicated operations.


Procedure
The algorithm takes as input, a table of order nxn and returns a table of order (n+1)x(n+1). The fundamental operation done here is to apply the following formula;


I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)
Where, 
  i(x,y) = Element of image array i[x][y]
  I(x,y) =  Element of integral image array I[x][y]


The procedure can be better explained by the following code snippet

Integral Image

Definition

An Integral image is one that is conducive to frequent summation operations. Any rectangular subset of such an image can be evaluated in constant time. Such an image is achieved by converting its pixel values to a SAT (summed area table) by simple interpolation of known pixel values.

An Integral Image is defined as,

I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)

Where,

i(x,y) = Pixel value of base image at (x,y)

I(x,y) = Pixel value of integral image at (x,y)

How this helps

Once the integral image has been calculated, the sum of any rectangular subset can be calculated by just 4 array points, i.e.,

SUM = (Bottom right + top left – top right – bottom left)

Application

Despite being a very simple transform (mathematically), calculating integral images helps perform many complex calculations with ease. Processing an integral image is much simpler than processing a normal pixel table. Hence the prerequisite step of several image processing algorithms is the conversion to an integral image.

Integral Images are useful for calculating HAAR wavelets, gradients, means and other measures. These are also used in image blurring, face recognition and other similar algorithms.

The concept of integral images can be easily extended to continuous domain (using limits) and multidimensional images. Also, the nature of summation operations can be modified to suit the algorithm, such as summation over non rectangular areas.

Method

Integral images are calculated using the following method.

How I Installed CUDA on my PC

Platform: Windows 7 (32 bit)

CUDA Hardware: None yet, will use simulator till then.

1 Prologue

      Before you start, get a clear idea about CUDA and its features from here.

2 Installation

2.1 Software setups

Basic step is to download the latest SDK and to choose an appropriate Toolkit according to your hardware’s compute capability. Download links are given here.

If you don’t have the hardware yet, you will need to use the emulator to compile and run programs (covered here). The emulator was however deprecated in the 3.x updates. Hence you need to download CUDA Toolkit 2.3 from here.

2.2  Installation Steps

Thankfully for windows, no post-installation configuration is required. Just run the setups and install-away.

3      Choose your language: C\C++

3.1 C++

Visual Studio will be used for C++ development for convenience. Express versions can be downloaded and registered for no cost. Or check with your countries IEEE MSDNAA alliance website if you are a member.

(If other, better IDE’s now have compatibility with CUDA; please notify me in the comments)

Downloads:

 Visual Studio2008

CUDA VS WIZARD (Win 32) 2.00 (or latest version)

  

3.2 C

C is best used on Linux or a native Linux environment. For windows users, the limited capability offered by the command line is satisfactory in this context. No separate setup is needed as the environment variables are already in place and CUDA’s compiler; nvcc can be invoked from the command line directly.

3.3 Java

I am, as of now, not committed to the idea of using Java for CUDA programs. But for reference, please go to this site.

After these steps have been completed, you are now ready to compile and execute CUDA programs.

CUDA Emulator

The CUDA emulator is a software that duplicates (or emulates) the functions of a computer system with a CUDA-enabled card in a computer system with no such hardware, so that the emulated behavior closely resembles the behavior of the real system. This software package is mainly aimed to empower developers and students who do not have access to Nvidia GPU's.


Initially, the CUDA Toolkit came with an emulator "built into" the CUDA compilor; "nvcc". Later, from versions after 3.0, the emulator was dropped. The last version that supports the emulator is v2.3, and can be downloaded from the CUDA Toolkit archives here.


But thankfully, several third parties have contributed to produce several emulation options that will be listed in this space shortly.

What is CUDA?

The article serves as a prologue for beginners. Please note that this is a primer not a tutorial, tutorials will follow.

CUDA (Compute Unified Device Architecture) is a parallel processing architecture that gives developers the ability to process their applications on CUDA-enabled processors. Basically it provides “us” the ability to process parallely, not just the CPU. The CPU and GPU are treated as separate devices with their own address space and memory. Actual processing is delegated to the GPU via a costly memory transfer between the CPU and GPU. After the job is finished, the result is transferred back to CPU for output to user.

One of the main implications of CUDA is that algorithms can now be split and processed on multiple processing units (called CUDA cores) to achieve excellent performance. This feature promises to add some viability to otherwise redundant or unfeasibly slow algorithms.

CUDA cores are processing units with their own memory as well as access to a shared global memory of the GPU. Each of these “cores” is a powerful processor in itself and can execute many threads collectively. Threads are the smallest execution unit of a program and are created\coded to suit the algorithm being processed.

In terms of software, parallel processed code is written using extensions to C\C++\Java, the favorite among developers being “extended C” due to its simplicity. Other languages can\will support CUDA via separately written libraries (for example: jCUDA for Java).  

In terms of hardware, CUDA needs to be run using CUDA-enabled GPU’s. These devices come with hundreds of CUDA cores, a fundamental requirement to run code written for CUDA. NVIDIA provides a list of all CUDA-enabled GPU’s here.

For a detailed theoretical explanation, you may now move on to Wikipedia (here) and then to NVIDIA Documentation provided with the SDK.

Using UML in Projects

Well the obvious question by any fresh student\developer is not how but WHY??? UML is used extensively in project development as a general programming practice, where you pictorially represent your entire project as a series of diagrams.


What is UML?
Seriously if you're still searching then I'd suggest Wikipedia. the most apt definition i found was:

The Unified Modeling Language (UML) is a standard  language for specifying, visualizing, constructing, and documenting the artifacts of software systems, as well as for business modeling and other non-software systems. The UML represents a collection of best engineering practices that have proven successful in the modeling of large and complex systems.

Now lets proceed to why we as students\developers should use it more often.


1) Everyone needs a plan
Thinking of starting without a plan? Well we are not cowboys, nor are we experienced that much, a plan will certainly help keep track of project progress. Also, a well structured plan can be verified, evaluated, and improved in the very initial stages without even having to make those obvious mistakes. Besides this the diagrams let you know exactly where you are and what you need to do next.


2) Ease of understanding
Software projects tend to get lengthy and boring. Class Diagrams will definitely help understand the project code better than a hundred page source-code booklet. UML helps you show the scope, depth and size of the project in simple diagrams. Any level of detail can be incorporated into the pictorials to ease understanding. 


3) Explain to "others"
It is simple to show how a project operates or how to proceed while making it using Use-case diagrams. Others simply have to put themselves in place of the "actor" and they have a plan of action that tells them how to operate.


4) Document Assets
Any software requires good documentation to support it. Both User Manuals and Developer manuals mark the beginning of a support and maintainance relationship that must continue long after sale, both for corporate and open source products. UML diagrams in documentation bring both transparency and clarity and reduces dependence on rather obtuse source code.


5) Re-Usability
Any reboot\restart\retry will require a new approach firmly rooted to the last one. Hence the use of UML retains the very essence of that process used. Also, it is pretty simple to edit existing models and modify them to match new requirements.


6) Universal
UML standards are universally accepted. People might not know the programming language used or whether it was object oriented or procedure centric but they definitely will understand the UML part of your documentation.


7) Further Development
Models can be isolated, segmented, and edited individually, allowing for branching into several projects. Large projects can be decomposed and utilized by many people for their applications.


Some Important Softwares(Opensource)
1) StarUML
2) ArgoUML

IEEE - AIYEHUM 2011

IEEE Bangalore is organizing AIYEHUM 2011, or The All India Young Engineers’ Humanitarian Challenge to encourage students to solve real world problems and promote their ideas by providing all necessary means to implement them. These projects will be judged on the basis of their impact on humanity and their creativity, and several other factors like sustainability and cost.

Summary of events:

• Proposals are invited from the students of India to solve Humanitarian Challenges.
• Mentors from both Industry and Academia will be provided to guide selected teams implement their ideas for about 3 months.
• The projects will be published on the IEEE Humanitarian Technology Network – www.ieeehtn.org 
• The winners to be awarded with prizes and certificates.

Eligibility:

• Challenge is open to all, both IEEE and non-IEEE members from UG/PG courses enrolled in technical colleges in India.
• Teams will have minimum of 2 to up-to 4 members.
• If a project is granted funds, teams must include an IEEE Student Member in the lead role, other team members are preferred to be IEE Student members but not mandatory. [All team members must be at least 18 years of age.].

Proposal submission:

Proposals must be submitted using the form provided on:

http://youngengineers.ieeebangalore.org/aiyehum-2011/

Important Deadlines:

Proposal submission: 01 March 2011

Notification: 10 March 2011

Initial progress report: 10 April 2011

Intermediate progress report: 30 May 2011

Final report: 01 July 2011

Please visit the Official Website  for more details...

Sourceforge.net attacked!

This was a direct attack to Open Source website sourceforge.net that hosts opensource projects made by anyone interested in making such projects. On Wednesday, the website reported exploit of several servers and fears compromise of user passwords. Hence all users have been asked to renew their passwords via the link:

https://sourceforge.net/account/registration/recover.php

Besides this, many developer-centric services were shut down to prevent data integrity. Mainly people reported that their file editing system was not working. The following services have been shut-down to prevent further damage:

* CVS Hosting
* ViewVC (web based code browsing)
* New Release upload capability
* Interactive Shell services

It was truly outrageous of some people to attack an open-source project in a world where anything else costs too much for individual PC users. Meanwhile, SF is busy identifying the attack's source.

Google Summer of CodeTM 2011

While surfing i came across this completely amazing concept by google, actually just another to add to their existing list of ideas. Eventually I also felt the need to promote this. Imagine being paid to express your coding abilities on open-source environments, i.e. to be paid stipends to work on open source programs.

An excellent opportunity for college students to gain experience on coding as well as get paid to do it, things just couldn't get better, heres an excerpt from their website.

"About Google Summer of Code

Google Summer of Code (GSoC) is a global program that offers student developers stipends to write code for various open source software projects. We have worked with several open source, free software, and technology-related groups to identify and fund several projects over a three month period. Since its inception in 2005, the program has brought together over 4,500 students and more than more than 4,000 mentors & co-mentors from over 85 countries worldwide, all for the love of code. Through Google Summer of Code, accepted student applicants are paired with a mentor or mentors from the participating projects, thus gaining exposure to real-world software development scenarios and the opportunity for employment in areas related to their academic pursuits. In turn, the participating projects are able to more easily identify and bring in new developers. Best of all, more source code is created and released for the use and benefit of all."

-http://www.google-melange.com/site/home/site

Exception Handling Basics

Basics:

• Events are abnormal activities that occur during runtime.

• Errors are rather cataclysmic; there is no recovery or handling.

• Exceptions are the unwanted problems in a program that don’t cause irrecoverable damage. Exceptions are, in effect, just errors that can be handled by guessing their occurrence in a particular section of code. They are of two types, Checked or Unchecked.

• Runtime Environment is aware of most errors, called “Unchecked” Exceptions. E.g. Division by zero, typecasting between incompatible types, etc. Handling of these unchecked exceptions is not required, i.e. they don’t have to be “caught” or “declared thrown”.

• On the other hand, “Checked” Exceptions must be caught and thrown explicitly. But in terms of functionality both are the same and no extra feature exists in either class of exceptions.

• Handling is the practice of transferring control to special functions called handlers. Code is inspected in a “try” block, exception cases are detected and caught by “catch” blocks that work to handle and neutralize the problem imposed by the exception.

Important concepts:

(mainly C++)

1. The “try” block

Any statement or group of statements capable of generating an exception should be located in a try block. Exception objects are thrown in Java. In C++, a parameter is thrown whose type is matched to a catch block.

2. The “throw” keyword

This keyword is used to literally throw a value (C++) or object (Java) that is directly sent to catch blocks for evaluation. For example, in C++ one may write

throw 1;

Now a call will be made to a catch block that has the following prototype:

            catch(int arg) {;}

3. The “catch” block

The catch block catches the exception object(Java) or data type(C++). In C++, the type of the thrown parameter is matched to the prototype of the catch block. The match found is used to handle the thrown exception. Catch blocks contain error messages or substitute code that can help avoid the exceptional case.

A single try block can have multiple catch blocks but at least one catch is necessary that can handle all possible exceptions thrown from its parent try.

A default catch block that can accommodate all types is given below. It is used for default handling code.

            catch(…) {;}

“…” is an ellipsis that indicates no type specification.

GO Programming Language

GO is a systems programming language by Google.Inc. 
The official website http://golang.org/ describes this language as simple, fast, concurrent, safe, fun, open source and what not. So far it has not been developed for the Windows platform, so if interested, it means you need the good ol' Linux.

GO is basically an OOPs based language that looks a lot like Java but personally I felt it was more like C\C++ given a lot of resources and power. What differentiates it from Java is basically a heavy use of low level features, which anyone would have started missing if they used Java for too long. Three instruction sets for amd86, x86\x86-32, ARM are supported.

Installation is easy if you have ever installed Java before, because it involves setting environmental variables. Programs have a ".go" extension and when compiled the extension changes to name of current commpilor, eg. "file.6". The Linked files are named as ".out"

The main comparisons to C++\Java are implicit Garbage-collection, use of imports through package files, no implicit type-conversions (type-casts are used, called conversions), etc. Also, unlike Java, Pointers ARE supported, but pointer arithmetic is not. Pleas visit the mentioned website for details...

Stack Template Class

The stack template I made. Overflow conditions have been skipped as they practically dont occur on modern PC's.


Please specify class T when you declare the object, for example for 'int',
stack  < type_name > stack_object_name;

template < class T >

class stack

{

struct node

{

T data;

struct node *next;

}*top;

public:

stack()

{

  top=NULL;

}

void push(const T & value)

{

  struct node *ptr;

  ptr=new node;

  ptr->data=value;

  ptr->next=NULL;

  if(top!=NULL)

  ptr->next=top;

  top=ptr;

  cout<<"\nNew item is inserted to the stack!!!";

  getch();

}

T pop()

{

  struct node *temp;

  if(top==NULL)

  {

  cout<<"\nThe stack is empty!!!";

  getch();

  return;

  }

  temp=top;

  top=top->next;

  T t=temp->data;

  delete temp;

  return t;

}

void show()

{

        if(top==NULL)

   {

  cout<<"\nThe stack is empty!!!";

  getch();

  return;

   }

  struct node *ptr1=top;

  cout<<"\nThe stack is\n";

  while(ptr1!=NULL)

  {

  cout<data<<" ->";

  ptr1=ptr1->next;

  }

}

};

Queue Template

The queue template I made. Overflow conditions have been skipped as they practically dont occur on modern PC's.

Please specify class T when you declare the object, for example for 'int',

queue < type_name > queue_object_name;

template < class T >

class queue

{

   struct node{

   T data;

   struct node *next;

   }*frnt,*rear;

public:

queue()

{

                  frnt=rear=NULL;

}

void insert(const T & value)

{

   struct node *ptr;

   ptr=new node;

   ptr->data=value;

   ptr->next=NULL;

   if(frnt==NULL)

                   frnt=ptr;

   else

                   rear->next=ptr;

   rear=ptr;

   cout<<"\nNew item is inserted to the Queue!!!";

   getch();

}

T del()

{

   if(frnt==NULL)

   {

                   cout<<"\nQueue is empty!!";

                   getch();

                   return;

   }

   struct node *temp;

   temp=frnt;

   frnt=frnt->next;

   T t=temp->data;

   delete temp;

   return t;

}

void show()

{

   struct node *ptr1=frnt;

   if(frnt==NULL)

   {

                   cout<<"The Queue is empty!!";

                   getch();

                   return;

   }

   cout<<"\nThe Queue is\n";

   while(ptr1!=NULL)

   {

                    cout<data<<" ->";

                    ptr1=ptr1->next;

   }

}

};