Original Matrix Decomposed Matrix



(347) 954-4405

View Original Matrix

(563) 285-8639

View Decomposed Matrix



C++ Implementation

Web Service

Contact Us

Make a Donation

Epsilon Decomposition

Welcome to the Epsilon Decomposition site. This interactive site enables execution of epsilon decomposition on uploaded input data. Input matrix data have to be provided as csv ascii compressed file. After data upload, input matrix graphical presentation is available. Now epsilon decomposition can be performed and decomposition results are presented in tabular form. Also, graphical presentation of decomposed matrix is available. Finally decomposition results data are provided for download.

Demo Data

By clicking on Get Demo Data button, demo matrix data are going to be loaded. Now, by selecting Decompose Matrix link, demo matrix can be decomposed with user entered epsilon value. Graphical presentation of decomposed input matrix for epsilon ranging from 0 to 0.9 are shown below.

no dec eps 0.1 eps 0.2 eps 0.5 eps 0.6 eps 0.9

What is Epsilon Decomposition

Epsilon decomposition, decomposes a matrix and creates a block diagonal matrix. It removes normalized matrix row elements that are less than epsilon (0 <= epsilon <= 1). The row elements are normalized by the absolute maximum value in the row. After the normalization process, all normalized row values are <= 1. The next step is to find what matrix rows are connected, then permute the matrix rows and columns in order to to get a block diagonal decomposed matrix.

Epsilon decomposition can be used in decentralized control in order to find what parts of the system are weakly coupled.

Note that program is handling both square and rectangular matrices.

The following example demonstrates epsilon decomposition and its results.

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

Aorg =

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

First the row elements are normalized by row absolute maximal value

Anorm =

[0.08 0.86 0.21 1.00]
[0.91 0.00 1.00 0.10]
[0.09 0.09 0.00 1.00]
[0.95 0.00 1.00 0.10]

After removing elements that are less than 0.2, reordering the row and columns and restoring original values, the following block diagonal matrix is produced:

Adec =

[2.10 2.30 0.00 0.00]
[4.10 -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 that belong to the block are not removed (Adec(4,3) = 0.32).

The program also provides the following information:

  • Number of blocks after decomposition, for above example nBlocks = 2
  • Block sizes given in the number of rows and columns, 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
Adec = Aorg(rowPermRhs, colPermRhs)

After permuting the original matrix one needs to remove elements that are outside the blocks in order to get a block diagonal decomposed matrix.

I hope that you are going to enjoy using Epsilon Decomposition site.

Dejan Miljkovic