source: glpk-cmake/src/glpfhv.h @ 2:4c8956a7bdf4

/* glpfhv.h (LP basis factorization, FHV eta file version) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
*  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
*  E-mail: <mao@gnu.org>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#ifndef GLPFHV_H
#define GLPFHV_H

#include "glpluf.h"

/***********************************************************************
*  The structure FHV defines the factorization of the basis mxm-matrix
*  B, where m is the number of rows in corresponding problem instance.
*
*  This factorization is the following sextet:
*
*     [B] = (F, H, V, P0, P, Q),                                     (1)
*
*  where F, H, and V are such matrices that
*
*     B = F * H * V,                                                 (2)
*
*  and P0, P, and Q are such permutation matrices that the matrix
*
*     L = P0 * F * inv(P0)                                           (3)
*
*  is lower triangular with unity diagonal, and the matrix
*
*     U = P * V * Q                                                  (4)
*
*  is upper triangular. All the matrices have the same order m, which
*  is the order of the basis matrix B.
*
*  The matrices F, V, P, and Q are stored in the structure LUF (see the
*  module GLPLUF), which is a member of the structure FHV.
*
*  The matrix H is stored in the form of eta file using row-like format
*  as follows:
*
*     H = H[1] * H[2] * ... * H[nfs],                                (5)
*
*  where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs
*  from the unity matrix only by one row, nfs is current number of row-
*  like factors. After the factorization has been built for some given
*  basis matrix B the matrix H has no factors and thus it is the unity
*  matrix. Then each time when the factorization is recomputed for an
*  adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built
*  and added to the end of the eta file H.
*
*  Being sparse vectors non-trivial rows of the factors H[k] are stored
*  in the right part of the sparse vector area (SVA) in the same manner
*  as rows and columns of the matrix F.
*
*  For more details see the program documentation. */

typedef struct FHV FHV;

struct FHV
{     /* LP basis factorization */
      int m_max;
      /* maximal value of m (increased automatically, if necessary) */
      int m;
      /* the order of matrices B, F, H, V, P0, P, Q */
      int valid;
      /* the factorization is valid only if this flag is set */
      LUF *luf;
      /* LU-factorization (contains the matrices F, V, P, Q) */
      /*--------------------------------------------------------------*/
      /* matrix H in the form of eta file */
      int hh_max;
      /* maximal number of row-like factors (which limits the number of
         updates of the factorization) */
      int hh_nfs;
      /* current number of row-like factors (0 <= hh_nfs <= hh_max) */
      int *hh_ind; /* int hh_ind[1+hh_max]; */
      /* hh_ind[k], k = 1, ..., nfs, is the number of a non-trivial row
         of factor H[k] */
      int *hh_ptr; /* int hh_ptr[1+hh_max]; */
      /* hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element
         of the non-trivial row of factor H[k] in the SVA */
      int *hh_len; /* int hh_len[1+hh_max]; */
      /* hh_len[k], k = 1, ..., nfs, is the number of non-zero elements
         in the non-trivial row of factor H[k] */
      /*--------------------------------------------------------------*/
      /* matrix P0 */
      int *p0_row; /* int p0_row[1+m_max]; */
      /* p0_row[i] = j means that p0[i,j] = 1 */
      int *p0_col; /* int p0_col[1+m_max]; */
      /* p0_col[j] = i means that p0[i,j] = 1 */
      /* if i-th row or column of the matrix F corresponds to i'-th row
         or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i
         and p0_col[i] = i' */
      /*--------------------------------------------------------------*/
      /* working arrays */
      int *cc_ind; /* int cc_ind[1+m_max]; */
      /* integer working array */
      double *cc_val; /* double cc_val[1+m_max]; */
      /* floating-point working array */
      /*--------------------------------------------------------------*/
      /* control parameters */
      double upd_tol;
      /* update tolerance; if after updating the factorization absolute
         value of some diagonal element u[k,k] of matrix U = P*V*Q is
         less than upd_tol * max(|u[k,*]|, |u[*,k]|), the factorization
         is considered as inaccurate */
      /*--------------------------------------------------------------*/
      /* some statistics */
      int nnz_h;
      /* current number of non-zeros in all factors of matrix H */
};

/* return codes: */
#define FHV_ESING    1  /* singular matrix */
#define FHV_ECOND    2  /* ill-conditioned matrix */
#define FHV_ECHECK   3  /* insufficient accuracy */
#define FHV_ELIMIT   4  /* update limit reached */
#define FHV_EROOM    5  /* SVA overflow */

#define fhv_create_it _glp_fhv_create_it
FHV *fhv_create_it(void);
/* create LP basis factorization */

#define fhv_factorize _glp_fhv_factorize
int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j,
      int ind[], double val[]), void *info);
/* compute LP basis factorization */

#define fhv_h_solve _glp_fhv_h_solve
void fhv_h_solve(FHV *fhv, int tr, double x[]);
/* solve system H*x = b or H'*x = b */

#define fhv_ftran _glp_fhv_ftran
void fhv_ftran(FHV *fhv, double x[]);
/* perform forward transformation (solve system B*x = b) */

#define fhv_btran _glp_fhv_btran
void fhv_btran(FHV *fhv, double x[]);
/* perform backward transformation (solve system B'*x = b) */

#define fhv_update_it _glp_fhv_update_it
int fhv_update_it(FHV *fhv, int j, int len, const int ind[],
      const double val[]);
/* update LP basis factorization */

#define fhv_delete_it _glp_fhv_delete_it
void fhv_delete_it(FHV *fhv);
/* delete LP basis factorization */

#endif

/* eof */