Loading...
Searching...
No Matches
glpinv.h
Go to the documentation of this file.
/* glpinv.h */
/*----------------------------------------------------------------------
-- Copyright (C) 2000, 2001, 2002, 2003 Andrew Makhorin, Department
-- for Applied Informatics, Moscow Aviation Institute, Moscow, Russia.
-- All rights reserved. E-mail: <mao@mai2.rcnet.ru>.
--
-- This file is a part of GLPK (GNU Linear Programming Kit).
--
-- Licensed under the Eclipse Public License (EPL) by permission of the
-- author for inclusion in the DyLP LP distribution.
----------------------------------------------------------------------*/
/*
@(#)glpinv.h 1.3 06/22/04
svn/cvs: $Id: glpinv.h 407 2010-12-31 20:48:48Z lou $
*/
#ifndef _GLPINV_H
#define _GLPINV_H
#include "glpluf.h"
#define inv_create dy_glp_inv_create
#define inv_decomp dy_glp_inv_decomp
#define inv_h_solve dy_glp_inv_h_solve
#define inv_ftran dy_glp_inv_ftran
#define inv_btran dy_glp_inv_btran
#define inv_update dy_glp_inv_update
#define inv_delete dy_glp_inv_delete
/*----------------------------------------------------------------------
-- The structure INV defines an invertable form of the basis matrix B,
-- which is based on LU-factorization and 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
-- section GLPLUF), which is a member of the structure INV.
--
-- 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 INV INV;
struct INV
{ /* invertable (factorized) form of the basis matrix */
int m;
/* order of the matrices B, F, H, V, P0, P, Q */
int valid;
/* if this flag is not set, the invertable form is invalid and
can't be updated nor used in ftran and btran operations */
LUF *luf;
/* LU-factorization (holds the matrices F, V, P, Q) */
/*--------------------------------------------------------------*/
/* matrix H in the form of eta file */
int hh_max;
/* maximal number of row-like factors (that limits maximal number
of updates of the factorization) */
int hh_nfs;
/* current number of row-like factors (0 <= hh_nfs <= hh_max) */
int *hh_ndx; /* int hh_ndx[1+hh_max]; */
/* hh_ndx[0] is not used;
hh_ndx[k], k = 1, ..., nfs, is number of a non-trivial row of
the factor H[k] */
int *hh_ptr; /* int hh_ptr[1+hh_max]; */
/* hh_ptr[0] is not used;
hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element
of the non-trivial row of the factor H[k] in the sparse vector
area */
int *hh_len; /* int hh_len[1+hh_max]; */
/* hh_len[0] is not used;
hh_len[k], k = 1, ..., nfs, is total number of elements in the
non-trivial row of the factor H[k] */
/*--------------------------------------------------------------*/
/* matrix P0 */
int *p0_row; /* int p0_row[1+n]; */
/* p0_row[0] is not used; p0_row[i] = j means that p0[i,j] = 1 */
int *p0_col; /* int p0_col[1+n]; */
/* p0_col[0] is not used; 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' */
/*--------------------------------------------------------------*/
/* partially transformed column is inv(F*H)*B[j], where B[j] is a
new column, which will replace the existing j-th column of the
basis matrix */
int cc_len;
/* number of (non-zero) elements in the partially transformed
column; if cc_len < 0, the column has been not prepared yet */
int *cc_ndx; /* int cc_ndx[1+m]; */
/* cc_ndx[0] is not used;
cc_ndx[k], k = 1, ..., cc_len, is a row index of the partially
transformed column element */
double *cc_val; /* double cc_val[1+m]; */
/* cc_val[0] is not used;
cc_val[k], k = 1, ..., cc_len, is a numerical (non-zero) value
of the column element */
/*--------------------------------------------------------------*/
/* control parameters */
double upd_tol;
#if 0
/* update tolerance; if on updating the factorization absolute
value of some diagonal element of the matrix U = P*V*Q is less
than upd_tol, the factorization is considered as inaccurate */
#else
/* update tolerance; if after the factorization has been updated
absolute value of some diagonal element u[k,k] of the matrix
U = P*V*Q is less than upd_tol * max(|u[k,*]|, |u[*,k]|), the
factorization is considered as inaccurate */
#endif
/*--------------------------------------------------------------*/
/* some statistics */
int nnz_h;
/* current number of non-zeros in all factors of the matrix H */
double min_vrratio ;
/* minimum value of u[k,k]/(upd_tol)*max(|u[k,*]|, |u[*,k]|) since
last pivot. */
};
INV *inv_create(int m, int max_upd);
/* create factorization of the basis matrix */
int inv_decomp(INV *inv,
void *info, int (*col)(void *info, int j, int rn[], double bj[]));
/* compute factorization of the basis matrix */
void inv_h_solve(INV *inv, int tr, double x[]);
/* solve system H*x = b or H'*x = b */
void inv_ftran(INV *inv, double x[], int save);
/* perform forward transformation (FTRAN) */
void inv_btran(INV *inv, double x[]);
/* perform backward transformation (BTRAN) */
int inv_update(INV *inv, int j);
/* update factorization for adjacent basis matrix */
void inv_delete(INV *inv);
/* delete factorization of the basis matrix */
#endif
/* eof */
inv_delete
#define inv_delete
Definition glpinv.h:31
inv_decomp
#define inv_decomp
Definition glpinv.h:26
inv_create
#define inv_create
Definition glpinv.h:25
inv_btran
#define inv_btran
Definition glpinv.h:29
inv_h_solve
#define inv_h_solve
Definition glpinv.h:27
inv_ftran
#define inv_ftran
Definition glpinv.h:28
inv_update
#define inv_update
Definition glpinv.h:30
glpluf.h
INV
Definition glpinv.h:79
INV::cc_val
double * cc_val
Definition glpinv.h:127
INV::cc_ndx
int * cc_ndx
Definition glpinv.h:123
INV::hh_ndx
int * hh_ndx
Definition glpinv.h:94
INV::hh_ptr
int * hh_ptr
Definition glpinv.h:98
INV::nnz_h
int nnz_h
Definition glpinv.h:146
INV::hh_nfs
int hh_nfs
Definition glpinv.h:92
INV::hh_max
int hh_max
Definition glpinv.h:89
INV::min_vrratio
double min_vrratio
Definition glpinv.h:148
INV::p0_row
int * p0_row
Definition glpinv.h:109
INV::cc_len
int cc_len
Definition glpinv.h:120
INV::valid
int valid
Definition glpinv.h:82
INV::luf
LUF * luf
Definition glpinv.h:85
INV::m
int m
Definition glpinv.h:80
INV::upd_tol
double upd_tol
Definition glpinv.h:133
INV::p0_col
int * p0_col
Definition glpinv.h:111
INV::hh_len
int * hh_len
Definition glpinv.h:103
LUF
Definition glpluf.h:84