SRC/symbfact.c File Reference

Performs a symbolic factorization. More...

#include "superlu_ddefs.h"

Defines

#define T2_SUPER

Functions/Subroutines

static void relax_snode (const int_t n,int_t *et,const int_t relax,int_t *desc,int_t *relax_end)
static int_t snode_dfs (SuperMatrix *A,const int_t jcol,const int_t kcol,int_t *xprune,int_t *marker,Glu_persist_t *Glu_persist,Glu_freeable_t *Glu_freeable)
static int_t column_dfs (SuperMatrix *A,const int_t jcol,int_t *perm_r,int_t *nseg,int_t *segrep,int_t *repfnz,int_t *xprune,int_t *marker,int_t *parent,int_t *xplore,Glu_persist_t *Glu_persist,Glu_freeable_t *Glu_freeable)
static int_t pivotL (const int_t jcol,int_t *perm_r,int_t *pivrow,Glu_persist_t *Glu_persist,Glu_freeable_t *Glu_freeable)
static int_t set_usub (const int_t n,const int_t jcol,const int_t nseg,int_t *segrep,int_t *repfnz,Glu_persist_t *Glu_persist,Glu_freeable_t *Glu_freeable)
static void pruneL (const int_t, const int_t *, const int_t, const int_t, const int_t *, const int_t *, int_t *, Glu_persist_t *, Glu_freeable_t *)
int_t symbfact (superlu_options_t *options, int pnum, SuperMatrix *A, int_t *perm_c, int_t *etree, Glu_persist_t *Glu_persist, Glu_freeable_t *Glu_freeable)


Detailed Description

 -- Distributed SuperLU routine (version 1.0) --
 Lawrence Berkeley National Lab, Univ. of California Berkeley.
 September 1, 1999

  Copyright (c) 1994 by Xerox Corporation.  All rights reserved.

  THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
  EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.

  Permission is hereby granted to use or copy this program for any
  purpose, provided the above notices are retained on all copies.
  Permission to modify the code and to distribute modified code is
  granted, provided the above notices are retained, and a notice that
  the code was modified is included with the above copyright notice.
 

Define Documentation

#define T2_SUPER


Function Documentation

static int_t column_dfs ( SuperMatrix A,
const int_t  jcol,
int_t perm_r,
int_t nseg,
int_t segrep,
int_t repfnz,
int_t xprune,
int_t marker,
int_t parent,
int_t xplore,
Glu_persist_t Glu_persist,
Glu_freeable_t Glu_freeable 
) [static]

 Purpose
 =======
   column_dfs() performs a symbolic factorization on column jcol, and
   detects the supernode boundary. This routine uses the row indices of
   A[*,jcol] to start the depth-first search (DFS).

 Output
 ======
   A supernode representative is the last column of a supernode.
   The nonzeros in U[*,j] are segments that end at supernodal
   representatives. The routine returns a list of such supernodal 
   representatives ( segrep[*] ) in topological order of the DFS that 
   generates them. The location of the first nonzero in each such 
   supernodal segment is also returned ( repfnz[*] ).

 Data structure
 ==============
   (lsub, xlsub):
      lsub[*] contains the compressed subscripts of the supernodes;
      xlsub[j] points to the starting location of the j-th column in
               lsub[*]; 
	Storage: original row subscripts in A.

      During the course of symbolic factorization, we also use
	(lsub, xlsub, xprune) for the purpose of symmetric pruning.
      For each supernode {s,s+1,...,t=s+r} with first column s and last
	column t, there are two subscript sets,  the last column
      structures (for pruning) will be removed in the end.
        o lsub[j], j = xlsub[s], ..., xlsub[s+1]-1
          is the structure of column s (i.e. structure of this supernode).
          It is used for the storage of numerical values.
	  o lsub[j], j = xlsub[t], ..., xlsub[t+1]-1
	    is the structure of the last column t of this supernode.
	    It is for the purpose of symmetric pruning. Therefore, the
	    structural subscripts can be rearranged without making physical
	    interchanges among the numerical values.

      (1) if t > s, only the subscript sets for column s and column t
          are stored. Column t represents pruned adjacency structure.

                  --------------------------------------------
          lsub[*]    ... |   col s    |   col t   | ...
                  --------------------------------------------
                          ^            ^           ^
                       xlsub[s]    xlsub[s+1]  xlsub[t+1]
                                       :           :
                                       :         xprune[t]
                                   xlsub[t]      
                                   xprune[s]

      (2) if t == s, i.e., a singleton supernode, the same subscript set
          is used for both G(L) and pruned graph:

                  --------------------------------------
          lsub[*]    ... |      s     | ...
                  --------------------------------------
                          ^            ^   
                       xlsub[s]   xlsub[s+1]  
                                  xprune[s]

       DFS will traverse the second subscript list, i.e., the part of the
       pruned graph.

 Local parameters
 ================
   nseg: no of segments in current U[*,j]
   jsuper: jsuper=EMPTY if column j does not belong to the same
	supernode as j-1. Otherwise, jsuper=nsuper.

   marker: A-row --> A-row/col (0/1)
   repfnz: SuperA-col --> PA-row
   parent: SuperA-col --> SuperA-col
   xplore: SuperA-col --> index to L-structure

 Return value
 ============
     0  success;
   > 0  number of bytes allocated when run out of space.
 

static int_t pivotL ( const int_t  jcol,
int_t perm_r,
int_t pivrow,
Glu_persist_t Glu_persist,
Glu_freeable_t Glu_freeable 
) [static]

 Purpose
 =======
   pivotL() interchanges row subscripts so that each diagonal block of a
   supernode in L has the row subscripts sorted in order of pivots.
   The row subscripts in the off-diagonal block are not sorted.
 

static void pruneL ( const   int_t,
const int_t perm_r,
const   int_t,
const   int_t,
const int_t segrep,
const int_t repfnz,
int_t xprune,
Glu_persist_t Glu_persist,
Glu_freeable_t Glu_freeable 
) [static]

static void relax_snode ( const int_t  n,
int_t et,
const int_t  relax,
int_t desc,
int_t relax_end 
) [static]

 Purpose
 =======
   relax_snode() identifies the initial relaxed supernodes, assuming that 
   the matrix has been reordered according to an postorder of the etree.
 

static int_t set_usub ( const int_t  n,
const int_t  jcol,
const int_t  nseg,
int_t segrep,
int_t repfnz,
Glu_persist_t Glu_persist,
Glu_freeable_t Glu_freeable 
) [static]

 
 Purpose
 =======
   set_usub() sets up data structure to store supernodal segments in U.
   The supernodal segments in each column are stored in topological order.

 NOTE
 ====
   For each supernodal segment, we only store the index of the first
   nonzero index, rather than the indices of the whole segment, because
   those indices can be generated from first nonzero and supnodal
   representative.
   Therefore, for G(U), we store the "skeleton" of it.
 

static int_t snode_dfs ( SuperMatrix A,
const int_t  jcol,
const int_t  kcol,
int_t xprune,
int_t marker,
Glu_persist_t Glu_persist,
Glu_freeable_t Glu_freeable 
) [static]

 
 Purpose
 =======
    snode_dfs() determines the union of the row structures of those 
    columns within the relaxed snode.
    Note: The relaxed snodes are leaves of the supernodal etree, therefore, 
    the part outside the rectangular supernode must be zero.

 Return value
 ============
    0   success;
   >0   number of bytes allocated when run out of memory.
 

int_t symbfact ( superlu_options_t options,
int  pnum,
SuperMatrix A,
int_t perm_c,
int_t etree,
Glu_persist_t Glu_persist,
Glu_freeable_t Glu_freeable 
)

 Purpose
 =======
   symbfact() performs a symbolic factorization on matrix A and sets up 
   the nonzero data structures which are suitable for supernodal Gaussian
   elimination with no pivoting (GENP). This routine features:
        o depth-first search (DFS)
        o supernodes
        o symmetric structure pruning

 Return value
 ============
   < 0, number of bytes needed for LSUB.
   = 0, matrix dimension is 1.
   > 0, number of bytes allocated when out of memory.
 


Generated on Wed Nov 24 18:17:32 2010 for SuperLUDistributed by  doxygen 1.5.5