orderIncidenceMatrix

Method of mdss.

Reorder a square incidence matrix into block-lower-triangular form.

Source: src/model/@mdss/orderIncidenceMatrix.m

Syntax

[Isorted, rowSort, colSort] = orderIncidenceMatrix(sys, I)

Description

orderIncidenceMatrix permutes the rows and columns of a square incidence matrix I so that the equation system becomes block-lower-triangular (BLT). It applies MATLAB’s dmperm (Dulmage–Mendelsohn decomposition) and reorders I by the flipped row and column permutations, sorting equations by the number of variables they contain.

The matrix I must be square: the number of unknown variables must equal the number of equations and constraints, otherwise an error is raised. The sys argument is not used by the computation (the method ignores it) and the routine is an internal helper, called by determineParallizedSolvingOrder.

Input arguments

Argument	Description
`sys`	The `mdss` model (unused by the computation).
`I`	Square incidence matrix (equations × unknowns).

Output arguments

Output	Description
`Isorted`	`I` reordered into block-lower-triangular form.
`rowSort`	Row permutation applied to `I`.
`colSort`	Column permutation applied to `I`.

Example

Take a square incidence matrix of three equations in three unknowns (1 = the unknown appears in the equation):

        v1 v2 v3
 eq1 [   1  1  1 ]
 eq2 [   0  0  1 ]
 eq3 [   0  1  1 ]

This is not lower-triangular, so it cannot be solved by direct forward substitution as written. orderIncidenceMatrix permutes it into block-lower-triangular form:

I = [1 1 1; ...
     0 0 1; ...
     0 1 1];

[Isorted, rowSort, colSort] = orderIncidenceMatrix(sys, I);

giving a lower-triangular pattern — eq2 isolates v3, then eq3 gives v2, then eq1 gives v1:

 rowSort = [2 3 1]      colSort = [3 2 1]

         v3 v2 v1
 eq2 [    1  0  0 ]
 eq3 [    1  1  0 ]
 eq1 [    1  1  1 ]