lu-lapack.cpp File Reference

#include "hex-blas.h"
#include "lu-lapack.h"

Include dependency graph for lu-lapack.cpp:

Functions
template<class IdxT >
NumberArray< IdxT >	cuthill_mckee (NumberArray< IdxT > const &P, NumberArray< IdxT > const &I)
	Compute the Cuthill-McKee ordering. More...

Function Documentation

cuthill_mckee()

template<class IdxT >

NumberArray<IdxT> cuthill_mckee	(	NumberArray< IdxT > const &	P,
		NumberArray< IdxT > const &	I
	)

Returns a row/column permutation array that will minimize the bandwidth of a symmetric matrix using the Cuthill-McKee algorithm. The matrix structure is given using the CSR index arrays (row pointers and column indices). Only upper triangle positions are considered.

The algorithm works as follows:

• A row with the lowest number of non-zeros is taken as the starting row and inserted into the resulting row sequence R.
• While there are some rows not in R: – Construct the adjacency set A of R, i.e. all rows that are coupled by the matrix rows already in R, excluding those already in R. If there is none such row, the reordered matrix has a block structure and it is necessary to restart the algorithm from the first step on the remaining rows. – Sort A by number of non-zeros on the rows. – Append A to R.