seq Subroutine

private subroutine seq(n, Indrow, Jpntr, Indcol, Ipntr, List, Ngrp, Maxgrp, Iwa)

given the sparsity pattern of an m by n matrix a, this subroutine determines a consistent partition of the columns of a by a sequential algorithm.

a consistent partition is defined in terms of the loopless graph g with vertices a(j), j = 1,2,...,n where a(j) is the j-th column of a and with edge (a(i),a(j)) if and only if columns i and j have a non-zero in the same row position.

a partition of the columns of a into groups is consistent if the columns in any group are not adjacent in the graph g. in graph-theory terminology, a consistent partition of the columns of a corresponds to a coloring of the graph g.

the subroutine examines the columns in the order specified by the array list, and assigns the current column to the group with the smallest possible number.

note that the value of m is not needed by seq and is therefore not present in the subroutine statement.

Arguments

Type IntentOptional Attributes Name
integer :: n

a positive integer input variable set to the number of columns of a.
integer, dimension(*) :: Indrow

an integer input array which contains the row indices for the non-zeroes in the matrix a.
integer, dimension(n+1) :: Jpntr

an integer input array of length n + 1 which specifies the locations of the row indices in indrow. the row indices for column j are indrow(k), k = jpntr(j),...,jpntr(j+1)-1. note that jpntr(n+1)-1 is then the number of non-zero elements of the matrix a.
integer, dimension(*) :: Indcol

an integer input array which contains the column indices for the non-zeroes in the matrix a.
integer, dimension(*) :: Ipntr

an integer input array of length m + 1 which specifies the locations of the column indices in indcol. the column indices for row i are indcol(k), k = ipntr(i),...,ipntr(i+1)-1. note that ipntr(m+1)-1 is then the number of non-zero elements of the matrix a.
integer, dimension(n) :: List

an integer input array of length n which specifies the order to be used by the sequential algorithm. the j-th column in this order is list(j).
integer, dimension(n) :: Ngrp

an integer output array of length n which specifies the partition of the columns of a. column jcol belongs to group ngrp(jcol).
integer :: Maxgrp

an integer output variable which specifies the number of groups in the partition of the columns of a.
integer, dimension(n) :: Iwa

an integer work array of length n

Called by

proc~~seq~~CalledByGraph proc~seq dsm_module::seq proc~dsm dsm_module::dsm proc~dsm->proc~seq proc~dsm_wrapper numerical_differentiation_module::sparsity_pattern%dsm_wrapper proc~dsm_wrapper->proc~dsm proc~compute_sparsity_random numerical_differentiation_module::compute_sparsity_random proc~compute_sparsity_random->proc~dsm_wrapper proc~compute_sparsity_random_2 numerical_differentiation_module::compute_sparsity_random_2 proc~compute_sparsity_random_2->proc~dsm_wrapper proc~set_sparsity_pattern numerical_differentiation_module::numdiff_type%set_sparsity_pattern proc~set_sparsity_pattern->proc~dsm_wrapper

Source Code

    subroutine seq(n,Indrow,Jpntr,Indcol,Ipntr,List,Ngrp,Maxgrp,Iwa)

    implicit none

    integer                :: n         !! a positive integer input variable set to the number
                                        !! of columns of `a`.
    integer                :: Maxgrp    !! an integer output variable which specifies the
                                        !! number of groups in the partition of the columns of `a`.
    integer,dimension(*)   :: Indrow    !! an integer input array which contains the row
                                        !! indices for the non-zeroes in the matrix `a`.
    integer,dimension(n+1) :: Jpntr     !! an integer input array of length `n + 1` which
                                        !! specifies the locations of the row indices in `indrow`.
                                        !! the row indices for column `j` are
                                        !! `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`.
                                        !! **note** that `jpntr(n+1)-1` is then the number of non-zero
                                        !! elements of the matrix `a`.
    integer,dimension(*)   :: Indcol    !! an integer input array which contains the
                                        !! column indices for the non-zeroes in the matrix `a`.
    integer,dimension(*)   :: Ipntr     !! an integer input array of length `m + 1` which
                                        !! specifies the locations of the column indices in `indcol`.
                                        !! the column indices for row `i` are
                                        !! `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`.
                                        !! **note** that `ipntr(m+1)-1` is then the number of non-zero
                                        !! elements of the matrix `a`.
    integer,dimension(n)   :: List      !! an integer input array of length `n` which specifies
                                        !! the order to be used by the sequential algorithm.
                                        !! the `j`-th column in this order is `list(j)`.
    integer,dimension(n)   :: Ngrp      !! an integer output array of length `n` which specifies
                                        !! the partition of the columns of `a`. column `jcol` belongs
                                        !! to group `ngrp(jcol)`.
    integer,dimension(n)   :: Iwa       !! an integer work array of length `n`

    integer :: ic , ip , ir , j , jcol , jp

    ! initialization block.

    Maxgrp = 0
    do jp = 1 , n
        Ngrp(jp) = n
        Iwa(jp) = 0
    enddo

    ! beginning of iteration loop.
    do j = 1 , n

        jcol = List(j)

        ! find all columns adjacent to column jcol.
        !
        ! determine all positions (ir,jcol) which correspond
        ! to non-zeroes in the matrix.
        do jp = Jpntr(jcol) , Jpntr(jcol+1) - 1
            ir = Indrow(jp)
            ! for each row ir, determine all positions (ir,ic)
            ! which correspond to non-zeroes in the matrix.
            do ip = Ipntr(ir) , Ipntr(ir+1) - 1
                ic = Indcol(ip)
                ! array iwa marks the group numbers of the
                ! columns which are adjacent to column jcol.
                Iwa(Ngrp(ic)) = j
            enddo
        enddo

        ! assign the smallest un-marked group number to jcol.
        do jp = 1 , Maxgrp
            if ( Iwa(jp)/=j ) then
                Maxgrp = Maxgrp - 1
                exit
            end if
        enddo
        Maxgrp = Maxgrp + 1
        Ngrp(jcol) = jp

    enddo
    ! end of iteration loop.

    end subroutine seq