Zoltan User's Guide  |  Next  |  Previous

Ordering Functions

Zoltan provides functions for ordering a set of objects, typically given as a graph (which may correspond to a sparse matrix). The following functions are the ordering interface functions in Zoltan. The first is the main function, and the others are accessor functions that should only be called after Zoltan_Order.
C: int Zoltan_Order (
      struct Zoltan_Struct *zz,
      int num_gid_entries,
      int num_obj,
      ZOLTAN_ID_PTR global_ids,
      ZOLTAN_ID_PTR rank,
      )
FORTRAN: FUNCTION Zoltan_Order(zz, num_gid_entries, num_obj, global_ids, rank, iperm)
INTEGER(Zoltan_INT) :: Zoltan_Order
TYPE(Zoltan_Struct), INTENT(IN) :: zz
INTEGER(Zoltan_INT), INTENT(IN) :: num_gid_entries
INTEGER(Zoltan_INT), INTENT(IN) :: num_obj
INTEGER(Zoltan_INT) :: global_ids(*)
INTEGER(Zoltan_INT) :: rank(*)
C++: int Zoltan::Order (
      int num_gid_entries,
      int num_obj,
      ZOLTAN_ID_PTR global_ids,
      ZOLTAN_ID_PTR rank,
      )
Zoltan_Order invokes the ordering routine specified by the  ORDER_METHOD parameter. Results of the ordering is returned in the array rank .

  • rank[i] gives the rank of global_ids[i] in the computed ordering, which is a number between 0 and N-1 where N is the overall number of objects across all the processors. (Note: This will change in future versions. A permuted set of GIDs will be returned instead.)
    • The arrays global_ids, rank, should all be allocated by the application before Zoltan_Order is called. Each array must have space for (at least) num_obj elements, where num_obj is the number of objects the user want to know informations about.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, to be used in this invocation of the load-balancing routine.
        num_gid_entries Input: the number of array entries used to describe a single global ID.  This value is the maximum value over all processors of the parameter NUM_GID_ENTRIES.
        num_obj Number of objects for which we want to know the ordering. Objects may be non-local.
        global_ids An array of global IDs of objects for which we want to know the ordering on this processor. Size of this array must be num_obj.
    Objects may be non-local. Objects IDs may be repeated on several processor.
        rank Upon return, an array of length num_obj containing the rank of each object in the computed ordering. When rank[i] = j, that means that the object corresponding to global_ids[i] is the jth object in the ordering. (This array corresponds directly to the perm array in METIS and the order array in ParMETIS.) Note that the rank may refer to either a local or a global ordering, depending on ORDER_TYPE.  Memory for this array must have been allocated before Zoltan_Order is called.
    Returned Value:
        int Error code.

    Accessors

    Zoltan primarily supports nested dissection orderings, which are typically used to reduce fill in direct solvers. For this use case, it is important to get additional information (the separators). The accessor functions below define the Zoltan interface. Note that these functions should be called after Zoltan_Order.
    C: int Zoltan_Order_Get_Num_Blocks (
          struct Zoltan_Struct *zz)
    C++: int Zoltan::Order_Get_Num_Blocks ()
    Zoltan_Order_Get_Num_Blocks returns the number of subdomains (or column blocks) computed during the ordering. For a Nested Dissection based ordering method, it corresponds to the sum of the separators and the subgraphs of the lowest level. For example, after one bisection the number of blocks is three.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, which has been used in the ordering routine.
    Returned Value:
        int The number of blocks (subdomains).

    C: int Zoltan_Order_Get_Block_Bounds (
          struct Zoltan_Struct *zz,
          int block_id,
          int *first,
          int *last)
    C++: int Zoltan::Order_Get_Block_Bounds (
          int block_id,
          int &first,
          int &last)
    Zoltan_Order_Get_Block_Bounds gives the boundaries of the given block. The first and last parameters contain upon return the indices of the begin and the end of the block. These indices are from the global continuous numbering between 1 and N-1 of the N distributed objects.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, which has been used in the ordering routine.
        block_id The number of the block we want informations on.
        first Upon return, pointer to the value of the begining of the block.
        last Upon return, pointer to the value of the end of the block.
    Returned Value:
        int Error code.

    C: int Zoltan_Order_Get_Block_Size (
          struct Zoltan_Struct *zz,
          int block_id)
    C++: int Zoltan::Order_Get_Block_Size (
          int block_id)
    Zoltan_Order_Get_Block_Size returns the number of objects in the block block_id.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, which has been used in the ordering routine.
        block_id The indice of the block we want to know the size.
    Returned Value:
        int The number of objects in this given block.

    C: int Zoltan_Order_Get_Block_Parent (
          struct Zoltan_Struct *zz,
          int block_id)
    C++: int Zoltan::Order_Get_Block_Parent (
          int block_id)
    Zoltan_Order_Get_Block_Parent returns the number (id) of the parent block in the elimination tree. The value is -1 for the root of the tree.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, which has been used in the ordering routine.
        block_id The indice of the block we want to know the size.
    Returned Value:
        int The number (id) of the parent block in the elimination tree. The value is -1 for the root of the tree.

    C: int Zoltan_Order_Get_Num_Leaves (
          struct Zoltan_Struct *zz)
    C++: int Zoltan::Order_Get_Num_Leaves ()
    Zoltan_Order_Get_Num_Leaves returns the number of leaves in the elimination tree.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, which has been used in the ordering routine.
    Returned Value:
        int The number of leaves in the elimination tree.

    C: void Zoltan_Order_Get_Block_Leaves (
          struct Zoltan_Struct *zz,
          int *leaves)
    C++: void Zoltan::Order_Get_Block_Leaves (
          struct Zoltan_Struct *zz,
          int *leaves)
    Zoltan_Order_Get_Block_Leaves get the indices of the blocks that are leaves in the elimination tree.
     
    Arguments:
        zz Pointer to the Zoltan structure, created by Zoltan_Create, which has been used in the ordering routine.
        leaves Array of indices of the blocks that are leaves in the elimination. The last element of this array is -1. The array must be of size number of leave + 1 and must be allocated by the user before the call.

    [Table of Contents  | Next:  Coloring Functions  |  Previous:  Migration Functions  |  Privacy and Security]