md Subroutine

subroutine md(N, Ia, Ja, Max, V, L, Head, Last, Next, Mark, Flag)

md – minimum degree algorithm (based on element model)

description

md finds a minimum degree ordering of the rows and columns of a
general sparse matrix m stored in (ia,ja,a) format.
when the structure of m is nonsymmetric, the ordering is that
obtained for the symmetric matrix  m + m-transpose.

additional parameters

MAX

: declared dimension of the one-dimensional arrays v and l.
max must be at least  n+2k,  where k is the number of
nonzeroes in the strict upper triangle of m + m-transpose

V

: integer one-dimensional work array.  dimension = max

L

: integer one-dimensional work array.  dimension = max

HEAD

: integer one-dimensional work array.  dimension = n

LAST

: integer one-dimensional array used to return the permutation
of the rows and columns of m corresponding to the minimum
degree ordering.  dimension = n

NEXT

: integer one-dimensional array used to return the inverse of
the permutation returned in last.  dimension = n

MARK

: integer one-dimensional work array (may be the same as v).
dimension = n

FLAG

: integer error flag.  values and their meanings are -

         0     no errors detected
         9n+k  insufficient storage in md

definitions of internal parameters

    ---------+---------------------------------------------------------
    v(s)     - value field of list entry
    ---------+---------------------------------------------------------
    l(s)     - link field of list entry  (0 =) end of list)
    ---------+---------------------------------------------------------
    l(vi)    - pointer to element list of uneliminated vertex vi
    ---------+---------------------------------------------------------
    l(ej)    - pointer to boundary list of active element ej
    ---------+---------------------------------------------------------
    head(d)  - vj =) vj head of d-list d
             -  0 =) no vertex in d-list d


             -                  vi uneliminated vertex
             -          vi in ek           -       vi not in ek
    ---------+-----------------------------+---------------------------
    next(vi) - undefined but nonnegative   - vj =) vj next in d-list
             -                             -  0 =) vi tail of d-list
    ---------+-----------------------------+---------------------------
    last(vi) - (not set until mdp)         - -d =) vi head of d-list d
             --vk =) compute degree        - vj =) vj last in d-list
             - ej =) vi prototype of ej    -  0 =) vi not in any d-list
             -  0 =) do not compute degree -
    ---------+-----------------------------+---------------------------
    mark(vi) - mark(vk)                    - nonneg. tag .lt. mark(vk)


             -                   vi eliminated vertex
             -      ei active element      -           otherwise
    ---------+-----------------------------+---------------------------
    next(vi) - -j =) vi was j-th vertex    - -j =) vi was j-th vertex
             -       to be eliminated      -       to be eliminated
    ---------+-----------------------------+---------------------------
    last(vi) -  m =) size of ei = m        - undefined
    ---------+-----------------------------+---------------------------
    mark(vi) - -m =) overlap count of ei   - undefined
             -       with ek = m           -
             - otherwise nonnegative tag   -
             -       .lt. mark(vk)         -

Arguments

Type IntentOptional Attributes Name
integer :: N
integer :: Ia(*)
integer :: Ja(*)
integer :: Max
integer :: V(*)
integer :: L(*)
integer, intent(inout) :: Head(*)
integer, intent(inout) :: Last(*)
integer, intent(inout) :: Next(*)
integer :: Mark(*)
integer :: Flag

Calls

proc~~md~~CallsGraph proc~md md.inc::md mdi mdi proc~md->mdi mdm mdm proc~md->mdm mdp mdp proc~md->mdp mdu mdu proc~md->mdu

Variables

Type Visibility Attributes Name Initial
integer, public :: dmin
integer, public :: ek
integer, public :: k
integer, public :: tag
integer, public :: tail
integer, public :: vk

Source Code

subroutine md(N,Ia,Ja,Max,V,L,Head,Last,Next,Mark,Flag)

integer               :: N
integer               :: Ia(*)
integer               :: Ja(*)
integer               :: Max
integer               :: V(*)
integer               :: L(*)
integer,intent(inout) :: Head(*)
integer,intent(inout) :: Last(*)
integer,intent(inout) :: Next(*)
integer               :: Mark(*)
integer               :: Flag

integer :: dmin, ek, k, tag, tail, vk

equivalence (vk,ek)

   !----initialization
   tag = 0
   call mdi(N,Ia,Ja,Max,V,L,Head,Last,Next,Mark,tag,Flag)
   if ( Flag/=0 ) return
   !
   k = 0
   dmin = 1
   !
   !----while  k .lt. n  do
   do while ( k<N )
   !
   !------search for vertex of minimum degree
      do while ( Head(dmin)<=0 )
         dmin = dmin + 1
      enddo
   !
   !------remove vertex vk of minimum degree from degree list
      vk = Head(dmin)
      Head(dmin) = Next(vk)
      if ( Head(dmin)>0 ) Last(Head(dmin)) = -dmin
   !
   !------number vertex vk, adjust tag, and tag vk
      k = k + 1
      Next(vk) = -k
      Last(ek) = dmin - 1
      tag = tag + Last(ek)
      Mark(vk) = tag
   !
   !------form element ek from uneliminated neighbors of vk
      call mdm(vk,tail,V,L,Last,Next,Mark)
   !
   !------purge inactive elements and do mass elimination
      call mdp(k,ek,tail,V,L,Head,Last,Next,Mark)
   !
   !------update degrees of uneliminated vertices in ek
   !
      call mdu(ek,dmin,V,L,Head,Last,Next,Mark)
   enddo
   !
   !----generate inverse permutation from permutation
   do k = 1, N
      Next(k) = -Next(k)
      Last(Next(k)) = k
   enddo

end subroutine md