QR_MUMPS
 All Classes Files Functions Variables Enumerations Enumerator Pages
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 104 of file qrm_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 _qrm_analyse().

integer function _qrm_rowcount::flip ( integer  p)

Definition at line 371 of file qrm_rowcount.F90.

References flip().

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

Definition at line 338 of file qrm_rowcount.F90.

References setfind().

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

Definition at line 363 of file qrm_rowcount.F90.

integer function _qrm_rowcount::unflip ( integer  p)

Definition at line 380 of file qrm_rowcount.F90.

References unflip().