DyLP 1.10.4
Loading...
Searching...
No Matches
glpinv.h
Go to the documentation of this file.
1/* glpinv.h */
2
3/*----------------------------------------------------------------------
4-- Copyright (C) 2000, 2001, 2002, 2003 Andrew Makhorin, Department
5-- for Applied Informatics, Moscow Aviation Institute, Moscow, Russia.
6-- All rights reserved. E-mail: <mao@mai2.rcnet.ru>.
7--
8-- This file is a part of GLPK (GNU Linear Programming Kit).
9--
10-- Licensed under the Eclipse Public License (EPL) by permission of the
11-- author for inclusion in the DyLP LP distribution.
12----------------------------------------------------------------------*/
13
14/*
15 @(#)glpinv.h 1.3 06/22/04
16 svn/cvs: $Id: glpinv.h 407 2010-12-31 20:48:48Z lou $
17*/
18
19
20#ifndef _GLPINV_H
21#define _GLPINV_H
22
23#include "glpluf.h"
24
25#define inv_create dy_glp_inv_create
26#define inv_decomp dy_glp_inv_decomp
27#define inv_h_solve dy_glp_inv_h_solve
28#define inv_ftran dy_glp_inv_ftran
29#define inv_btran dy_glp_inv_btran
30#define inv_update dy_glp_inv_update
31#define inv_delete dy_glp_inv_delete
32
33/*----------------------------------------------------------------------
34-- The structure INV defines an invertable form of the basis matrix B,
35-- which is based on LU-factorization and is the following sextet:
36--
37-- [B] = (F, H, V, P0, P, Q), (1)
38--
39-- where F, H, and V are such matrices that
40--
41-- B = F * H * V, (2)
42--
43-- and P0, P, and Q are such permutation matrices that the matrix
44--
45-- L = P0 * F * inv(P0) (3)
46--
47-- is lower triangular with unity diagonal, and the matrix
48--
49-- U = P * V * Q (4)
50--
51-- is upper triangular. All the matrices have the same order m, which
52-- is the order of the basis matrix B.
53--
54-- The matrices F, V, P, and Q are stored in the structure LUF (see the
55-- section GLPLUF), which is a member of the structure INV.
56--
57-- The matrix H is stored in the form of eta file using row-like format
58-- as follows:
59--
60-- H = H[1] * H[2] * ... * H[nfs], (5)
61--
62-- where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs
63-- from the unity matrix only by one row, nfs is current number of row-
64-- like factors. After the factorization has been built for some given
65-- basis matrix B the matrix H has no factors and thus it is the unity
66-- matrix. Then each time when the factorization is recomputed for an
67-- adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built
68-- and added to the end of the eta file H.
69--
70-- Being sparse vectors non-trivial rows of the factors H[k] are stored
71-- in the right part of the sparse vector area (SVA) in the same manner
72-- as rows and columns of the matrix F.
73--
74-- For more details see the program documentation. */
75
76typedef struct INV INV;
77
78struct INV
79{ /* invertable (factorized) form of the basis matrix */
80 int m;
81 /* order of the matrices B, F, H, V, P0, P, Q */
82 int valid;
83 /* if this flag is not set, the invertable form is invalid and
84 can't be updated nor used in ftran and btran operations */
86 /* LU-factorization (holds the matrices F, V, P, Q) */
87 /*--------------------------------------------------------------*/
88 /* matrix H in the form of eta file */
89 int hh_max;
90 /* maximal number of row-like factors (that limits maximal number
91 of updates of the factorization) */
92 int hh_nfs;
93 /* current number of row-like factors (0 <= hh_nfs <= hh_max) */
94 int *hh_ndx; /* int hh_ndx[1+hh_max]; */
95 /* hh_ndx[0] is not used;
96 hh_ndx[k], k = 1, ..., nfs, is number of a non-trivial row of
97 the factor H[k] */
98 int *hh_ptr; /* int hh_ptr[1+hh_max]; */
99 /* hh_ptr[0] is not used;
100 hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element
101 of the non-trivial row of the factor H[k] in the sparse vector
102 area */
103 int *hh_len; /* int hh_len[1+hh_max]; */
104 /* hh_len[0] is not used;
105 hh_len[k], k = 1, ..., nfs, is total number of elements in the
106 non-trivial row of the factor H[k] */
107 /*--------------------------------------------------------------*/
108 /* matrix P0 */
109 int *p0_row; /* int p0_row[1+n]; */
110 /* p0_row[0] is not used; p0_row[i] = j means that p0[i,j] = 1 */
111 int *p0_col; /* int p0_col[1+n]; */
112 /* p0_col[0] is not used; p0_col[j] = i means that p0[i,j] = 1 */
113 /* if i-th row or column of the matrix F corresponds to i'-th row
114 or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i
115 and p0_col[i] = i' */
116 /*--------------------------------------------------------------*/
117 /* partially transformed column is inv(F*H)*B[j], where B[j] is a
118 new column, which will replace the existing j-th column of the
119 basis matrix */
121 /* number of (non-zero) elements in the partially transformed
122 column; if cc_len < 0, the column has been not prepared yet */
123 int *cc_ndx; /* int cc_ndx[1+m]; */
124 /* cc_ndx[0] is not used;
125 cc_ndx[k], k = 1, ..., cc_len, is a row index of the partially
126 transformed column element */
127 double *cc_val; /* double cc_val[1+m]; */
128 /* cc_val[0] is not used;
129 cc_val[k], k = 1, ..., cc_len, is a numerical (non-zero) value
130 of the column element */
131 /*--------------------------------------------------------------*/
132 /* control parameters */
133 double upd_tol;
134#if 0
135 /* update tolerance; if on updating the factorization absolute
136 value of some diagonal element of the matrix U = P*V*Q is less
137 than upd_tol, the factorization is considered as inaccurate */
138#else
139 /* update tolerance; if after the factorization has been updated
140 absolute value of some diagonal element u[k,k] of the matrix
141 U = P*V*Q is less than upd_tol * max(|u[k,*]|, |u[*,k]|), the
142 factorization is considered as inaccurate */
143#endif
144 /*--------------------------------------------------------------*/
145 /* some statistics */
146 int nnz_h;
147 /* current number of non-zeros in all factors of the matrix H */
148 double min_vrratio ;
149 /* minimum value of u[k,k]/(upd_tol)*max(|u[k,*]|, |u[*,k]|) since
150 last pivot. */
151};
152
153INV *inv_create(int m, int max_upd);
154/* create factorization of the basis matrix */
155
157 void *info, int (*col)(void *info, int j, int rn[], double bj[]));
158/* compute factorization of the basis matrix */
159
160void inv_h_solve(INV *inv, int tr, double x[]);
161/* solve system H*x = b or H'*x = b */
162
163void inv_ftran(INV *inv, double x[], int save);
164/* perform forward transformation (FTRAN) */
165
166void inv_btran(INV *inv, double x[]);
167/* perform backward transformation (BTRAN) */
168
169int inv_update(INV *inv, int j);
170/* update factorization for adjacent basis matrix */
171
172void inv_delete(INV *inv);
173/* delete factorization of the basis matrix */
174
175#endif
176
177/* eof */
#define inv_delete
Definition glpinv.h:31
#define inv_decomp
Definition glpinv.h:26
#define inv_create
Definition glpinv.h:25
#define inv_btran
Definition glpinv.h:29
#define inv_h_solve
Definition glpinv.h:27
#define inv_ftran
Definition glpinv.h:28
#define inv_update
Definition glpinv.h:30
Definition glpinv.h:79
double * cc_val
Definition glpinv.h:127
int * cc_ndx
Definition glpinv.h:123
int * hh_ndx
Definition glpinv.h:94
int * hh_ptr
Definition glpinv.h:98
int nnz_h
Definition glpinv.h:146
int hh_nfs
Definition glpinv.h:92
int hh_max
Definition glpinv.h:89
double min_vrratio
Definition glpinv.h:148
int * p0_row
Definition glpinv.h:109
int cc_len
Definition glpinv.h:120
int valid
Definition glpinv.h:82
LUF * luf
Definition glpinv.h:85
int m
Definition glpinv.h:80
double upd_tol
Definition glpinv.h:133
int * p0_col
Definition glpinv.h:111
int * hh_len
Definition glpinv.h:103
Definition glpluf.h:84