lemon-project-template-glpk

annotate deps/glpk/src/glpscf.h @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpscf.h (Schur complement factorization) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #ifndef GLPSCF_H
alpar@9 26 #define GLPSCF_H
alpar@9 27
alpar@9 28 /***********************************************************************
alpar@9 29 * The structure SCF defines the following factorization of a square
alpar@9 30 * nxn matrix C (which is the Schur complement):
alpar@9 31 *
alpar@9 32 * F * C = U * P,
alpar@9 33 *
alpar@9 34 * where F is a square transforming matrix, U is an upper triangular
alpar@9 35 * matrix, P is a permutation matrix.
alpar@9 36 *
alpar@9 37 * It is assumed that matrix C is small and dense, so matrices F and U
alpar@9 38 * are stored in the dense format by rows as follows:
alpar@9 39 *
alpar@9 40 * 1 n n_max 1 n n_max
alpar@9 41 * 1 * * * * * * x x x x 1 * * * * * * x x x x
alpar@9 42 * * * * * * * x x x x . * * * * * x x x x
alpar@9 43 * * * * * * * x x x x . . * * * * x x x x
alpar@9 44 * * * * * * * x x x x . . . * * * x x x x
alpar@9 45 * * * * * * * x x x x . . . . * * x x x x
alpar@9 46 * n * * * * * * x x x x n . . . . . * x x x x
alpar@9 47 * x x x x x x x x x x . . . . . . x x x x
alpar@9 48 * x x x x x x x x x x . . . . . . . x x x
alpar@9 49 * x x x x x x x x x x . . . . . . . . x x
alpar@9 50 * n_max x x x x x x x x x x n_max . . . . . . . . . x
alpar@9 51 *
alpar@9 52 * matrix F matrix U
alpar@9 53 *
alpar@9 54 * where '*' are matrix elements, 'x' are reserved locations.
alpar@9 55 *
alpar@9 56 * Permutation matrix P is stored in row-like format.
alpar@9 57 *
alpar@9 58 * Matrix C normally is not stored.
alpar@9 59 *
alpar@9 60 * REFERENCES
alpar@9 61 *
alpar@9 62 * 1. M.A.Saunders, "LUSOL: A basis package for constrained optimiza-
alpar@9 63 * tion," SCCM, Stanford University, 2006.
alpar@9 64 *
alpar@9 65 * 2. M.A.Saunders, "Notes 5: Basis Updates," CME 318, Stanford Univer-
alpar@9 66 * sity, Spring 2006.
alpar@9 67 *
alpar@9 68 * 3. M.A.Saunders, "Notes 6: LUSOL---a Basis Factorization Package,"
alpar@9 69 * ibid. */
alpar@9 70
alpar@9 71 typedef struct SCF SCF;
alpar@9 72
alpar@9 73 struct SCF
alpar@9 74 { /* Schur complement factorization */
alpar@9 75 int n_max;
alpar@9 76 /* maximal order of matrices C, F, U, P; n_max >= 1 */
alpar@9 77 int n;
alpar@9 78 /* current order of matrices C, F, U, P; n >= 0 */
alpar@9 79 double *f; /* double f[1+n_max*n_max]; */
alpar@9 80 /* matrix F stored by rows */
alpar@9 81 double *u; /* double u[1+n_max*(n_max+1)/2]; */
alpar@9 82 /* upper triangle of matrix U stored by rows */
alpar@9 83 int *p; /* int p[1+n_max]; */
alpar@9 84 /* matrix P; p[i] = j means that P[i,j] = 1 */
alpar@9 85 int t_opt;
alpar@9 86 /* type of transformation used to restore triangular structure of
alpar@9 87 matrix U: */
alpar@9 88 #define SCF_TBG 1 /* Bartels-Golub elimination */
alpar@9 89 #define SCF_TGR 2 /* Givens plane rotation */
alpar@9 90 int rank;
alpar@9 91 /* estimated rank of matrices C and U */
alpar@9 92 double *c; /* double c[1+n_max*n_max]; */
alpar@9 93 /* matrix C stored in the same format as matrix F and used only
alpar@9 94 for debugging; normally this array is not allocated */
alpar@9 95 double *w; /* double w[1+n_max]; */
alpar@9 96 /* working array */
alpar@9 97 };
alpar@9 98
alpar@9 99 /* return codes: */
alpar@9 100 #define SCF_ESING 1 /* singular matrix */
alpar@9 101 #define SCF_ELIMIT 2 /* update limit reached */
alpar@9 102
alpar@9 103 #define scf_create_it _glp_scf_create_it
alpar@9 104 SCF *scf_create_it(int n_max);
alpar@9 105 /* create Schur complement factorization */
alpar@9 106
alpar@9 107 #define scf_update_exp _glp_scf_update_exp
alpar@9 108 int scf_update_exp(SCF *scf, const double x[], const double y[],
alpar@9 109 double z);
alpar@9 110 /* update factorization on expanding C */
alpar@9 111
alpar@9 112 #define scf_solve_it _glp_scf_solve_it
alpar@9 113 void scf_solve_it(SCF *scf, int tr, double x[]);
alpar@9 114 /* solve either system C * x = b or C' * x = b */
alpar@9 115
alpar@9 116 #define scf_reset_it _glp_scf_reset_it
alpar@9 117 void scf_reset_it(SCF *scf);
alpar@9 118 /* reset factorization for empty matrix C */
alpar@9 119
alpar@9 120 #define scf_delete_it _glp_scf_delete_it
alpar@9 121 void scf_delete_it(SCF *scf);
alpar@9 122 /* delete Schur complement factorization */
alpar@9 123
alpar@9 124 #endif
alpar@9 125
alpar@9 126 /* eof */