1 | /* glpscf.h (Schur complement factorization) */ |
---|
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 GLPSCF_H |
---|
26 | #define GLPSCF_H |
---|
27 | |
---|
28 | /*********************************************************************** |
---|
29 | * The structure SCF defines the following factorization of a square |
---|
30 | * nxn matrix C (which is the Schur complement): |
---|
31 | * |
---|
32 | * F * C = U * P, |
---|
33 | * |
---|
34 | * where F is a square transforming matrix, U is an upper triangular |
---|
35 | * matrix, P is a permutation matrix. |
---|
36 | * |
---|
37 | * It is assumed that matrix C is small and dense, so matrices F and U |
---|
38 | * are stored in the dense format by rows as follows: |
---|
39 | * |
---|
40 | * 1 n n_max 1 n n_max |
---|
41 | * 1 * * * * * * x x x x 1 * * * * * * x x x x |
---|
42 | * * * * * * * x x x x . * * * * * x x x x |
---|
43 | * * * * * * * x x x x . . * * * * x x x x |
---|
44 | * * * * * * * x x x x . . . * * * x x x x |
---|
45 | * * * * * * * x x x x . . . . * * x x x x |
---|
46 | * n * * * * * * x x x x n . . . . . * x x x x |
---|
47 | * x x x x x x x x x x . . . . . . x x x x |
---|
48 | * x x x x x x x x x x . . . . . . . x x x |
---|
49 | * x x x x x x x x x x . . . . . . . . x x |
---|
50 | * n_max x x x x x x x x x x n_max . . . . . . . . . x |
---|
51 | * |
---|
52 | * matrix F matrix U |
---|
53 | * |
---|
54 | * where '*' are matrix elements, 'x' are reserved locations. |
---|
55 | * |
---|
56 | * Permutation matrix P is stored in row-like format. |
---|
57 | * |
---|
58 | * Matrix C normally is not stored. |
---|
59 | * |
---|
60 | * REFERENCES |
---|
61 | * |
---|
62 | * 1. M.A.Saunders, "LUSOL: A basis package for constrained optimiza- |
---|
63 | * tion," SCCM, Stanford University, 2006. |
---|
64 | * |
---|
65 | * 2. M.A.Saunders, "Notes 5: Basis Updates," CME 318, Stanford Univer- |
---|
66 | * sity, Spring 2006. |
---|
67 | * |
---|
68 | * 3. M.A.Saunders, "Notes 6: LUSOL---a Basis Factorization Package," |
---|
69 | * ibid. */ |
---|
70 | |
---|
71 | typedef struct SCF SCF; |
---|
72 | |
---|
73 | struct SCF |
---|
74 | { /* Schur complement factorization */ |
---|
75 | int n_max; |
---|
76 | /* maximal order of matrices C, F, U, P; n_max >= 1 */ |
---|
77 | int n; |
---|
78 | /* current order of matrices C, F, U, P; n >= 0 */ |
---|
79 | double *f; /* double f[1+n_max*n_max]; */ |
---|
80 | /* matrix F stored by rows */ |
---|
81 | double *u; /* double u[1+n_max*(n_max+1)/2]; */ |
---|
82 | /* upper triangle of matrix U stored by rows */ |
---|
83 | int *p; /* int p[1+n_max]; */ |
---|
84 | /* matrix P; p[i] = j means that P[i,j] = 1 */ |
---|
85 | int t_opt; |
---|
86 | /* type of transformation used to restore triangular structure of |
---|
87 | matrix U: */ |
---|
88 | #define SCF_TBG 1 /* Bartels-Golub elimination */ |
---|
89 | #define SCF_TGR 2 /* Givens plane rotation */ |
---|
90 | int rank; |
---|
91 | /* estimated rank of matrices C and U */ |
---|
92 | double *c; /* double c[1+n_max*n_max]; */ |
---|
93 | /* matrix C stored in the same format as matrix F and used only |
---|
94 | for debugging; normally this array is not allocated */ |
---|
95 | double *w; /* double w[1+n_max]; */ |
---|
96 | /* working array */ |
---|
97 | }; |
---|
98 | |
---|
99 | /* return codes: */ |
---|
100 | #define SCF_ESING 1 /* singular matrix */ |
---|
101 | #define SCF_ELIMIT 2 /* update limit reached */ |
---|
102 | |
---|
103 | #define scf_create_it _glp_scf_create_it |
---|
104 | SCF *scf_create_it(int n_max); |
---|
105 | /* create Schur complement factorization */ |
---|
106 | |
---|
107 | #define scf_update_exp _glp_scf_update_exp |
---|
108 | int scf_update_exp(SCF *scf, const double x[], const double y[], |
---|
109 | double z); |
---|
110 | /* update factorization on expanding C */ |
---|
111 | |
---|
112 | #define scf_solve_it _glp_scf_solve_it |
---|
113 | void scf_solve_it(SCF *scf, int tr, double x[]); |
---|
114 | /* solve either system C * x = b or C' * x = b */ |
---|
115 | |
---|
116 | #define scf_reset_it _glp_scf_reset_it |
---|
117 | void scf_reset_it(SCF *scf); |
---|
118 | /* reset factorization for empty matrix C */ |
---|
119 | |
---|
120 | #define scf_delete_it _glp_scf_delete_it |
---|
121 | void scf_delete_it(SCF *scf); |
---|
122 | /* delete Schur complement factorization */ |
---|
123 | |
---|
124 | #endif |
---|
125 | |
---|
126 | /* eof */ |
---|