Introduction

PyOrder is a Python package that provides access to several means to reorder sparse matrices. Typically, sparse matrices are reordered prior to factorization so as to preserve sparsity of the factors, ensure that there are as many nonzero elements as possible on the diagonal, or decrease the envelope, wavefront, profile or semi-bandwidth.

Note

Orderings designed to promote sparsity of the factors of a matrix are different in nature from the other types of orderings mentioned in the previous paragraph and are not considered in PyOrder. If you would like to see such orderings (e.g., AMD, CAMD, COLAMD, etc.) included in future releases of PyOrder, please let me know.

A Few Concepts about Symmetric Sparse Matrices

Although not all ordering functions in this package assume symmetry, most concepts are defined for symmetric matrices only.

If \(A\) is a square \(n \times n\) symmetric sparse matrix, let \(a_{ij}\) be the element at the intersection of the \(i\)-th row and the \(j\)-th column. The following concepts are important for reordering purposes.

The \(i\)-th wavefront of \(A\) is the number of nonzero rows in the submatrix \(A(i:n,1:i)\), \(i = 1, \ldots, n\). It is denoted \(f_i\).

The maximum wavefront is

\[\max_{i=1,\ldots,n} f_i\]

while the mean-square wavefront is

\[\frac{1}{n} \sum_{i=1}^{n} f_i^2.\]

If \(m_i\) is the column index of the first nonzero element on the \(i\)-th row of \(A\), the envelope of \(A\) is the set of nonzero elements lying between \((i,m_i)\) and the diagonal, exclusive of the diagonal, i.e.

\[\begin{split}\text{Env}(A) = \left\{ (i,j) \mid 1 \leq i \leq n, \ m_i \leq j < i \right\}.\end{split}\]

The profile \(P(A)\) of the matrix is the number of elements in \(\text{Env}(A)\) plus the number of nonzero elements on the diagonal, i.e.,

\[P = \sum_{i=1}^{n} (i - m_i + 1).\]

It is possible to show that those quantities are linked via the relationship

\[P = \sum_{i=1}^{n} f_i.\]

Availability

PyOrder is essentially a set of interfaces to subroutines from the HSL http://www.cse.scitech.ac.uk/nag/hsl (formerly the Harwell Subroutine Library). Subroutines from the HSL may be obtained free of charge under certain conditions. See http://hsl.rl.ac.uk/hsl2007/hsl20074researchers.html to decide whether the terms apply to you. The HSL subroutines relevant to PyOrder are not packaged together with the Python interfaces and should be obtained separately.

Note

At this time, only double precision real data is supported. Please let me know if you would like support for single precision and/or complex data.