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