Tutorial 2: How to Add Matrix Ordering

SparseViz allows its users to add the custom matrix orderings that they want to implement on their matrices. Adding such matrix orderings into SparseViz involves a couple of elementary steps. In this tutorial, these steps are going to be explained in a detailed manner.

Every custom matrix ordering in the SparseViz ecosystem derives from the abstract MatrixOrdering class. SparseViz/include/Matrix/Orderings is where the header file of this custom ordering class could be created and SparseViz/src/Matrix/Orderings is where the source file of this custom ordering class could be created. In this tutorial, we are going to create an example matrix ordering named AddingMatrixOrdering and show how it can be integrated into the library.

Step 1: Creating a Custom Ordering Class

First, we will create the AddingMatrixOrdering.h file in the SparseViz/include/Matrix/Orderings directory.

The header file will contain the declaration of our class, which consists of only 5 lines of C++ code.

AddingMatrixOrdering.h

#include "MatrixOrdering"

class AddingMatrixOrdering: public MatrixOrdering

{

public:

    AddingMatrixOrdering(SparseMatrix& matrix, std::string orderingName, std::string orderingParameters);

    virtual void orderingFunction() override;

};

MatrixOrdering has only one pure virtual function that it dictates to be overridden by every derived class. This function is called orderingFunction which would carry the implementation of the ordering logic. In addition to that, a constructor should be written for the custom matrix ordering classes whose first 2 parameters have to be the reference to the matrix on which the ordering will be applied and the name of the ordering, respectively. The third parameter is optional in that it can be skipped safely if the custom order does not need any parameters to work properly.

Having declared our class, next is to create its source file named AddingMatrixOrdering.cpp under the directory SparseViz/src/Matrix/Orderings.

AddingMatrixOrdering.cpp

#include "AddingMatrixOrdering.h"

AddingMatrixOrdering::AddingMatrixOrdering(SparseMatrix &matrix, std::string orderingName, std::string orderingParameters)
:   MatrixOrdering(matrix, orderingName, true, true, 5)
{

    // Ordering parameters could be parsed (remember the delimiter is '/')

    // and appropriate private member variables could be set here

}

void AddingMatrixOrdering::orderingFunction()
{

    rowIPermutation = new vType[this->getMatrix().getRowCount()];

    colIPermutation = new vType[this->getMatrix().getColCount()];

    // Your ordering function logic goes here

}

There are a couple of important parts in the source code that require careful attention. The first is the initialization of the base class MatrixOrdering in the constructor of the AddingMatrixOrdering class. MatrixOrdering expects the following parameters to be provided.

SparseMatrix& matrix

std::string orderingName

bool rectangularSupport

bool patternUnsymmetricSupport

unsigned int orderingFunctionPrice = 0

The first 2 parameters, matrix, and orderingName, could easily be provided to the parent class with the constructor parameters of the child class. The third parameter, rectangularSupport, determines whether or not this custom ordering class has support for rectangular matrices. In case a rectangular matrix will be tried to be ordered in a scenario in which this support is not found, then MatrixOrdering will create an ordering-supported matrix during the runtime to make this ordering possible. Similar to the rectangular support parameter, the patternUnsymmetricSupport parameter determines whether or not this custom ordering class has support for matrices in which pattern symmetry is not available. In case a pattern unsymmetric matrix will be tried to be ordered in a scenario in which this support is not found, an ordering support matrix will be created in the runtime by the MatrixOrdering library to make this ordering possible. The last parameter is an integer between 0 to 10 representing the overhead of the ordering function. Although it has a default value of 0, we recommend custom ordering derived classes to specify this value, as appropriate values could increase the performance of the program. For our ordering class, we will assume that it supports rectangular and pattern unsymmetric matrices with an orderingFunction overhead value of 5.

The last important remark that we need to make is that in the custom matrix orderings, 2 arrays should be generated by orderingFunction. These are the only protected member variables of the MatrixOrdering base class whose initialization values are nullptr. These arrays are called rowIPermutation and colIPermutation which determine the new location of each row and column after the ordering is implemented. They should be allocated on the heap with sizes equal to the row size for rowIPermutation and equal to the col size of colIPermutation. Custom ordering classes are not responsible for deleting these arrays, as the MatrixOrdering base class will safely handle this problem.

Step 2: Adding Files into CMakeLists.txt

In the former step, we have created our header file and source file for our class named AddingMatrixOrdering. In this step, we are going to include these files in our build automation tool. SparseViz utilizes CMake as its build system. In the CMakeLists.txt file located under the project directory, we should include our header file under the HEADER_FILES environment variable and include our source under the SOURCE_FILES environment variable, like so:

CMakeLists.txt

set(HEADER_FILES

    --- OTHER HEADER FILES (CROPPED) ---

    include/Matrix/Orderings/AddingMatrixOrdering.h

)

set(SOURCE_FILES

    --- OTHER SOURCE FILES (CROPPED) ---

    src/Matrix/Orderings/AddingMatrixOrdering.cpp

)

Step 3: Adding Ordering Definition Into SparseVizEngine

As the last step, we are going to add our ordering class definition into SparseVizEngine and allow the library to identify the presence of this ordering. As our first job, we are going to include our custom ordering class' header file into the SparseVizEngine.h:

SparseVizEngine.h

#include "AddingMatrixOrdering.h"

After that, we are going to add the definition of the class to the matrix ordering factory function located in the source file of the SparseVizEngine

SparseVizEngine.cpp

MatrixOrdering *SparseVizEngine::matrixOrderingFactory(SparseMatrix& matrix, std::string orderingClassName, std::string orderingName, std::string orderingParameters)

{

    --- OTHER ORDERING CLASSES (CROPPED) ---

    else if (orderingClassName == "AddingMatrixOrdering")

    {

        return new AddingMatrixOrdering(matrix, orderingName, orderingParameters);

    }

    return nullptr;

}

Having done this, we can easily run this ordering from within the config file by indicating it under the section *MATRIX_ORDERINGS*, like so:

config

*MATRIX_ORDERINGS*

AddingMatrixOrdering | WeHaveAddedAMatrixOrdering | Param1/Param2/Param3

This concludes the tutorial 2, the way to add matrix orderings into the library.