A package grouping matrices row reordering algorithms to minimize their front size.
Project description
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.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.