QR_MUMPS
 All Classes Files Functions Variables Enumerations Enumerator Pages
Functions/Subroutines
dqrm_rowcount.F90 File Reference

Go to the source code of this file.

Functions/Subroutines

subroutine dqrm_rowcount (graph, parent, porder, rc)
 This subroutine computes the rowcount of the R factor. More...
 
integer function setfind (setpath, p_leaf)
 
subroutine setunion (setpath, j, pj)
 
integer function flip (p)
 
integer function unflip (p)
 

Function/Subroutine Documentation

subroutine dqrm_rowcount ( type(dqrm_spmat_type)  graph,
integer, dimension(:)  parent,
integer, dimension(:)  porder,
integer, dimension(:)  rc 
)

This subroutine computes the rowcount of the R factor.

The mothod implemented here is described in:

  1. J. R. Gilbert, X. S. Li, E. G. Ng, and B. W. Peyton, 2001. "Computing row and column counts for sparse QR and LU factorization." BIT Numer. Math. 41, 4, 693–710.
  2. J. R. Gilbert , E. G. Ng , B. W. Peyton, 1994 "An Efficient Algorithm to Compute Row and Column Counts for Sparse Cholesky Factorization." SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1075-1091, Oct. 1994

The algorithm on Fig. 3.2 in [1] was (easily) extended with supernodes detection as described in [2].

Also, on output, the tree is modified in order to reflect the supernodal structure.

Parameters
[in]graphthe graph associated to A (or a pruned version if singleton detection was done)
[out]rcthe row count. rc(i)=k means that in the k-th row of R there are k nonzeroes; k=0 for all the subordinate variables. This also gives us the size of the rows of front i.
[in,out]porderon input an integer array containing a postorder of the tree. On output it contains an equivalent postorder where principal variables come always before the correspondig subordinates. Other routines rely on this postorder and thus it should never be changed.
[in,out]parentan integer array containing the elimination tree in input and the assembly tree on output. The meaning of parent on output is:
  1. parent(i) = j>0: i is the principal variable of a node and j if the principal variable of its father node
  2. parent(i) = j=0: i is a principal variable of a root node
  3. parent(i) = j<0: i is a subordinate variable inside a node whose principal variable is j.

Example output:

         +---+
         |7  |
         | 6 |           
         |  5|           parent=(/ -1, 7, -4, 7, -7, -7, 0 /)
         +---+
        /     \
       /       \
   +--+         +--+
   |2 |         |4 |
   | 1|         | 3|
   +--+         +--+
Warning
at the moment the detection of supernodes is turned off (see comments in the code). This is due to the fact that supernodes are detected by the amalgamation routine qrm_amalg_tree. As a result, all the entries of parent will be positive on output.

Definition at line 104 of file dqrm_rowcount.F90.

References i, qrm_error_mod::qrm_err_act_restore(), qrm_error_mod::qrm_err_act_save(), qrm_error_mod::qrm_err_check(), setfind(), and setunion().

Referenced by dqrm_analyse().

integer function dqrm_rowcount::flip ( integer  p)

Definition at line 371 of file dqrm_rowcount.F90.

References flip().

integer function dqrm_rowcount::setfind ( integer, dimension(:)  setpath,
integer  p_leaf 
)

Definition at line 338 of file dqrm_rowcount.F90.

Referenced by _qrm_rowcount(), dqrm_rowcount(), and setfind().

subroutine dqrm_rowcount::setunion ( integer, dimension(:)  setpath,
integer  j,
integer  pj 
)

Definition at line 363 of file dqrm_rowcount.F90.

Referenced by _qrm_rowcount(), and dqrm_rowcount().

integer function dqrm_rowcount::unflip ( integer  p)

Definition at line 380 of file dqrm_rowcount.F90.

References unflip().