NAG Library Routine Document

1Purpose

m01zcf decomposes a permutation into cycles, as an aid to reordering ranked data.

2Specification

Fortran Interface
 Subroutine m01zcf ( m1, m2,
 Integer, Intent (In) :: m1, m2 Integer, Intent (Inout) :: iperm(m2), ifail Integer, Intent (Out) :: icycl(m2)
#include nagmk26.h
 void m01zcf_ ( Integer iperm[], const Integer *m1, const Integer *m2, Integer icycl[], Integer *ifail)

3Description

m01zcf is provided as an aid to reordering arbitrary data structures without using additional storage. However, you should consider carefully whether it is necessary to rearrange yourr data, or whether it would be simpler and more efficient to refer to the data in sorted order using an index vector, or to create a copy of the data in sorted order.
To rearrange data into a different order without using additional storage, the simplest method is to decompose the permutation which specifies the new order into cycles and then to do a cyclic permutation of the data items in each cycle. (This is the method used by the M01E reordering routines.) Given a vector IRANK which specifies the ranks of the data (as generated by the M01D routines), m01zcf generates a new vector icycl, in which the permutation is represented in its component cycles, with the first element of each cycle negated. For example, the permutation
 $5 7 4 2 1 6 3$
is composed of the cycles
 $1 5 2 7 3 4 6$
and the vector icycl generated by m01zcf contains
 $-1 5 -2 7 3 4 -6$
In order to rearrange the data according to the specified ranks:
• item $6$ must be left in place;
• items $1$ and $5$ must be interchanged;
• items $4$, $2$, $7$ and $3$ must be moved right one place round the cycle.
The complete rearrangement can be achieved by the following code:
```Do 10 k = m1, m2
i = icycl(k)
If (i.lt.0) Then
j = -i
Else
[swap items i and j]
Endif
10 Continue```

None.

5Arguments

1:     $\mathbf{iperm}\left({\mathbf{m2}}\right)$ – Integer arrayInput/Output
On entry: elements m1 to m2 of iperm must contain a permutation of the integers m1 to m2.
On exit: is used as internal workpsace prior to being restored and hence is unchanged.
2:     $\mathbf{m1}$ – IntegerInput
3:     $\mathbf{m2}$ – IntegerInput
On entry: m1 and m2 must specify the range of elements used in the array iperm and the range of values in the permutation, as specified under iperm.
Constraint: $0<{\mathbf{m1}}\le {\mathbf{m2}}$.
4:     $\mathbf{icycl}\left({\mathbf{m2}}\right)$ – Integer arrayOutput
On exit: elements m1 to m2 of icycl contain a representation of the permutation as a list of cycles, with the first integer in each cycle negated. (See Section 3.)
5:     $\mathbf{ifail}$ – IntegerInput/Output
On entry: ifail must be set to $0$, $-1\text{​ or ​}1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{​ or ​}1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$. When the value $-\mathbf{1}\text{​ or ​}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{m2}}<1$, or ${\mathbf{m1}}<1$, or ${\mathbf{m1}}>{\mathbf{m2}}$.
${\mathbf{ifail}}=2$
Elements m1 to m2 of iperm contain a value outside the range m1 to m2.
${\mathbf{ifail}}=3$
Elements m1 to m2 of iperm contain a repeated value.
If ${\mathbf{ifail}}={\mathbf{2}}$ or ${\mathbf{3}}$, elements m1 to m2 of iperm do not contain a permutation of the integers m1 to m2.
${\mathbf{ifail}}=-99$
See Section 3.9 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 3.8 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

Not applicable.

8Parallelism and Performance

m01zcf is not threaded in any implementation.

None.

10Example

This example reads a matrix of real numbers and rearranges its columns so that the elements of the $l$th row are in ascending order. To do this, the program first calls m01djf to rank the elements of the $l$th row, and then calls m01zcf to decompose the rank vector into cycles. It then rearranges the columns using the framework of code suggested in Section 3. The value of $l$ is read from the data file.

10.1Program Text

Program Text (m01zcfe.f90)

10.2Program Data

Program Data (m01zcfe.d)

10.3Program Results

Program Results (m01zcfe.r)

© The Numerical Algorithms Group Ltd, Oxford, UK. 2017