===================================================== 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,