# colperm

Sparse column permutation based on nonzero count

## Syntax

```j = colperm(S) ```

## Description

`j = colperm(S)` generates a permutation vector `j` such that the columns of `S(:,j)` are ordered according to increasing count of nonzero entries. This is sometimes useful as a preordering for LU factorization; in this case use `lu(S(:,j))`.

If `S` is symmetric, then `j` `=` `colperm(S)` generates a permutation `j` so that both the rows and columns of `S(j,j)` are ordered according to increasing count of nonzero entries. If `S` is positive definite, this is sometimes useful as a preordering for Cholesky factorization; in this case use `chol(S(j,j))`.

## Examples

The `n`-by-`n` arrowhead matrix

`A = [ones(1,n); ones(n-1,1) speye(n-1,n-1)]`

has a full first row and column. Its LU factorization, `lu(A)`, is almost completely full. The statement

`j = colperm(A)`

returns `j` `=` `[2:n` `1]`. So `A(j,j)` sends the full row and column to the bottom and the rear, and `lu(A(j,j))` has the same nonzero structure as `A` itself.

On the other hand, the Bucky ball example,

`B = bucky`

has exactly three nonzero elements in each row and column, so ```j = colperm(B)``` is the identity permutation and is no help at all for reducing fill-in with subsequent factorizations.

## Algorithms

The algorithm involves a sort on the counts of nonzeros in each column.