|
static void | relax_snode (int_t, int_t *, int_t, int_t *, int_t *) |
|
static int_t | snode_dfs (SuperMatrix *, const int_t, const int_t, int_t *, int_t *, Glu_persist_t *, Glu_freeable_t *) |
|
static int_t | column_dfs (superlu_dist_options_t *, SuperMatrix *, const int_t, int_t *, int_t *, int_t *, int_t *, int_t *, int_t *, int_t *, int_t *, Glu_persist_t *, Glu_freeable_t *) |
|
static int_t | pivotL (const int_t, int_t *, int_t *, Glu_persist_t *, Glu_freeable_t *) |
|
static int_t | set_usub (const int_t, const int_t, const int_t, int_t *, int_t *, Glu_persist_t *, Glu_freeable_t *) |
|
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_dist_options_t *options, int pnum, SuperMatrix *A, int_t *perm_c, int_t *etree, Glu_persist_t *Glu_persist, Glu_freeable_t *Glu_freeable) |
|
Performs a symbolic factorization.
Copyright (c) 2003, The Regents of the University of California, through Lawrence Berkeley National Laboratory (subject to receipt of any required approvals from U.S. Dept. of Energy)
All rights reserved.
The source code is distributed under BSD license, see the file License.txt at the top-level directory.
-- 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.
static int_t column_dfs |
( |
superlu_dist_options_t * |
options, |
|
|
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.