|
1 /* glpfhv.h (LP basis factorization, FHV eta file version) */ |
|
2 |
|
3 /*********************************************************************** |
|
4 * This code is part of GLPK (GNU Linear Programming Kit). |
|
5 * |
|
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
|
7 * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
|
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
|
9 * E-mail: <mao@gnu.org>. |
|
10 * |
|
11 * GLPK is free software: you can redistribute it and/or modify it |
|
12 * under the terms of the GNU General Public License as published by |
|
13 * the Free Software Foundation, either version 3 of the License, or |
|
14 * (at your option) any later version. |
|
15 * |
|
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT |
|
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
|
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
|
19 * License for more details. |
|
20 * |
|
21 * You should have received a copy of the GNU General Public License |
|
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
|
23 ***********************************************************************/ |
|
24 |
|
25 #ifndef GLPFHV_H |
|
26 #define GLPFHV_H |
|
27 |
|
28 #include "glpluf.h" |
|
29 |
|
30 /*********************************************************************** |
|
31 * The structure FHV defines the factorization of the basis mxm-matrix |
|
32 * B, where m is the number of rows in corresponding problem instance. |
|
33 * |
|
34 * This factorization is the following sextet: |
|
35 * |
|
36 * [B] = (F, H, V, P0, P, Q), (1) |
|
37 * |
|
38 * where F, H, and V are such matrices that |
|
39 * |
|
40 * B = F * H * V, (2) |
|
41 * |
|
42 * and P0, P, and Q are such permutation matrices that the matrix |
|
43 * |
|
44 * L = P0 * F * inv(P0) (3) |
|
45 * |
|
46 * is lower triangular with unity diagonal, and the matrix |
|
47 * |
|
48 * U = P * V * Q (4) |
|
49 * |
|
50 * is upper triangular. All the matrices have the same order m, which |
|
51 * is the order of the basis matrix B. |
|
52 * |
|
53 * The matrices F, V, P, and Q are stored in the structure LUF (see the |
|
54 * module GLPLUF), which is a member of the structure FHV. |
|
55 * |
|
56 * The matrix H is stored in the form of eta file using row-like format |
|
57 * as follows: |
|
58 * |
|
59 * H = H[1] * H[2] * ... * H[nfs], (5) |
|
60 * |
|
61 * where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs |
|
62 * from the unity matrix only by one row, nfs is current number of row- |
|
63 * like factors. After the factorization has been built for some given |
|
64 * basis matrix B the matrix H has no factors and thus it is the unity |
|
65 * matrix. Then each time when the factorization is recomputed for an |
|
66 * adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built |
|
67 * and added to the end of the eta file H. |
|
68 * |
|
69 * Being sparse vectors non-trivial rows of the factors H[k] are stored |
|
70 * in the right part of the sparse vector area (SVA) in the same manner |
|
71 * as rows and columns of the matrix F. |
|
72 * |
|
73 * For more details see the program documentation. */ |
|
74 |
|
75 typedef struct FHV FHV; |
|
76 |
|
77 struct FHV |
|
78 { /* LP basis factorization */ |
|
79 int m_max; |
|
80 /* maximal value of m (increased automatically, if necessary) */ |
|
81 int m; |
|
82 /* the order of matrices B, F, H, V, P0, P, Q */ |
|
83 int valid; |
|
84 /* the factorization is valid only if this flag is set */ |
|
85 LUF *luf; |
|
86 /* LU-factorization (contains 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 (which limits the number of |
|
91 updates of the factorization) */ |
|
92 int hh_nfs; |
|
93 /* current number of row-like factors (0 <= hh_nfs <= hh_max) */ |
|
94 int *hh_ind; /* int hh_ind[1+hh_max]; */ |
|
95 /* hh_ind[k], k = 1, ..., nfs, is the number of a non-trivial row |
|
96 of factor H[k] */ |
|
97 int *hh_ptr; /* int hh_ptr[1+hh_max]; */ |
|
98 /* hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element |
|
99 of the non-trivial row of factor H[k] in the SVA */ |
|
100 int *hh_len; /* int hh_len[1+hh_max]; */ |
|
101 /* hh_len[k], k = 1, ..., nfs, is the number of non-zero elements |
|
102 in the non-trivial row of factor H[k] */ |
|
103 /*--------------------------------------------------------------*/ |
|
104 /* matrix P0 */ |
|
105 int *p0_row; /* int p0_row[1+m_max]; */ |
|
106 /* p0_row[i] = j means that p0[i,j] = 1 */ |
|
107 int *p0_col; /* int p0_col[1+m_max]; */ |
|
108 /* p0_col[j] = i means that p0[i,j] = 1 */ |
|
109 /* if i-th row or column of the matrix F corresponds to i'-th row |
|
110 or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i |
|
111 and p0_col[i] = i' */ |
|
112 /*--------------------------------------------------------------*/ |
|
113 /* working arrays */ |
|
114 int *cc_ind; /* int cc_ind[1+m_max]; */ |
|
115 /* integer working array */ |
|
116 double *cc_val; /* double cc_val[1+m_max]; */ |
|
117 /* floating-point working array */ |
|
118 /*--------------------------------------------------------------*/ |
|
119 /* control parameters */ |
|
120 double upd_tol; |
|
121 /* update tolerance; if after updating the factorization absolute |
|
122 value of some diagonal element u[k,k] of matrix U = P*V*Q is |
|
123 less than upd_tol * max(|u[k,*]|, |u[*,k]|), the factorization |
|
124 is considered as inaccurate */ |
|
125 /*--------------------------------------------------------------*/ |
|
126 /* some statistics */ |
|
127 int nnz_h; |
|
128 /* current number of non-zeros in all factors of matrix H */ |
|
129 }; |
|
130 |
|
131 /* return codes: */ |
|
132 #define FHV_ESING 1 /* singular matrix */ |
|
133 #define FHV_ECOND 2 /* ill-conditioned matrix */ |
|
134 #define FHV_ECHECK 3 /* insufficient accuracy */ |
|
135 #define FHV_ELIMIT 4 /* update limit reached */ |
|
136 #define FHV_EROOM 5 /* SVA overflow */ |
|
137 |
|
138 #define fhv_create_it _glp_fhv_create_it |
|
139 FHV *fhv_create_it(void); |
|
140 /* create LP basis factorization */ |
|
141 |
|
142 #define fhv_factorize _glp_fhv_factorize |
|
143 int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j, |
|
144 int ind[], double val[]), void *info); |
|
145 /* compute LP basis factorization */ |
|
146 |
|
147 #define fhv_h_solve _glp_fhv_h_solve |
|
148 void fhv_h_solve(FHV *fhv, int tr, double x[]); |
|
149 /* solve system H*x = b or H'*x = b */ |
|
150 |
|
151 #define fhv_ftran _glp_fhv_ftran |
|
152 void fhv_ftran(FHV *fhv, double x[]); |
|
153 /* perform forward transformation (solve system B*x = b) */ |
|
154 |
|
155 #define fhv_btran _glp_fhv_btran |
|
156 void fhv_btran(FHV *fhv, double x[]); |
|
157 /* perform backward transformation (solve system B'*x = b) */ |
|
158 |
|
159 #define fhv_update_it _glp_fhv_update_it |
|
160 int fhv_update_it(FHV *fhv, int j, int len, const int ind[], |
|
161 const double val[]); |
|
162 /* update LP basis factorization */ |
|
163 |
|
164 #define fhv_delete_it _glp_fhv_delete_it |
|
165 void fhv_delete_it(FHV *fhv); |
|
166 /* delete LP basis factorization */ |
|
167 |
|
168 #endif |
|
169 |
|
170 /* eof */ |