#include "superlu_ddefs.h"
Defines | |
#define | T2_SUPER |
Functions | |
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) |
-- 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 T2_SUPER |
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 | jcol, | |
const int_t * | perm_r, | |||
const int_t | pivrow, | |||
const int_t | nseg, | |||
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.