/* 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, 2011 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 */