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 100-by-100
arrowhead matrix
n = 100; 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.
Extended Capabilities
Version History
Introduced before R2006a
