Sparse column permutation based on nonzero count

`j = colperm(S)`

`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))`

.

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.

Was this topic helpful?