QR_MUMPS
Functions/Subroutines
qrm_rowcount.F90 File Reference

This file contains the routine that computes the rowcount for the R factor. More...

Go to the source code of this file.

Functions/Subroutines

subroutine _qrm_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)
 

Detailed Description

This file contains the routine that computes the rowcount for the R factor.

Date
2016-01-29 22:22:30 +0100 (Fri, 29 Jan 2016)
Author
abuttari
Version
1.1
Revision
2075

Definition in file qrm_rowcount.F90.

Function/Subroutine Documentation

subroutine _qrm_rowcount ( type(_qrm_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 105 of file qrm_rowcount.F90.

References setfind(), and setunion().

Referenced by _qrm_analyse().

integer function _qrm_rowcount::flip ( integer  p)

Definition at line 372 of file qrm_rowcount.F90.

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

Definition at line 339 of file qrm_rowcount.F90.

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

Definition at line 364 of file qrm_rowcount.F90.

integer function _qrm_rowcount::unflip ( integer  p)

Definition at line 381 of file qrm_rowcount.F90.