lemon-project-template-glpk

annotate deps/glpk/src/amd/amd_preprocess.c @ 10:5545663ca997

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