Mercurial > matrix-functions
annotate funm_files/swapping.m @ 0:8f23314345f4 draft
Create local repository for matrix toolboxes. Step #0 done.
author | Antonio Pino Robles <data.script93@gmail.com> |
---|---|
date | Wed, 06 May 2015 14:56:53 +0200 |
parents | |
children |
rev | line source |
---|---|
0
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
1 function [M,ind,n_swaps] = swapping(m) |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
2 %SWAPPING Confluent permutation by swapping adjacent elements. |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
3 % [ISWAP,IND,N_SWAPS] = SWAPPING(M) takes a vector M containing |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
4 % the integers 1:k (some repeated if K < LENGTH(M)) |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
5 % and constructs a swapping scheme that produces |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
6 % a confluent permutation, with elements ordered by ascending |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
7 % average position. The confluent permutation is obtained by using |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
8 % the LAPACK routine ZTREX to move m(ISWAP(i,2)) to m(ISWAP(i,1)) |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
9 % by swapping adjacent elements, for i = 1:SIZE(M,1). |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
10 % The cell array vector IND defines the resulting block form: |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
11 % IND{i} contains the indices of the i'th block in the permuted form. |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
12 % N_SWAPS is the total number of swaps required. |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
13 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
14 mmax = max(m); M = []; ind = {}; h = zeros(1,mmax); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
15 g = zeros(1,mmax); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
16 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
17 for i = 1:mmax |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
18 p = find(m==i); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
19 h(i) = length(p); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
20 g(i) = sum(p)/h(i); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
21 end |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
22 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
23 [x,y] = sort(g); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
24 mdone = 1; |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
25 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
26 for i = y |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
27 if any(m(mdone:mdone+h(i)-1) ~= i) |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
28 f = find(m==i); g = mdone:mdone+h(i)-1; |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
29 ff = f(f~=g); gg = g(f~=g); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
30 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
31 % Create vector v = mdone:f(end) with all elements of f deleted. |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
32 v = mdone-1 + find(m(mdone:f(end)) ~= i); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
33 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
34 % v = zeros(1,f(end)-g(1)+1); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
35 % v(f-g(1)+1) = 1; v = g(1)-1 + find(v==0); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
36 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
37 M(end+1:end+length(gg),:) = [gg' ff']; |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
38 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
39 m(g(end)+1:f(end)) = m(v); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
40 m(g) = i*ones(1,h(i)); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
41 ind = cat(2,ind,{mdone:mdone+h(i)-1}); mdone = mdone + h(i); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
42 else |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
43 ind = cat(2,ind,{mdone:mdone+h(i)-1}); mdone = mdone + h(i); |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
44 end |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
45 end |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
46 |
8f23314345f4
Create local repository for matrix toolboxes. Step #0 done.
Antonio Pino Robles <data.script93@gmail.com>
parents:
diff
changeset
|
47 n_swaps = sum(abs(diff(M'))); |