(Matrix Ordering algorithm for minimum NET-cuts!)

      Yifan Hu, Daresbury Laboratory
       version: 1.00, Nov. 1998

      Copyright (C) 1998 Yifan Hu

This software should not be redistributed without the consent of the
author. Please acknowledge the use of this software using the
following reference:

Y. F. Hu, K. C. F. Maguire and R. J. Blake, A multilevel unsymmetric
matrix ordering algorithm for parallel process simulation, Computers
and Chemical Engineering 23 (1631-1647), 2000.


This is a F90 code which orders a general unsymmetric matrix into
bordered block diagonal matrix of the form

( D1           B1)
(    D2        B2)
(       D3     B3)
(      ....    ..)
(           Dn Bn)

The packege contains the following directory

lib  --- contains the subroutine library and modules
test --- a test driver of the code which also act as a stand alone
         code for ordering matrix of either Harwell-Boeing format
         (with suffix .rua) or of the (i,j,a(i,j)) format (with suffix .mtx)
bin --- where the excutable after "make" in test will be

Usage as a stand alone code:

1) cd test 
2) edit the common.make file to include the 
   suitable compiler option. Some sample compiler
   options can be find in AIX.make, ALPHA.make, IRIX.make etc.
3) type make
4) an excutable code will be in the bin direcotry
5) two sample matrix files are given, west0381.rua (in Harwell-Boeing format)
   and simple.mtx (in coordinate format). 
6) as an test ---

% cd matrices; ../bin/monet west0381.rua  4

gives you ----

problem = west0381.rua blocks =      4
calling the ordering routine ----------
cpu =       0.71
netcut =        166 netcut% =        43.83
finish the ordering routine ----------
block    1 =         95 X 
block    2 =         95 X 
block    3 =         95 X 
block    4 =         96 X 
imbalance =       0.79%

An output file "west0381.rua.4" is also generated. 
It is of the form 

% nrow ncol
% new_row old_row row_block_index
% ....
% new_col old_col col_block_index
% ....
   .   .   .
   .   .   .
  i1  i2  i3
   .   .   .

  i1: the new row/column index
  i2: the corresponding old row/column index
  i3: the row/column block index of this row/column i1 

7) The code can also be used as a subroutine call to order a matrix
into bordered block diagonal. MONET/test/main.f90 gives an example
of how this could be done. The Makefile in the MONET/test directory
shows how the library should be linked.

The subroutine call takes the form
  call monet(n,nz,irn,jcn,val,num_blocks,row_order, &
where the last three arguments are optional.

Details of the arguments are as follows.

#ifdef BIT64

    ! ======================== INPUT =========================
    ! n: row size
    ! nz: number of nonzeros
    integer (kind=myint), intent (in) ::  n
    integer (kind=myint), intent (in) :: nz

    ! irn, jcn: row, column indices of the matrix
    ! of size >= nz assigned by the user
    integer (kind=myint), intent (in) :: irn(:)
    integer (kind=myint), intent (in) :: jcn(:)

    ! number of blocks
    integer (kind = myint), intent (in) :: max_blocks

    ! ========================== OUTPUT =======================
    ! row ordering: row_order(i) is the original row index
    ! of the i-row of the reordered matrix. Integer array of 
    ! size >= n, space allocated by the user.
    integer (kind = myint), intent (out) :: row_order(:)

    ! ========================= optional INPUT =====================
    ! control parameters: 
    ! 1) moderate (cntrl(1) <= 0) or aggressive (cntrl(1) > 0)
    ! 2) load imbalance allowed at each bisection
    ! 3) print option: -1 for quiet, 0 for verbose
    ! 4) number of levels in the multilevel scheme, default 10
    ! 5) ... not used
    real (kind = myreal), optional, intent (in), dimension (:) :: cntrl

    ! ========================== optional output =======================
    ! row_sta (optional): row  starting index for each block.
    ! integer array of size >= max_blocks1, space allocated
    ! by the user
    integer (kind = myint), optional, intent (out), dimension (:) :: row_sta

    ! column order (optional): column_order(i) is the original column index
    ! of the i-column of the reordered matrix. An integer array 
    ! of size >= maxval(jcn), with its space allocated by the user before
    ! calling this program
    integer (kind = myint), intent (out), optional, &
         dimension (:) :: column_order

    ! column_sta (optional): the starting column index for each block.
    ! column_sta(i) is the starting column index of the i-th block. 
    ! An integer array of size >= max_blocks+1, with its space 
    ! allocated by the user before calling this program
    integer (kind = myint), intent (out), optional, &
         dimension (:) :: column_sta

7) after the call, you can reorder your system as
  irn = row_position(irn)
  jcn = column_position(jcn) 
  rhs = rhs(row_order)
where row_position and column_position can be derived yourself 
as in MONET/test/main.f90, e.g., 
  do i = 1, n
     row_position(row_order(i)) = i
  end do  

8) to view your matrix, there are two facilities, either 
 call dump_coo_gnuplot(n,nz,irn,jcn,val,"my_matrix")
which will write out two files: "my_matrix" and "my_matrix.com".
The latter is a gnuplot command file. You can either
  plot "my_matrix"
to have a look at you matrix or
   gnuplot "my_matrix.com"
to have your matrix written into a postscript file "my_matrix.ps"
(depend on the version of your gnuplot you may need to modify
the .com file).


 call dump_coo_to_hb(n,maxval(jcn(1:nz)),nz,irn,jcn,val,"my_matrix.rua")
to dump into a Harwell-Boeing formatted matrix "my_matrix.rua" and use
a HB format sparse matrix viewer such as EMILY available from the internet,