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