Blame view
fvn_sparse/AMD/Source/amd_preprocess.c
3.8 KB
422234dc3
git-svn-id: https...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
/* ========================================================================= */
/* === AMD_preprocess ====================================================== */
/* ========================================================================= */
/* ------------------------------------------------------------------------- */
/* AMD, Copyright (c) Timothy A. Davis, */
/* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
/* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
/* web: http://www.cise.ufl.edu/research/sparse/amd */
/* ------------------------------------------------------------------------- */
/* Sorts, removes duplicate entries, and transposes from the nonzero pattern of
* a column-form matrix A, to obtain the matrix R. The input matrix can have
* duplicate entries and/or unsorted columns (AMD_valid (n,Ap,Ai) must not be
* AMD_INVALID).
*
* This input condition is NOT checked. This routine is not user-callable.
*/
#include "amd_internal.h"
/* ========================================================================= */
/* === AMD_preprocess ====================================================== */
/* ========================================================================= */
/* AMD_preprocess does not check its input for errors or allocate workspace.
* On input, the condition (AMD_valid (n,n,Ap,Ai) != AMD_INVALID) must hold.
*/
GLOBAL void AMD_preprocess
(
Int n, /* input matrix: A is n-by-n */
const Int Ap [ ], /* size n+1 */
const Int Ai [ ], /* size nz = Ap [n] */
/* output matrix R: */
Int Rp [ ], /* size n+1 */
Int Ri [ ], /* size nz (or less, if duplicates present) */
Int W [ ], /* workspace of size n */
Int Flag [ ] /* workspace of size n */
)
{
/* --------------------------------------------------------------------- */
/* local variables */
/* --------------------------------------------------------------------- */
Int i, j, p, p2 ;
ASSERT (AMD_valid (n, n, Ap, Ai) != AMD_INVALID) ;
/* --------------------------------------------------------------------- */
/* count the entries in each row of A (excluding duplicates) */
/* --------------------------------------------------------------------- */
for (i = 0 ; i < n ; i++)
{
W [i] = 0 ; /* # of nonzeros in row i (excl duplicates) */
Flag [i] = EMPTY ; /* Flag [i] = j if i appears in column j */
}
for (j = 0 ; j < n ; j++)
{
p2 = Ap [j+1] ;
for (p = Ap [j] ; p < p2 ; p++)
{
i = Ai [p] ;
if (Flag [i] != j)
{
/* row index i has not yet appeared in column j */
W [i]++ ; /* one more entry in row i */
Flag [i] = j ; /* flag row index i as appearing in col j*/
}
}
}
/* --------------------------------------------------------------------- */
/* compute the row pointers for R */
/* --------------------------------------------------------------------- */
Rp [0] = 0 ;
for (i = 0 ; i < n ; i++)
{
Rp [i+1] = Rp [i] + W [i] ;
}
for (i = 0 ; i < n ; i++)
{
W [i] = Rp [i] ;
Flag [i] = EMPTY ;
}
/* --------------------------------------------------------------------- */
/* construct the row form matrix R */
/* --------------------------------------------------------------------- */
/* R = row form of pattern of A */
for (j = 0 ; j < n ; j++)
{
p2 = Ap [j+1] ;
for (p = Ap [j] ; p < p2 ; p++)
{
i = Ai [p] ;
if (Flag [i] != j)
{
/* row index i has not yet appeared in column j */
Ri [W [i]++] = j ; /* put col j in row i */
Flag [i] = j ; /* flag row index i as appearing in col j*/
}
}
}
#ifndef NDEBUG
ASSERT (AMD_valid (n, n, Rp, Ri) == AMD_OK) ;
for (j = 0 ; j < n ; j++)
{
ASSERT (W [j] == Rp [j+1]) ;
}
#endif
}
|