lemon-project-template-glpk
view deps/glpk/src/glpscf.h @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* glpscf.h (Schur complement factorization) */
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, 2011 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 ***********************************************************************/
25 #ifndef GLPSCF_H
26 #define GLPSCF_H
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. */
71 typedef struct SCF SCF;
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 };
99 /* return codes: */
100 #define SCF_ESING 1 /* singular matrix */
101 #define SCF_ELIMIT 2 /* update limit reached */
103 #define scf_create_it _glp_scf_create_it
104 SCF *scf_create_it(int n_max);
105 /* create Schur complement factorization */
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 */
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 */
116 #define scf_reset_it _glp_scf_reset_it
117 void scf_reset_it(SCF *scf);
118 /* reset factorization for empty matrix C */
120 #define scf_delete_it _glp_scf_delete_it
121 void scf_delete_it(SCF *scf);
122 /* delete Schur complement factorization */
124 #endif
126 /* eof */