alpar@9: /* glpscf.h (Schur complement factorization) */ alpar@9: alpar@9: /*********************************************************************** alpar@9: * This code is part of GLPK (GNU Linear Programming Kit). alpar@9: * alpar@9: * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, alpar@9: * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, alpar@9: * Moscow Aviation Institute, Moscow, Russia. All rights reserved. alpar@9: * E-mail: . alpar@9: * alpar@9: * GLPK is free software: you can redistribute it and/or modify it alpar@9: * under the terms of the GNU General Public License as published by alpar@9: * the Free Software Foundation, either version 3 of the License, or alpar@9: * (at your option) any later version. alpar@9: * alpar@9: * GLPK is distributed in the hope that it will be useful, but WITHOUT alpar@9: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY alpar@9: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public alpar@9: * License for more details. alpar@9: * alpar@9: * You should have received a copy of the GNU General Public License alpar@9: * along with GLPK. If not, see . alpar@9: ***********************************************************************/ alpar@9: alpar@9: #ifndef GLPSCF_H alpar@9: #define GLPSCF_H alpar@9: alpar@9: /*********************************************************************** alpar@9: * The structure SCF defines the following factorization of a square alpar@9: * nxn matrix C (which is the Schur complement): alpar@9: * alpar@9: * F * C = U * P, alpar@9: * alpar@9: * where F is a square transforming matrix, U is an upper triangular alpar@9: * matrix, P is a permutation matrix. alpar@9: * alpar@9: * It is assumed that matrix C is small and dense, so matrices F and U alpar@9: * are stored in the dense format by rows as follows: alpar@9: * alpar@9: * 1 n n_max 1 n n_max alpar@9: * 1 * * * * * * x x x x 1 * * * * * * x x x x alpar@9: * * * * * * * x x x x . * * * * * x x x x alpar@9: * * * * * * * x x x x . . * * * * x x x x alpar@9: * * * * * * * x x x x . . . * * * x x x x alpar@9: * * * * * * * x x x x . . . . * * x x x x alpar@9: * n * * * * * * x x x x n . . . . . * x x x x alpar@9: * x x x x x x x x x x . . . . . . x x x x alpar@9: * x x x x x x x x x x . . . . . . . x x x alpar@9: * x x x x x x x x x x . . . . . . . . x x alpar@9: * n_max x x x x x x x x x x n_max . . . . . . . . . x alpar@9: * alpar@9: * matrix F matrix U alpar@9: * alpar@9: * where '*' are matrix elements, 'x' are reserved locations. alpar@9: * alpar@9: * Permutation matrix P is stored in row-like format. alpar@9: * alpar@9: * Matrix C normally is not stored. alpar@9: * alpar@9: * REFERENCES alpar@9: * alpar@9: * 1. M.A.Saunders, "LUSOL: A basis package for constrained optimiza- alpar@9: * tion," SCCM, Stanford University, 2006. alpar@9: * alpar@9: * 2. M.A.Saunders, "Notes 5: Basis Updates," CME 318, Stanford Univer- alpar@9: * sity, Spring 2006. alpar@9: * alpar@9: * 3. M.A.Saunders, "Notes 6: LUSOL---a Basis Factorization Package," alpar@9: * ibid. */ alpar@9: alpar@9: typedef struct SCF SCF; alpar@9: alpar@9: struct SCF alpar@9: { /* Schur complement factorization */ alpar@9: int n_max; alpar@9: /* maximal order of matrices C, F, U, P; n_max >= 1 */ alpar@9: int n; alpar@9: /* current order of matrices C, F, U, P; n >= 0 */ alpar@9: double *f; /* double f[1+n_max*n_max]; */ alpar@9: /* matrix F stored by rows */ alpar@9: double *u; /* double u[1+n_max*(n_max+1)/2]; */ alpar@9: /* upper triangle of matrix U stored by rows */ alpar@9: int *p; /* int p[1+n_max]; */ alpar@9: /* matrix P; p[i] = j means that P[i,j] = 1 */ alpar@9: int t_opt; alpar@9: /* type of transformation used to restore triangular structure of alpar@9: matrix U: */ alpar@9: #define SCF_TBG 1 /* Bartels-Golub elimination */ alpar@9: #define SCF_TGR 2 /* Givens plane rotation */ alpar@9: int rank; alpar@9: /* estimated rank of matrices C and U */ alpar@9: double *c; /* double c[1+n_max*n_max]; */ alpar@9: /* matrix C stored in the same format as matrix F and used only alpar@9: for debugging; normally this array is not allocated */ alpar@9: double *w; /* double w[1+n_max]; */ alpar@9: /* working array */ alpar@9: }; alpar@9: alpar@9: /* return codes: */ alpar@9: #define SCF_ESING 1 /* singular matrix */ alpar@9: #define SCF_ELIMIT 2 /* update limit reached */ alpar@9: alpar@9: #define scf_create_it _glp_scf_create_it alpar@9: SCF *scf_create_it(int n_max); alpar@9: /* create Schur complement factorization */ alpar@9: alpar@9: #define scf_update_exp _glp_scf_update_exp alpar@9: int scf_update_exp(SCF *scf, const double x[], const double y[], alpar@9: double z); alpar@9: /* update factorization on expanding C */ alpar@9: alpar@9: #define scf_solve_it _glp_scf_solve_it alpar@9: void scf_solve_it(SCF *scf, int tr, double x[]); alpar@9: /* solve either system C * x = b or C' * x = b */ alpar@9: alpar@9: #define scf_reset_it _glp_scf_reset_it alpar@9: void scf_reset_it(SCF *scf); alpar@9: /* reset factorization for empty matrix C */ alpar@9: alpar@9: #define scf_delete_it _glp_scf_delete_it alpar@9: void scf_delete_it(SCF *scf); alpar@9: /* delete Schur complement factorization */ alpar@9: alpar@9: #endif alpar@9: alpar@9: /* eof */