1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpfhv.h Mon Dec 06 13:09:21 2010 +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 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 */