alpar@1: /* glpfhv.h (LP basis factorization, FHV eta file version) */ alpar@1: alpar@1: /*********************************************************************** alpar@1: * This code is part of GLPK (GNU Linear Programming Kit). alpar@1: * alpar@1: * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, alpar@1: * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, alpar@1: * Moscow Aviation Institute, Moscow, Russia. All rights reserved. alpar@1: * E-mail: . alpar@1: * alpar@1: * GLPK is free software: you can redistribute it and/or modify it alpar@1: * under the terms of the GNU General Public License as published by alpar@1: * the Free Software Foundation, either version 3 of the License, or alpar@1: * (at your option) any later version. alpar@1: * alpar@1: * GLPK is distributed in the hope that it will be useful, but WITHOUT alpar@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY alpar@1: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public alpar@1: * License for more details. alpar@1: * alpar@1: * You should have received a copy of the GNU General Public License alpar@1: * along with GLPK. If not, see . alpar@1: ***********************************************************************/ alpar@1: alpar@1: #ifndef GLPFHV_H alpar@1: #define GLPFHV_H alpar@1: alpar@1: #include "glpluf.h" alpar@1: alpar@1: /*********************************************************************** alpar@1: * The structure FHV defines the factorization of the basis mxm-matrix alpar@1: * B, where m is the number of rows in corresponding problem instance. alpar@1: * alpar@1: * This factorization is the following sextet: alpar@1: * alpar@1: * [B] = (F, H, V, P0, P, Q), (1) alpar@1: * alpar@1: * where F, H, and V are such matrices that alpar@1: * alpar@1: * B = F * H * V, (2) alpar@1: * alpar@1: * and P0, P, and Q are such permutation matrices that the matrix alpar@1: * alpar@1: * L = P0 * F * inv(P0) (3) alpar@1: * alpar@1: * is lower triangular with unity diagonal, and the matrix alpar@1: * alpar@1: * U = P * V * Q (4) alpar@1: * alpar@1: * is upper triangular. All the matrices have the same order m, which alpar@1: * is the order of the basis matrix B. alpar@1: * alpar@1: * The matrices F, V, P, and Q are stored in the structure LUF (see the alpar@1: * module GLPLUF), which is a member of the structure FHV. alpar@1: * alpar@1: * The matrix H is stored in the form of eta file using row-like format alpar@1: * as follows: alpar@1: * alpar@1: * H = H[1] * H[2] * ... * H[nfs], (5) alpar@1: * alpar@1: * where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs alpar@1: * from the unity matrix only by one row, nfs is current number of row- alpar@1: * like factors. After the factorization has been built for some given alpar@1: * basis matrix B the matrix H has no factors and thus it is the unity alpar@1: * matrix. Then each time when the factorization is recomputed for an alpar@1: * adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built alpar@1: * and added to the end of the eta file H. alpar@1: * alpar@1: * Being sparse vectors non-trivial rows of the factors H[k] are stored alpar@1: * in the right part of the sparse vector area (SVA) in the same manner alpar@1: * as rows and columns of the matrix F. alpar@1: * alpar@1: * For more details see the program documentation. */ alpar@1: alpar@1: typedef struct FHV FHV; alpar@1: alpar@1: struct FHV alpar@1: { /* LP basis factorization */ alpar@1: int m_max; alpar@1: /* maximal value of m (increased automatically, if necessary) */ alpar@1: int m; alpar@1: /* the order of matrices B, F, H, V, P0, P, Q */ alpar@1: int valid; alpar@1: /* the factorization is valid only if this flag is set */ alpar@1: LUF *luf; alpar@1: /* LU-factorization (contains the matrices F, V, P, Q) */ alpar@1: /*--------------------------------------------------------------*/ alpar@1: /* matrix H in the form of eta file */ alpar@1: int hh_max; alpar@1: /* maximal number of row-like factors (which limits the number of alpar@1: updates of the factorization) */ alpar@1: int hh_nfs; alpar@1: /* current number of row-like factors (0 <= hh_nfs <= hh_max) */ alpar@1: int *hh_ind; /* int hh_ind[1+hh_max]; */ alpar@1: /* hh_ind[k], k = 1, ..., nfs, is the number of a non-trivial row alpar@1: of factor H[k] */ alpar@1: int *hh_ptr; /* int hh_ptr[1+hh_max]; */ alpar@1: /* hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element alpar@1: of the non-trivial row of factor H[k] in the SVA */ alpar@1: int *hh_len; /* int hh_len[1+hh_max]; */ alpar@1: /* hh_len[k], k = 1, ..., nfs, is the number of non-zero elements alpar@1: in the non-trivial row of factor H[k] */ alpar@1: /*--------------------------------------------------------------*/ alpar@1: /* matrix P0 */ alpar@1: int *p0_row; /* int p0_row[1+m_max]; */ alpar@1: /* p0_row[i] = j means that p0[i,j] = 1 */ alpar@1: int *p0_col; /* int p0_col[1+m_max]; */ alpar@1: /* p0_col[j] = i means that p0[i,j] = 1 */ alpar@1: /* if i-th row or column of the matrix F corresponds to i'-th row alpar@1: or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i alpar@1: and p0_col[i] = i' */ alpar@1: /*--------------------------------------------------------------*/ alpar@1: /* working arrays */ alpar@1: int *cc_ind; /* int cc_ind[1+m_max]; */ alpar@1: /* integer working array */ alpar@1: double *cc_val; /* double cc_val[1+m_max]; */ alpar@1: /* floating-point working array */ alpar@1: /*--------------------------------------------------------------*/ alpar@1: /* control parameters */ alpar@1: double upd_tol; alpar@1: /* update tolerance; if after updating the factorization absolute alpar@1: value of some diagonal element u[k,k] of matrix U = P*V*Q is alpar@1: less than upd_tol * max(|u[k,*]|, |u[*,k]|), the factorization alpar@1: is considered as inaccurate */ alpar@1: /*--------------------------------------------------------------*/ alpar@1: /* some statistics */ alpar@1: int nnz_h; alpar@1: /* current number of non-zeros in all factors of matrix H */ alpar@1: }; alpar@1: alpar@1: /* return codes: */ alpar@1: #define FHV_ESING 1 /* singular matrix */ alpar@1: #define FHV_ECOND 2 /* ill-conditioned matrix */ alpar@1: #define FHV_ECHECK 3 /* insufficient accuracy */ alpar@1: #define FHV_ELIMIT 4 /* update limit reached */ alpar@1: #define FHV_EROOM 5 /* SVA overflow */ alpar@1: alpar@1: #define fhv_create_it _glp_fhv_create_it alpar@1: FHV *fhv_create_it(void); alpar@1: /* create LP basis factorization */ alpar@1: alpar@1: #define fhv_factorize _glp_fhv_factorize alpar@1: int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j, alpar@1: int ind[], double val[]), void *info); alpar@1: /* compute LP basis factorization */ alpar@1: alpar@1: #define fhv_h_solve _glp_fhv_h_solve alpar@1: void fhv_h_solve(FHV *fhv, int tr, double x[]); alpar@1: /* solve system H*x = b or H'*x = b */ alpar@1: alpar@1: #define fhv_ftran _glp_fhv_ftran alpar@1: void fhv_ftran(FHV *fhv, double x[]); alpar@1: /* perform forward transformation (solve system B*x = b) */ alpar@1: alpar@1: #define fhv_btran _glp_fhv_btran alpar@1: void fhv_btran(FHV *fhv, double x[]); alpar@1: /* perform backward transformation (solve system B'*x = b) */ alpar@1: alpar@1: #define fhv_update_it _glp_fhv_update_it alpar@1: int fhv_update_it(FHV *fhv, int j, int len, const int ind[], alpar@1: const double val[]); alpar@1: /* update LP basis factorization */ alpar@1: alpar@1: #define fhv_delete_it _glp_fhv_delete_it alpar@1: void fhv_delete_it(FHV *fhv); alpar@1: /* delete LP basis factorization */ alpar@1: alpar@1: #endif alpar@1: alpar@1: /* eof */