Curtis, Powell, and Reid heuristics

The heuristic of Curtis, Powell and Reid (hereinafter also CPR heuristic ) is a method for finding the columns (or rows) of a sparse matrix that can be combined linearly.

problem

Let J be a sparse matrix. Find a binary matrix S with minimal p such that all non-zero elements of J appear in the product (the compressed version of J). ${\ displaystyle m \ times n}$ ${\ displaystyle n \ times p}$ ${\ displaystyle {\ tilde {J}} = J \ cdot S}$

Structural orthogonality

Two vectors of a matrix are called structurally orthogonal if there is no row in which they have both elements other than zero. It follows that the scalar product of these two vectors is zero, which is a necessary but not a sufficient condition.

Setting up a partition

Groups of structurally orthogonal columns are described by a partition.

${\ displaystyle P: i \ rightarrow \ {1,2, \ dots, p \}}$

${\ displaystyle P (i) = k \ Leftrightarrow}$ i-th column is in k-th group of structurally orthogonal columns.

The number of a group is also called a color.

To set up the partition, all columns are worked through until the colors are assigned. The color with the lowest number is assigned in each case if the column currently under consideration is structurally orthogonal to one or more columns. If the column is not structurally orthogonal to any column, it receives a new color with the next higher number.

Setting up the seed matrix

The seed matrix S can be determined from the partition P as follows: The entry if column i has the color k and otherwise . ${\ displaystyle S_ {i, j} = 1}$ ${\ displaystyle S_ {i, j} = 0}$

Note : Since S in general cannot be inverted, the sparse pattern is required to get from the compressed version back to the uncompressed version J. ${\ displaystyle {\ tilde {J}}}$

literature

Alan R. Curtis, Michael JD Powell, John K. Reid: On the Estimation of Sparse Jacobian Matrices , J. Inst. Math. Appl., Vol. 13, pp. 117-119, (1974)