matrex

matrex stands for Matrix Reordering algorithms.

The library implements the Modified Sloan Row Ordering (MSRO) algorithm. By permuting the rows of a matrix, the algorithm minimizes the mean/max front size of this matrix. The front size minimization can be viewed in the following example :

Here, the black squares represent the position in the matrix where there is a non-zero value. The columns of the matrix have been reordered so that those values are closer together as much as possible in each row. The mean of this distance (difference between first and last non-zero index in a row) is shown on top of those pictures (before vs after msro application).

The original Fortran implementation is called mc62 and is part of the HSL library.

Installation

You can install matrex using pip:

pip install matrex

or by directly downloading it from this github :

pip install matrex@git+https://github.com/benjaminlanthier/matrex

The MSRO algorithm

This paper by Jennifer A. Scott describes the logic and structure of the MSRO algorithm. It iteratively selects rows to be part of the new permutation according to a priority function. In the paper, the authors use the following priority function:

$$ \begin{equation} P_i = -W_1 \text{rcgain}_i + W_2 d(i, e), \end{equation} $$

We implement a slightly different priority function described in the manual for mc62:

$$ \begin{equation} P_i = -W_1 \text{rcgain}_i + W_2 d(i, e) - W_3 \text{nold}_i. \end{equation} $$

In both equations, we have that:

• $\text{rcgain}_i$ is "the increases to the row and column front sizes resulting from assembling row $i$ next" [1]
• $d(i, e)$ is the distance between the row $i$ and the row $e$, where $e$ is the target row, found by using the pseudodiameter of the row graph of the input matrix.
• $\text{nold}_i$ is "the number of variables in row $i$ that are candidates for elimination and have already been brought into the front" [2].

Example

import numpy as np
from matrex import msro

m = np.array([[1, 1, 1, 0, 0, 0],
              [0, 1, 1, 0, 1, 0],
              [1, 1, 0, 1, 0, 0],
              [0, 0, 1, 0, 1, 1],
              [0, 1, 1, 0, 1, 0]])
# For the rows reordering
new_columns_order = msro(m)
reordered_rows_matrix = m[new_columns_order]
# For the columns reordering
new_columns_order = msro(m.T)
reordered_cols_matrix = m[:, new_columns_order]

Dependencies

Packages needed to run this algorithm :

• numpy
• networkx
• Optional : matplotlib (for visualizing the row graph)

References

[1] Scott, Jennifer A. ‘A New Row Ordering Strategy for Frontal Solvers’. Numerical Linear Algebra with Applications, vol. 6, no. 3, Apr. 1999, pp. 189–211. DOI.

[2] HSL, a collection of Fortran codes for large-scale scientific computation. See their site.