=====================================================
MONET
(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
. . .
where
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, &
cntrl,row_sta,column_order,column_sta)
where the last three arguments are optional.
Details of the arguments are as follows.
#ifdef BIT64
INTEGER, PARAMETER :: myint = INT64
#else
INTEGER, PARAMETER :: myint = INT32
#endif
INTEGER, PARAMETER :: myreal = DOUBLE
! ======================== 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
do
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).
or
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,