1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpfhv.h	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,170 @@
     1.4 +/* glpfhv.h (LP basis factorization, FHV eta file version) */
     1.5 +
     1.6 +/***********************************************************************
     1.7 +*  This code is part of GLPK (GNU Linear Programming Kit).
     1.8 +*
     1.9 +*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
    1.10 +*  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
    1.11 +*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.12 +*  E-mail: <mao@gnu.org>.
    1.13 +*
    1.14 +*  GLPK is free software: you can redistribute it and/or modify it
    1.15 +*  under the terms of the GNU General Public License as published by
    1.16 +*  the Free Software Foundation, either version 3 of the License, or
    1.17 +*  (at your option) any later version.
    1.18 +*
    1.19 +*  GLPK is distributed in the hope that it will be useful, but WITHOUT
    1.20 +*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.21 +*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
    1.22 +*  License for more details.
    1.23 +*
    1.24 +*  You should have received a copy of the GNU General Public License
    1.25 +*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
    1.26 +***********************************************************************/
    1.27 +
    1.28 +#ifndef GLPFHV_H
    1.29 +#define GLPFHV_H
    1.30 +
    1.31 +#include "glpluf.h"
    1.32 +
    1.33 +/***********************************************************************
    1.34 +*  The structure FHV defines the factorization of the basis mxm-matrix
    1.35 +*  B, where m is the number of rows in corresponding problem instance.
    1.36 +*
    1.37 +*  This factorization is the following sextet:
    1.38 +*
    1.39 +*     [B] = (F, H, V, P0, P, Q),                                     (1)
    1.40 +*
    1.41 +*  where F, H, and V are such matrices that
    1.42 +*
    1.43 +*     B = F * H * V,                                                 (2)
    1.44 +*
    1.45 +*  and P0, P, and Q are such permutation matrices that the matrix
    1.46 +*
    1.47 +*     L = P0 * F * inv(P0)                                           (3)
    1.48 +*
    1.49 +*  is lower triangular with unity diagonal, and the matrix
    1.50 +*
    1.51 +*     U = P * V * Q                                                  (4)
    1.52 +*
    1.53 +*  is upper triangular. All the matrices have the same order m, which
    1.54 +*  is the order of the basis matrix B.
    1.55 +*
    1.56 +*  The matrices F, V, P, and Q are stored in the structure LUF (see the
    1.57 +*  module GLPLUF), which is a member of the structure FHV.
    1.58 +*
    1.59 +*  The matrix H is stored in the form of eta file using row-like format
    1.60 +*  as follows:
    1.61 +*
    1.62 +*     H = H[1] * H[2] * ... * H[nfs],                                (5)
    1.63 +*
    1.64 +*  where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs
    1.65 +*  from the unity matrix only by one row, nfs is current number of row-
    1.66 +*  like factors. After the factorization has been built for some given
    1.67 +*  basis matrix B the matrix H has no factors and thus it is the unity
    1.68 +*  matrix. Then each time when the factorization is recomputed for an
    1.69 +*  adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built
    1.70 +*  and added to the end of the eta file H.
    1.71 +*
    1.72 +*  Being sparse vectors non-trivial rows of the factors H[k] are stored
    1.73 +*  in the right part of the sparse vector area (SVA) in the same manner
    1.74 +*  as rows and columns of the matrix F.
    1.75 +*
    1.76 +*  For more details see the program documentation. */
    1.77 +
    1.78 +typedef struct FHV FHV;
    1.79 +
    1.80 +struct FHV
    1.81 +{     /* LP basis factorization */
    1.82 +      int m_max;
    1.83 +      /* maximal value of m (increased automatically, if necessary) */
    1.84 +      int m;
    1.85 +      /* the order of matrices B, F, H, V, P0, P, Q */
    1.86 +      int valid;
    1.87 +      /* the factorization is valid only if this flag is set */
    1.88 +      LUF *luf;
    1.89 +      /* LU-factorization (contains the matrices F, V, P, Q) */
    1.90 +      /*--------------------------------------------------------------*/
    1.91 +      /* matrix H in the form of eta file */
    1.92 +      int hh_max;
    1.93 +      /* maximal number of row-like factors (which limits the number of
    1.94 +         updates of the factorization) */
    1.95 +      int hh_nfs;
    1.96 +      /* current number of row-like factors (0 <= hh_nfs <= hh_max) */
    1.97 +      int *hh_ind; /* int hh_ind[1+hh_max]; */
    1.98 +      /* hh_ind[k], k = 1, ..., nfs, is the number of a non-trivial row
    1.99 +         of factor H[k] */
   1.100 +      int *hh_ptr; /* int hh_ptr[1+hh_max]; */
   1.101 +      /* hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element
   1.102 +         of the non-trivial row of factor H[k] in the SVA */
   1.103 +      int *hh_len; /* int hh_len[1+hh_max]; */
   1.104 +      /* hh_len[k], k = 1, ..., nfs, is the number of non-zero elements
   1.105 +         in the non-trivial row of factor H[k] */
   1.106 +      /*--------------------------------------------------------------*/
   1.107 +      /* matrix P0 */
   1.108 +      int *p0_row; /* int p0_row[1+m_max]; */
   1.109 +      /* p0_row[i] = j means that p0[i,j] = 1 */
   1.110 +      int *p0_col; /* int p0_col[1+m_max]; */
   1.111 +      /* p0_col[j] = i means that p0[i,j] = 1 */
   1.112 +      /* if i-th row or column of the matrix F corresponds to i'-th row
   1.113 +         or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i
   1.114 +         and p0_col[i] = i' */
   1.115 +      /*--------------------------------------------------------------*/
   1.116 +      /* working arrays */
   1.117 +      int *cc_ind; /* int cc_ind[1+m_max]; */
   1.118 +      /* integer working array */
   1.119 +      double *cc_val; /* double cc_val[1+m_max]; */
   1.120 +      /* floating-point working array */
   1.121 +      /*--------------------------------------------------------------*/
   1.122 +      /* control parameters */
   1.123 +      double upd_tol;
   1.124 +      /* update tolerance; if after updating the factorization absolute
   1.125 +         value of some diagonal element u[k,k] of matrix U = P*V*Q is
   1.126 +         less than upd_tol * max(|u[k,*]|, |u[*,k]|), the factorization
   1.127 +         is considered as inaccurate */
   1.128 +      /*--------------------------------------------------------------*/
   1.129 +      /* some statistics */
   1.130 +      int nnz_h;
   1.131 +      /* current number of non-zeros in all factors of matrix H */
   1.132 +};
   1.133 +
   1.134 +/* return codes: */
   1.135 +#define FHV_ESING    1  /* singular matrix */
   1.136 +#define FHV_ECOND    2  /* ill-conditioned matrix */
   1.137 +#define FHV_ECHECK   3  /* insufficient accuracy */
   1.138 +#define FHV_ELIMIT   4  /* update limit reached */
   1.139 +#define FHV_EROOM    5  /* SVA overflow */
   1.140 +
   1.141 +#define fhv_create_it _glp_fhv_create_it
   1.142 +FHV *fhv_create_it(void);
   1.143 +/* create LP basis factorization */
   1.144 +
   1.145 +#define fhv_factorize _glp_fhv_factorize
   1.146 +int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j,
   1.147 +      int ind[], double val[]), void *info);
   1.148 +/* compute LP basis factorization */
   1.149 +
   1.150 +#define fhv_h_solve _glp_fhv_h_solve
   1.151 +void fhv_h_solve(FHV *fhv, int tr, double x[]);
   1.152 +/* solve system H*x = b or H'*x = b */
   1.153 +
   1.154 +#define fhv_ftran _glp_fhv_ftran
   1.155 +void fhv_ftran(FHV *fhv, double x[]);
   1.156 +/* perform forward transformation (solve system B*x = b) */
   1.157 +
   1.158 +#define fhv_btran _glp_fhv_btran
   1.159 +void fhv_btran(FHV *fhv, double x[]);
   1.160 +/* perform backward transformation (solve system B'*x = b) */
   1.161 +
   1.162 +#define fhv_update_it _glp_fhv_update_it
   1.163 +int fhv_update_it(FHV *fhv, int j, int len, const int ind[],
   1.164 +      const double val[]);
   1.165 +/* update LP basis factorization */
   1.166 +
   1.167 +#define fhv_delete_it _glp_fhv_delete_it
   1.168 +void fhv_delete_it(FHV *fhv);
   1.169 +/* delete LP basis factorization */
   1.170 +
   1.171 +#endif
   1.172 +
   1.173 +/* eof */