WHAT IS EPSD?

Epsilon decomposition decompose matrix and crates block diagonal matrix by removing normalized
matrix row elements that are less than epsilon (0 <= epsilon <= 1). The row elements are
normalized by row absolute maximal value i.e. all normalized row values are <= 1.
The epsilon decomposition can be used in decentralized control in order to find what parts of
the system are weakly coupled.

Note that class is handling both square and rectangular matrices.

   The following example demonstrates the epsilon decomposition and results that are
   produced by class EpsilonDec.

   Let us apply epsilon decomposition with epsilon = .2 to the following matrix:

          [0.11 1.20 0.30 1.40]
   Aorg = [2.10 0.00 2.30 0.24]
          [0.31 0.32 0.00 3.40]
          [-4.1 0.00 4.30 0.43]

First the row elements are normalized by row absolute maximal value and after removing elements
that are less than 0.2 and reordering row and columns following block diagonal matrix is produced:

          [2.10 2.30 0.00 0.00]
   Adec = [-4.1 4.30 0.00 0.00]
          [0.00 0.00 1.20 1.40]
          [0.00 0.00 0.32 3.40]

Note that elements that are less than epsilon and belongs to the block are not removed Adec(4,2) =  0.32.

The program is also providing following information's:
 - Number of blocks after decomposition i.e. for above example:
   nBlocks = 2
 - Block sizes given in number of rows and columns i.e. for above example:
   rowBlockSize = [2 2]
   colBlockSize = [2 2]
 - Permutation vectors:
   Right hand side row permutation vector,    rowPermRhs = [1 3 0 2]
   Left hand side row permutation vector,     rowPermLhs = [2 0 3 1]
   Right hand side column permutation vector, colPermRhs = [0 2 1 3]
   Left hand side column permutation vector,  colPermLhs = [0 2 1 3]

   The permutation vectors can be used in a following way
   Adec(rowPermLhs, colPermLhs) = Aorg
   or
   Adec = Aorg(rowPermRhs, colPermRhs)

After permuting the original matrix one need to remove elements that are outside the blocks
in order to get decomposed matrix.

The class is supporting several input/output matrix formats such as:
 - Sparse non zero values in column major orientation i.e. vector of non zero values, vector of
   corresponding row positions and vector of column pointers.
 - Sparse non zero values in row major orientation i.e. vector of non zero values, vector of
   corresponding column positions and vector of row pointers.
 - Sparse matrix given non-zero values and row and column positions for each non-zero value.
 - Row major boost sparse matrix.
 - Full matrix format. Note that all elements need to be initialized.


BUILDING AND INSTALLING EPSD 

The implementation of the epsilon decomposition is using the boost library for sparse matrix
storage and graph operations used in epsilon decomposition realization.
The boost library can be downloaded from www.boost.org

To unpack epsd, download the tar/compressed file
epsd-1.0.tar.gz and type:

% gunzip -c epsd-1.0.tar.gz | tar xvf -
% cd epsd-1.0


The test code (epsd_test.cpp) can be compiled on LINUX using following compilation line:

 g++ epsd_test.cpp -I/home/boost_1_32_0/ -c -g3 -O3 -pedantic -Wall -DNDEBUG -Wno-long-long -ftemplate-depth-100

   and than linked by

 g++ -o epsd epsd_test.o

Please note that in this case boost library need to be installed under /home/boost_1_32_0/

LICENSE

epsd is licensed under the MIT License.

AUTHOR
epsd is written and maintained by Dejan Miljkovic.
Write to dejanm@gmail.com for all comments and problem reports.