Matlab Reordering

matlab 提供了一些 reordering 的演算法
包括^[1]

amd	Approximate minimum degree permutation
colamd	Column approximate minimum degree permutation
colperm	Sparse column permutation based on nonzero count
dmperm	Dulmage-Mendelsohn decomposition
randperm	Random permutation
symamd	Symmetric approximate minimum degree permutation
symrcm	Sparse reverse Cuthill-McKee ordering

以 amd 為例，使用方法為

>> p=amd(A)

其中 A 是 n*n，要 reordering 的 matrix
p 是根據 reordering 演算法生成的 permutation vector

要把這個 permutation 作用在 A 上面可以透過矩陣乘法達成^[2]
首先準備一個和 A 一樣大，對角線是 1 其他都是 0 的 matrix

>> I = eye(n)

然後用 permutation vector 把 I 的位置換一換，生一個 permutation matrix 出來
這邊有兩種生法

>> P1 = I(:,p)
>> P2 = I(p,:)

其中的差別舉個例子說明：
如果 p = [2 3 1]

I
1 0 0
0 1 0
0 0 1

P1
0 0 1
1 0 0
0 1 0

P2
0 1 0
0 0 1
1 0 0

從 column 來看的話，
P1 把原本 col 2 換到新的 col 1 的位置、P2 把原本 col 1 換到新的 col 2 的位置
從 row 來看則是剛好反過來，
P1 把原本 row 1 換到新的 row 2 的位置、P2 把原本 row 2 換到新的 row 1 的位置

如果有 matrix A 和 permutation matrix P，
想要交換 column 的話，要用 A*P、想要交換 row 的話，則要用 P*A

因此想要用 amd 生成的 permutation 來達到 reorder graph node 的效果

>> reorder_A = P2*A*P1

當然也可以用 sparse matrix 比較省空間

>> I = speye(n);
>> P1 = I(:,p);
>> P2 = I(p,:);
>> reorder_A = P2*A*P1

Reference
[1] http://www.mathworks.com/help/matlab/reordering-algorithms.html
[2] http://matlab.izmiran.ru/help/techdoc/math/sparse17.html
[3] http://www.icm.tu-bs.de/~bolle/ilupack/doc/matlab.shtml