lemon-project-template-glpk

view deps/glpk/src/amd/amd_preprocess.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
line source
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 }