diff -r d59bea55db9b -r c445c931472f src/glpfhv.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/glpfhv.h Mon Dec 06 13:09:21 2010 +0100 @@ -0,0 +1,170 @@ +/* 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: . +* +* 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 . +***********************************************************************/ + +#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 */