Wednesday, October 15, 2014

Professional UI – Html Class (Part 2)

It is really nice to have a html page inside the application, it gives a professional dress, it links many URLs, like web sites, documentation, video and other useful information.

This page should be interactive in order to show dynamic information. That is why it needs to be created every time it is showed.



I this blog a pointed out everything (source code) that can be useful and shared for other programmer. I define a category called “Toolbox” in order to give more useful instrument, often necessary to provide a good program. That is why I have projected this class. 

We all know that HTML Language is the standard markup language used to create web pages. A HTML document is a simple text file, written in the form of HTML elements consisting of tags enclosed in angle brackets like in figure below.


So my class, works in order to manipulate this kind of documents, but how?

First of all the user have to create a HTML document template, that will have the desired layout structure with styles and some static contents and dynamic as well. 


Figure 1: Html Template File

Figure 2: How the template appears

How the dynamic content will be inserted will be documented ahead. 
The class will take this template, will manipulate the content that will became the definitive version showed into the application.
I summarize the specifics:

Input Elements:
  • HTML Template document
  • TagB and values: list of elements to replace run-time in template file.
  • Templates location: source directory where the templates are stored.
  • Report destination: where the elaborated copy will be produced.
  • Images location: the directory where images can be stored. It can manage image as well.

Output Element:
  • HTML Report or definitive HTML file manipulated.

Basic functions:
  • Loading the template file into a string list or collection.
  • Manipulation of this list.
  • Save the list into a new file Report.
  • Other support methods.

HTML Template document manipulation

One thing I omitted! This is how I will manage this file, in order to produce a new one.

Well, as we know Html uses tags closed into < and > brackets, so I have decided to introduce new custom tags but closed between curly brackets {}. This tags have significance only for the program or programmer. These tags will be replaced run-time by our application.

For example if I insert into my Html template {ref_version} when the program will find this tag then it will replace it with a string about the program version (eg. ManipulateHtml ver 1.0.1).

For convention, I called these tags TagB (Tags between Braces or Curly brackets).

So, my class has to:
  • Import the html template file.
  • Analyze it in order to find the TagB.
  • Replace these TagB with some values.
  • Produce a new html document.
The program will show this final html document.

 
public class HtmlReportBase
{
    //===============================================================================
    #region Variables Declarations
    protected string mTemplateDir;
    public string TemplateDir { get { return mTemplateDir; } }
    protected string mReportDir;
    public string ReportDir { get { return mReportDir; } }
    protected string mReportFile;
    public string ReportFile { get { return mReportFile; } }
    protected string mTemplateFile;
    public string TemplateFile { get { return mTemplateFile; } }
    protected string mImagesDir;
    public string ImagesDir { get { return mImagesDir; } }

    protected StringCollection mHtmlFile;
    protected FieldsItem myFieldList = new FieldsItem();
    protected TablesItem myTableList = new TablesItem();
    #endregion


The first part of our class defines the member variables and properties. In particular, the last three are more interesting.

  • mHtmlFile: contains all html original template text lines.
  • myFieldList: is a list of TagB to replace with their correspondent new values.
  • myTableList: Is a list of TagB to replace and their HtmlTable values. It is an improvement I did to this class, in order to manage also Html tables run-time.

First Step

 
// Constructor
//

// es. c:\myapp\print\report\
// es. c:\myapp\print\template\
// es. c:\myapp\print\images\
public HtmlReportBase(string sReportDir, string sTemplateDir, string sImagesDir)
{
    this.Initialize(sReportDir, sTemplateDir, sImagesDir);
}

Setup the involved directories.
 
// 
// Load the template into the mHtmlFile string collection.
//
// aTemplateFileNameOnly: File Name only! The Directory is already specified calling Initialize()
public void LoadTemplate(string aTemplateFileNameOnly)
{
    try
    {
        mTemplateFile = Path.GetFileName(aTemplateFileNameOnly);
        string sTemplate = (mTemplateDir + "\\" + mTemplateFile);

        Utility.LoadFileIntoCollection(sTemplate, out mHtmlFile);
    }
    catch (Exception ex)
    {
        Utility.ShowError("ReadTemplate(): " + ex.Message);
    }
}

Load html template into mHtmlFile string collection.


Second Step

Decide the TagB list to replace, and populate it.


 
// 
// Add and Item into the list (TagB, Value)
//
public void AddItem(string aFieldName, string aFieldValue)
{
    try
    {
        FieldItem oItem = new FieldItem("{" + aFieldName + "}", aFieldValue);
        myFieldList.Add(oItem);
    }
    catch (Exception ex)
    {

        Utility.ShowError("AddItem(): " + ex.Message);
    }
}


Third Step

Replace the TagB with values

 
// 
// Search the TagB into the html file and replace these with the FieldList values
//
public void ReplaceTags()
{
    try
    {
        int i, j;
        string s = "";

        for (i = 0; i < (mHtmlFile.Count); i++)
        {
            for (j = 0; j < myFieldList.Count; j++)
            {
                if (mHtmlFile[i].Contains("{"))
                {
                    s = mHtmlFile[i];
                    mHtmlFile[i] = mHtmlFile[i].Replace(myFieldList[j].FieldName, myFieldList[j].Value);
                    if (s != mHtmlFile[i])
                        break;
                }
            }
        }
        ReplaceTables();
    }
    catch (Exception ex)
    {
        Utility.ShowError("ReplaceFields(): " + ex.Message);
    }
}

Fourth Step

Generate the final document

 
// 
// Generate the final Report
//
public void WriteReport(string aReportFileNameOnly)
{
    try
    {
        mReportFile = aReportFileNameOnly;
        string sFileName = (mReportDir + "\\" + mReportFile);
        if (File.Exists(sFileName))
        {
            File.Delete(sFileName);
        }
        Utility.SaveCollectionIntoFile(ref mHtmlFile, sFileName);
    }
    catch (Exception ex)
    {
        Utility.ShowError("WriteReport(): " + ex.Message);
    }
}





At the end I have created an example, that loads the template and shows on a grid all the TagB contained in this document. The user can complete the grid with the values to replace.


 
private void btnCreate_Click(object sender, EventArgs e)
{
    foreach (DataGridViewRow row in grdTags.Rows)
    {
        if (row.Cells[1].Value != null)
            moHtml.AddItem(row.Cells[0].Value.ToString(), row.Cells[1].Value.ToString());
    }

    moHtml.ReplaceTags();
    moHtml.WriteReport("Index.html");

    Utility.BrowseTo(moHtml.ReportDir + "\\" + moHtml.ReportFile);
}








Tuesday, September 16, 2014

Professional UI – The Recent List (Part 1)

In this Post I will start to talk about how to project a Professional UI and what it should be useful to develop in order to maintain and create it.

In figure below you can see an UI that I have projected for GSLab, a computational program used to project substation grounding grid.



I toke inspiration by Visual Studio Interface, Microsoft Word and other common application on commercial market. What works for many it should work for few. In this UI it is possible to find many useful features.


  • A Toolbar (Ribbon Style), with items  that appear and disappear it depends on program status.
  • A Status bar that resume all main selections, program status, some user advice
  • A Left Panel where the user input parameters
  • A Start Page that works like a web browser.


Let's concentrate on Start Page.





We can distinguish three areas: Every one of which is very useful for the user’s experience.

Start: Gives to users the mains starting functionalities.

Recent: The List of last used projects.

Html: Area with useful information and links.

Before create this page, we have to create the separate functionalities that it grasp together. These functionalities could be accessed from different parts of the program. For example the "Recent List".

The “Recent List”


What is "the Recent List"?

Well. It is quite trivial to explain it and maybe it is not necessary to do that, but I will try anyway. First of all, it is a list, where we can find a maximum number of project references. This list has a project reference as unique key, this is because a project reference can appear just one time.

A project reference can be seen as a file, a name, a title, doesn't matter. In this particular case a Project Name.

Furthermore, the top item of the list is the last inserted. If an element already exist into the list when we try to insert it, then it is moved on top.


Example:

Recent List - State 1
1
Project C
2
Project B
3
Project F

Three projects inserted.

We Add a New project Project Z

Recent List - State 2
1
Project Z
2
Project C
3
Project B
4
Project F

Four projects inserted.

We Add again a project Project C

Recent List - State 3
1
Project C
2
Project Z
3
Project B
4
Project F

Four projects inserted.

Now it is clear how it works and we can start to make a class that do that.

Where to store these information?

Also in this case there are many possibilities I decide to use the Windows Registry.

 
public class FilesHistory: RegistryBase
{
const int MAX_ELEMENTS = 10;
List moFiles = new List(MAX_ELEMENTS);

public List Files

public FilesHistory(string sCompany, string sApplicationName)

public void Save()

public void Load()

public void Add(string sFileName)
}

The class definition it is very easy as it should be. It inherited from another class (RegistryBase) that it is not here explained but also easy to create.

A single property “Files” that contains the elements, and three methods: Save, Load, Add.

  • Save, as the name said, saves a list into the registry.
  • Load, loads from the registry and populate the list.
  • Add, append a new item into the list.

The Add() method use a private method Append() as well.

It removes the element instance if exist then append it. If a maximum number of elements is reached the last element is removed.

 
public void Add(string sFileName)
{
moFiles.Remove(sFileName);
Append(sFileName); //FIFO

if (moFiles.Count == MAX_ELEMENTS)
moFiles.RemoveAt(moFiles.Count-1);
}

The Append() method use a temporary list, where inserts the new element at the top, and then append all the old list.

 
private void Append(string sFileName)
{
List moFilesNew = new List(MAX_ELEMENTS);

moFilesNew.Add(sFileName);
foreach (string item in moFiles)
{
moFilesNew.Add(item);
}

moFiles.Clear();
moFiles.AddRange(moFilesNew);
}

Lets check the other two methods Save() and Load():

 
public void Save()
{
for (int i = 0; i < MAX_ELEMENTS; i++)
{
if (i < moFiles.Count)
Write("Main", "File" + i.ToString(), moFiles[i]);
else
Write("Main", "File" + i.ToString(), "");
}
}

public void Load()
{
for (int i = 0; i < MAX_ELEMENTS; i++)
{
string s = Read("Main", "File" + i.ToString());
if (s != "")
moFiles.Add(s);
}
}

As you can see these two methods uses Write(), and Read() methods inherited from the base class RegistryBase.

Ready to use

Now you are ready to use this class

Declaration:

FilesHistory HistoryFiles = new FilesHistory("MyCompany", "AppID");

The constructor parameters are the keys used for registry storing.

Starting the Application, the list is loaded:

HistoryFiles.Load();

Populate a menu list:

 
private void RefreshMenuHistory()
{
    mnuHistory.ClearLinks();
           

    for (int i = 0; i < moApp.HistoryFiles.Files.Count; i++)
    {
        BarButtonItem bt = new BarButtonItem();
        string[] lInfo = moApp.HistoryFiles.Files[i].Split('|');

        try
        {
            bt.Caption = lInfo[1];
            bt.Hint = "Dir: " + lInfo[0];
            bt.Tag = i;

            if (Directory.Exists(lInfo[0] + lInfo[1]))
            {
                mnuHistory.AddItem(bt);
                bt.ItemClick += bt_ItemClick;
            }
            else
                moApp.HistoryFiles.Files.RemoveAt(i);
        }
        catch (Exception)
        {
            moApp.HistoryFiles.Files.RemoveAt(i);
        }
    }         
}

In this case, if a file does not exist the item is removed from the list.

Add new items on the list, when you open a project:

 
HistoryFiles.Add(ProjectsDir + "|" Project.ProjectName);
HistoryFiles.Save();


I end my explanation here, for the moment you have to enjoy.

Wednesday, May 21, 2014

Improve Matrices Operations Speed (Part 2)

This new post will describe, how to invert a matrix and which are the best methods. As mentioned in “How to Solve” paragraph, the conventional Algorithm for the inversion between matrices is the LU decomposition. This method is quite expensive in terms of speed but I know there is a parallel version too. I have tried to study it, but I am sorry, I didn’t accept the challenge to rewrite LU decomposition in parallel version, it needed time that I didn’t have and I am only a developer and not mathematician.

Fortunately, when I studied Strassen for multiplication there was on the book an interesting conclusion: With this “fast” matrix multiplication, Strassen also obtained a surprising result for matrix inversion.

This very intriguing phrase bring me to the following formula:

R1 = Inverse(a11)
R2 = a21 x R1
R3 = R1 x a12
R4 = a21 x R3
R5 = R4 - a22
R6 = Inverse(R5)
c12 = R3 x R6
c21 = R6 x R2
R7 = R3 x c21
c11 = R1 - R7
c22 = -R6

So what I learned was that it is possible to obtain the matrix (multiple of 2^n) inversion from some “lighter” operations. I implemented this algorithm and compared it with the Gauss Jordan one.
Comparing those two algorithms, I obtained, using my notebook, these results:

Matrices 512x512 of Complex (double, double)
GJ; 24sec
Strassen: 19sec
20% time less

Matrices 1024x1024 of Complex (double, double)
GJ; 3min 02sec
Strassen: 2min 05sec
38% time less!

Used Invertion Methods

Gauss Jordan LU decomposition


public static Complex[,] GaussJordanInvertion(Complex[,] mat, BackgroundWorker bw = null)
{
    //Gestione notifica progressione            
    int iPerc = 0;
    int iMax = mat.GetLength(0);
    int iDone = 0;

    Complex[,] res;
    res = MatrixGeneric.Create<complex>(iMax);
    res = (Complex[,])mat.Clone();

    int[,] indxc;
    indxc = MatrixGeneric.Create<int>(iMax, true); 
    int[,] indxr;
    indxr = MatrixGeneric.Create<int>(iMax, true);
    int[,] ipiv;
    ipiv = MatrixGeneric.Create<int>(iMax, true);
    Complex big;
    Complex pivinv;
    Complex dum;
    int iRow = 1;
    int iCol = 1;

    for (int i = 1; i <= iMax; i++)
        ipiv[i, 1] = 0;
    for (int i = 1; i <= iMax; i++)
    {
        big = 0;
        for (int j = 1; j <= iMax; j++)
            if (ipiv[j, 1] != 1)
                for (int k = 1; k <= iMax; k++)
                {
                    if (ipiv[k, 1] == 0)
                    {
                        if (Complex.Abs(res[j, k]) >= Complex.Abs(big))
                        {
                            big = Complex.Abs(res[j, k]);
                            iRow = j;
                            iCol = k;
                        }
                    }
                    else if (ipiv[k, 1] > 1)
                    {
                        //Error "Singular Matrix -1"
                    }
                }
        ++(ipiv[iCol, 1]);
        if (iRow != iCol)
        {
            for (int l = 1; l <= iMax; l++)
                Swap(res[iRow, l], res[iCol, l]);
        }
        indxr[i, 1] = iRow;
        indxc[i, 1] = iCol;
        if (res[iCol, iCol] == 0)
        {
            //Error "Singular Matrix -2"
        }
        pivinv = 1 / res[iCol, iCol];
        res[iCol, iCol] = 1;
        for (int l = 1; l <= iMax; l++)
            res[iCol, l] = res[iCol, l] * pivinv;
        for (int ll = 1; ll <= iMax; ll++)
            if (ll != iCol)
            {
                dum = res[ll, iCol];
                res[ll, iCol] = 0;
                for (int l = 1; l <= iMax; l++)
                {
                    res[ll, l] = res[ll, l] - res[iCol, l] * dum;
                }
            }        
    }

    for (int l = iMax; l > 0; l--)
    {
        if (indxr[l, 1] != indxc[l, 1])
            for (int k = 1; k <= iMax; k++)
                Swap(res[k, indxr[l, 1]], res[k, indxc[l, 1]]);
    }

    return res;
}

Strassen

public static Complex[,] Inverse(Complex[,] a, int iThreshold = 128)
{
    int iOriginalSize = a.GetLength(0);
    int iFmtSize = GetSize(a.GetLength(0));
    Complex[,] A = a;

    int iSize = A.GetLength(0);
    int iHalfSize = iSize / 2;

    if (iSize <= iThreshold)    {
        return GaussJordanInvertion(a);
    }

    Complex[,] A11 = null;
    Complex[,] A12 = null;
    Complex[,] A21 = null;
    Complex[,] A22 = null;

    Complex[,] R1 = null;
    Complex[,] R2 = null;
    Complex[,] R3 = null;
    Complex[,] R4 = null;
    Complex[,] R5 = null;
    Complex[,] R6 = null;
    Complex[,] R7 = null;

    Complex[,] C11 = null;
    Complex[,] C12 = null;
    Complex[,] C21 = null;
    Complex[,] C22 = null;


    A11 = GetMatrixPortion(A, iHalfSize, 1, 1);
    R1 = Inverse(A11);

    A21 = GetMatrixPortion(A, iHalfSize, iHalfSize + 1, 1);
    R2 = Mul_Strassen(A21, R1, iThreshold);

    A12 = GetMatrixPortion(A, iHalfSize, 1, iHalfSize + 1);
    R3 = Mul_Strassen(R1, A12, iThreshold);

    R4 = Mul_Strassen(A21, R3, iThreshold);

    A22 = GetMatrixPortion(A, iHalfSize, iHalfSize + 1, iHalfSize + 1);
    R5 = Subtract(R4, A22);

    R6 = Inverse(R5);

    C12 = Mul_Strassen(R3, R6, iThreshold);
    C21 = Mul_Strassen(R6, R2, iThreshold);
    R7 = Mul_Strassen(R3, C21, iThreshold);

    C11 = Subtract(R1, R7);
    C22 = Multiply(R6, -1);

    Complex[,] c = MatrixGeneric.Create<complex>(iSize, iSize);
    for (int i = 1; i <= iHalfSize; i++)
    {
        for (int j = 1; j <= iHalfSize; j++)
        {
            c[i, j] = C11[i, j];
            c[i, j + iHalfSize] = C12[i, j];
            c[i + iHalfSize, j] = C21[i, j];
            c[i + iHalfSize, j + iHalfSize] = C22[i, j];
        }
    }

    A11 = null;
    A12 = null;
    A21 = null;
    A22 = null;

    R1 = null;
    R2 = null;
    R3 = null;
    R4 = null;
    R5 = null;
    R6 = null;
    R7 = null;

    C11 = null;
    C12 = null;
    C21 = null;
    C22 = null;

    GC.Collect();

    return c;
}


Remember that the input matrix shoud be a 2^n multiple, if not! complete it with 0 and 1 on the diagonal.

Friday, May 2, 2014

Improve Matrices Operations Speed (Part 1)


In this Article I will try to show how to improve the calculation performance of typical matrix operations, eg. Multiplication or Inversion. At a beginning, I will introduce some information taken from Wikipedia but easily reached from any Algebric book that explains why this subject is quite important.

In the example proposed, I decided to use only squared matrices and starting from index 1 and not 0, so I used a method for create these (see MatrixGeneric.Create()). I used to work also with a Complex data type, but all discussions are valid also for more simple types like double or integer.

System of linear equations

From Wikipedia: In mathematics, a system of linear equations (or linear system) is a collection of linear equations involving the same set of variables. For example,


In mathematics, the theory of linear systems is the basis and a fundamental part of linear algebra, a subject which is used in most parts of modern mathematics. 

Computational algorithms for finding the solutions are an important part of numerical linear algebra, and play a prominent role in engineering, physics, chemistry, computer science, and economics. 

A system of non-linear equations can often be approximated by a linear system (see linearization), a helpful technique when making a mathematical model or computer simulation of a relatively complex system.

Matrix Equation

The vector equation is equivalent to a matrix equation of the form


where A is an m×n matrix, x is a column vector with n entries, and b is a column vector with m entries.


The number of vectors in a basis for the span is now expressed as the rank of the matrix.

How to solve: Methods

While systems of three or four equations can be readily solved by hand, computers are often used for larger systems. The standard algorithm for solving a system of linear equations is based on Gaussian elimination with some modifications. 

Firstly, it is essential to avoid division by small numbers, which may lead to inaccurate results. This can be done by reordering the equations if necessary, a process known as pivoting. Secondly, the algorithm does not exactly do Gaussian elimination, but it computes the LU decomposition of the matrix A. This is mostly an organizational tool, but it is much quicker if one has to solve several systems with the same matrix A but different vectors b.

Algorithms

The algorithms are easily founded, for example if you use to program with C or C++ a valid book is (Numerical Recipes in C written by William H., Flannery, Brian P., Teukolsky, Saul A). In general, the most critical  operations used are matrices multiplication or inversion so I will concentrate my attention in this way. 

I have created a Class dedicated to wrap all these methods:

public static class MatrixComplex

Multiplication

The multiplication is quite easy, it is a simple three nested loops, like these:

public static Complex[,] Multiply(Complex[,] a, Complex[,] b)
{
    int  iSize = a.GetLength(0);
    Complex[,] res = MatrixGeneric.Create<complex>( iSize, iSize);
    for (int row = 1; row <= iSize; row++)
    {
        for (int col = 1; col <= iSize; col++)
        {
            for (int i = 1; i <= iSize; i++)
            {
                res[row, col] += a[row, i] * b[i, col];
            }
        }
    }
    return res;
}

The problem with this kind of operation is that it has n^3 complexity, that means that with a large matrix it can take a lot of time, too much! For this reason there will be some possible options: the two that I considered for comparisons are Strassen Method and Parallel Computation.

Strassen Method 

In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. It is faster than the standard matrix multiplication algorithm and is useful in practice for large matrices, but would be slower than the fastest known algorithm for extremely large matrices. (Wikipedia)

The complexity reached from Strassen Method is 2^2.8074 that means a lot of time less than standard method.

By the way this method is quite expensive in terms of memory, it uses many temporary smaller matrices and the input matrices must be 2^n squared matrix. So, if your input matrices are sized differently these must have their dimensions expanded to the next power of 2, which results in storing up to four times as many elements, and the seven auxiliary matrices each contain a quarter of the elements in the expanded ones.

In C# I suggest to compile in x64 (64bit), or looking for some trick in order to use the max memory size in x86 (32bit). (.NET Out Of Memory Exception - Used 1.3GB but have 16GB installed).

Strassen algorithm is a recursive method. It can be customized, a little, so you can try different variations to check the performances.

This is a C# version:

public static Complex[,] Strassen(Complex[,] a, Complex[,] b, int iThreshold = 128)
{
    int iSize = a.GetLength(0);
    Complex[,] c = MatrixGeneric.Create<complex>(iSize);
    int iNewSize = iSize / 2;

    if (iSize <= iThreshold) 
    {
        c = Multiply(a, b);
        return c;
    }

    Complex[,] A11 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] A12 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] A21 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] A22 = MatrixGeneric.Create<complex>(iNewSize);

    Complex[,] B11 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] B12 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] B21 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] B22 = MatrixGeneric.Create<complex>(iNewSize);

    Complex[,] C11 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] C12 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] C21 = MatrixGeneric.Create<complex>(iNewSize);
    Complex[,] C22 = MatrixGeneric.Create<complex>(iNewSize);

    Complex[,] M1 = null;
    Complex[,] M2 = null;
    Complex[,] M3 = null;
    Complex[,] M4 = null;
    Complex[,] M5 = null;
    Complex[,] M6 = null;
    Complex[,] M7 = null;
    Complex[,] AResult = null;
    Complex[,] BResult = null;
                      
    for (int i = 1; i <= iNewSize; i++)
    {
        for (int j = 1; j <= iNewSize; j++)
        {
            A11[i, j] = a[i, j];
            A12[i, j] = a[i, j + iNewSize];
            A21[i, j] = a[i + iNewSize, j];
            A22[i, j] = a[i + iNewSize, j + iNewSize];

            B11[i, j] = b[i, j];
            B12[i, j] = b[i, j + iNewSize];
            B21[i, j] = b[i + iNewSize, j];
            B22[i, j] = b[i + iNewSize, j + iNewSize];
        }
    }

    AResult = Sum(A11, A22);
    BResult = Sum(B11, B22);
    M1 = Strassen(AResult, BResult); 

    AResult = Sum(A21, A22);              
    M2 = Strassen(AResult, B11);       

    BResult = Subtract(B12, B22);              
    M3 = Strassen(A11, BResult);       

    BResult = Subtract(B21, B11);           
    M4 = Strassen(A22, BResult);       

    AResult = Sum(A11, A12);           
    M5 = Strassen(AResult, B22);       

    AResult = Subtract(A21, A11);
    BResult = Sum(B11, B12);             
    M6 = Strassen(AResult, BResult);    

    AResult = Subtract(A12, A22);
    BResult = Sum(B21, B22);             
    M7 = Strassen(AResult, BResult);     

    AResult = Sum(M1, M4);
    BResult = Subtract(M7, M5);
    C11 = Sum(AResult, BResult);

    C12 = Sum(M3, M5);

    C21 = Sum(M2, M4);

    //C22 = M1 + M3 - M2 + M6;
    AResult = Sum(M1, M3);
    BResult = Subtract(M6, M2);
    C22 = Sum(AResult, BResult);

    for (int i = 1; i <= iNewSize; i++)
    {
        for (int j = 1; j <= iNewSize; j++)
        {
            c[i, j] = C11[i, j];
            c[i, j + iNewSize] = C12[i, j];
            c[i + iNewSize, j] = C21[i, j];
            c[i + iNewSize, j + iNewSize] = C22[i, j];
        }
    }

    A11 = null;
    A12 = null;
    A21 = null;
    A22 = null;

    B11 = null;
    B12 = null;
    B21 = null;
    B22 = null;

    C11 = null;
    C12 = null;
    C21 = null;
    C22 = null;

    M1 = null;
    M2 = null;
    M3 = null;
    M4 = null;
    M5 = null;
    M6 = null;
    M7 = null;

    AResult = null;
    BResult = null;

    GC.Collect();

    return c;
}

At the end of calculation I force GC.Collect() in order to optimize the memory usage. Take care that this method can’t be called directly. Take care that the input matrices must be 2^n size.

In alternative use the below method. It resize the matrices before the multiplication.

public static Complex[,] Mul_Strassen(Complex[,] a, Complex[,] b, int iThreshold = 128)
{
    int iPrevSize = a.GetLength(0);
    int iNewSize = GetSize(a.GetLength(0));

    a = PrepareMatrix(a, iNewSize);
    b = PrepareMatrix(b, iNewSize);

    Complex[,] c = Strassen(a, b, iThreshold);

    c = GetMatrixPortion(c, iPrevSize);

    return c;
}

Standard Parallel Method

In my post C# (Multithreading) - A Wrapper Class, I exposed how and when to implement a parallel calculation. In multiplication calculus it is quite easy to do that, so using the MPBox class I modify the standard method.

Here the code:

private static Complex[,] A = MatrixGeneric.Create<Complex>(0);
private static Complex[,] B = MatrixGeneric.Create<Complex>(0);

public static Complex[,] Mul_Parallel(Complex[,] a, Complex[,] b)
{
    Utility.TraceLog("Begin Parallel Mul()");
    A = null;
    B = null;
    A = (Complex[,])a.Clone();
    B = (Complex[,])b.Clone();

    int iSize = A.GetLength(0);
    if (a.GetLength(0) != a.GetLength(1))
        throw new Exception("Not compatibles Matrices!");

    C = MatrixGeneric.Create<complex>(iSize);
    MyParamsItem[] aLoops = null;
    MPDefaultProc myp = new MPDefaultProc(MP_Mul);

    moMPBox.SetCicles(ref aLoops, 1, A.GetLength(0));

    moMPBox.Clear();
    for (int j = 0; j < aLoops.Length; j++)
    {
        moMPBox.Add(myp, aLoops[j]);
    }
    moMPBox.Start(); 
    Utility.TraceLog("End Parallel Mul()");

    A = null;
    B = null;
    return C;
}

public static void MP_Mul(MyParamsItem aoParam)
{
    int iSize = A.GetLength(0);
    for (int row = aoParam.min; row <= aoParam.max; row++) 
    {
        for (int col = 1; col <= iSize; col++) 
        {
            for (int i = 1; i <= iSize; i++) 
            {
                C[row, col] += A[row, i] * B[i, col]; 
            }
        }
    }        
}
Now you can easily compare the performances of the three methods exposed. You will see that the parallel method is the best one. This is because it reach better results compared with Strassen, but it doesn’t use so much memory .


Thursday, March 13, 2014

Create a speedometer from Rotary Incremental Encoder measures


This is what you can find in Wikipedia about Rotary Incremental Encoder:
A rotary encoder, also called a shaft encoder, is an electro-mechanical device that converts the angular position or motion of a shaft or axle to an analog or digital code.
There are two main types: absolute and incremental (relative). The output of absolute encoders indicates the current position of the shaft, making them angle transducers. The output of incremental encoders provides information about the motion of the shaft, which is typically further processed elsewhere into information such as speed, distance, and position. The PLC register value increases until it reaches the upper bound, then begin to increase from the lower value (zero).

Rotary encoders are used in many applications that require precise shaft unlimited rotation—including industrial controls, robotics, special purpose photographic lenses,[1] computer input devices (such as optomechanical mice and trackballs), controlled stressrheometers, and rotating radar platforms.

The Encoder Class
The program have to calculate and store the distance in meter made by a “device” connected to the engine, or simply counting the engine revolutions. In order to calculate the distance traveled the procedure has two take care of two factors: the Engine revolutions and a distance per round. The Motor can do many things, for example controlling a Winch. If the software needs to manage the distance done from rope, pulled or pushed by the Winch, it is necessary to use the revolution factor between the Motor and the Winch.

What it should be done is to manage an incremental encoder signal, that is a positional value, coming from motor revolutions. Imagine a disk that rotate and has a code for each position (For example 8192 values per revolution). To get all useful information it is necessary to pass through a PLC or something like this.

This information is stored into a PLC register. The PLC firmware reads this code and increments the position, moving forward or backward the values between the range This means that every sample time, the read value is added to a total amount, and if the new total value is over the upper bound, the new value is translated into the bottom.

For example consider the motor is moving forward at a constant speed. In tables below how PLC firmware gets samples. There is always two samples code taken in this example, just to simplify the comprehension of the mechanism.

Sample
Read Value
Total
PLC Register
1
1000
1000
1000
2
8192
8192
8192
3
1000
9182
9182
4
8192
16384
16384
5
1000
17384
17384
6
8192
24576
24576
7
1000
25576
25576
8
8192
32768
32768
9
1000
33768
33768
10
8192
40968
40968
11
1000
41968
41968
12
8192
49152
49152
13
1000
50152
50152
14
8192
57344
57344
15
1000
58344
58344
16
8192
65536
1
17
1000
1001
1001
18
8192
8193
8193
PLC register (UINT32 – range between 0  and 65535).

Sample
Read Value
Total
PLC Register
1
1000
1000
1000
2
8192
8192
8192
3
1000
9182
9182
4
8192
16384
16384
5
1000
17384
17384
6
8192
24576
24576
7
1000
25576
25576
8
8192
32768
-32768
9
1000
-31768
-31768
10
8192
-24576
-24576
11
1000
-23576
-23576
12
8192
-16384
-16384



PLC register (INT32 – range between –32768 and 32767).

In both cases when the upper bound is reached, the counter begin again from the bottom. The software, objective of this document, needs to read PLC register and analyze the values. The history of these values gives the distance from the starting point and also, if necessary, the total amount distance by going forward and backward.

What we have in a special case of constant speed is something like the graphic in figure:



The PLC register value increases until it reaches the upper bound, then begin to increase from the lower value (zero).

It is very important taking samples with a right frequency, otherwise there is a concrete risk to lose waves fronts, in this case the algorithm doesn’t work at all.

The idea of this class mechanism represented by the Encoder Class, is to store the previous sample, compare it with the new one and if the difference is upper than 8192, dividing the difference with 8192 in order to obtain the revolutions done. With the remainder of the division it recalculate the last sample to store for next analysis.

A particular attention needs to be done when Motor change direction.
The first sample will be the zero position, zero meter, zero kilometer. If the engine change direction the graphic change, in this case the waves will decrease in value starting from 65535 to zero etc..

Some member variables:

 
int m_prev_pulses = 0; //previuos sample stored
int m_prev_rpm = 0; //previous speed stored (useful to evaluate the direction)
bool m_prev_direction = true; //if true means forward else backward

bool m_Initializated = false;  //the first sample has been taken
int m_rounds = 0; //counter: motor rounds (distance = forward + backward)
int m_rounds_rel = 0; //counter: motor rounds relative (distance = forward - backward)

The constructor has two parameters, in order to create a flexible class. It accepts the distance per round (revolution) and the pulse per round.

 
 /// 
/// Configure the starting parameters
///

/// meter per round
/// pulses per round (from Device configuration)
public Encoder(float mpr, int ppr = 8192)
{
     m_mpr = mpr;
     m_ppr = ppr;
}

Let’s explain the main procedure. The AnalyzeSample() procedure has two input parameters, cnt that is the positional code from PLC register, and rpm that is the Engine speed in rpm (revolutions per meter).

In the current example, the samples comes from a INT32 registry so for first thing the procedure increases the cnt value in order to have always positive values. Then it decides to consider the current value or not checking a Speed filter. If the speed is too low it exits.

 

public void AnalyzeSample(int cnt, int rpm)
{
    m_prev_rpm = rpm;
    int iVal = m_Incr + cnt; //Always positive (0 - 65535)
    if (Math.Abs(rpm) <= m_PulseFilter) return; //speed too low - value ignored


It checks the speed in order to evaluate change of direction. The factor variable will determine the increase or decrease of done distance.

 

 bool bForward = rpm < 0; //forward speed < 0 | backward speed > 0
    int iFactor = bForward ? 1 : -1;
    int sample = bForward ? m_Max - iVal : iVal;


Initialization, only with the first sample this code is considered:
 

if (!m_Initializated)
    {
        m_Initializated = true;
        m_prev_pulses = sample;
        m_prev_direction = bForward;
        return;
    }


Change of direction Management:

 

 if (m_prev_direction != bForward)
    {
        m_prev_pulses = m_Max - m_prev_pulses;
        int diff = Math.Abs(m_prev_pulses - sample);
        m_prev_pulses = (sample - diff);
        if (m_prev_pulses < 0)
            m_prev_pulses = m_Max + m_prev_pulses;
        m_prev_direction = bForward;
        return;
    }
 

And finally the difference between the last sample and the current one is done.

 
 if (sample >= m_prev_pulses)
        dSmpi = (sample - m_prev_pulses);
    else
        dSmpi = (m_Max - m_prev_pulses + sample);

 


If the difference is greater than zero, it makes the division:

 

  int iQi = (int)(dSmpi / m_ppr);

    if (iQi <= 0) return; //not rounds

    m_rounds += iQi;
    m_rounds_rel = m_rounds_rel + (iFactor * iQi);

    int iRem = dSmpi - (iQi * m_ppr); //reminder

    m_prev_pulses = sample - iRem;
    if (m_prev_pulses < 0)
        m_prev_pulses = m_Max + m_prev_pulses;

 


here the complete code:

 

public void AnalyzeSample(int cnt, int rpm)
{
    m_prev_rpm = rpm;
    int iVal = m_Incr + cnt; //Always positive (0 - 65535)
    if (Math.Abs(rpm) <= m_PulseFilter) return; //speed too low - value ignored

    bool bForward = rpm > 0; //forward speed > 0 | backward speed < 0
    int iFactor = bForward ? 1 : -1;

    int sample = bForward ? iVal : m_Max - iVal;

    //first sample acquired
    if (!m_Initializated)
    {
        m_Initializated = true;
        m_prev_pulses = sample;
        m_prev_direction = bForward;
        return;
    }

    //Change of direction
    if (m_prev_direction != bForward)
    {
        m_prev_pulses = m_Max - m_prev_pulses;
        int diff = Math.Abs(m_prev_pulses - sample);
        m_prev_pulses = (sample - diff);
        if (m_prev_pulses < 0)
            m_prev_pulses = m_Max + m_prev_pulses;
        m_prev_direction = bForward;
        return;
    }                      

    int dSmpi = 0;
    if (sample >= m_prev_pulses)
        dSmpi = (sample - m_prev_pulses);
    else
        dSmpi = (m_Max - m_prev_pulses + sample);

    m_prev_direction = bForward;

    if (dSmpi <= 0) return;
    int iQi = (int)(dSmpi / m_ppr);

    if (iQi <= 0) return;

    m_rounds += iQi;
    m_rounds_rel = m_rounds_rel + (iFactor * iQi);

    int iRem = dSmpi - (iQi * m_ppr);

    m_prev_pulses = sample - iRem;
    if (m_prev_pulses < 0)
        m_prev_pulses = m_Max + m_prev_pulses;
}