alpar@9: /* glpfhv.c (LP basis factorization, FHV eta file version) */
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: <mao@gnu.org>.
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 <http://www.gnu.org/licenses/>.
alpar@9: ***********************************************************************/
alpar@9: 
alpar@9: #include "glpfhv.h"
alpar@9: #include "glpenv.h"
alpar@9: #define xfault xerror
alpar@9: 
alpar@9: /* CAUTION: DO NOT CHANGE THE LIMIT BELOW */
alpar@9: 
alpar@9: #define M_MAX 100000000 /* = 100*10^6 */
alpar@9: /* maximal order of the basis matrix */
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_create_it - create LP basis factorization
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  FHV *fhv_create_it(void);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_create_it creates a program object, which represents
alpar@9: *  a factorization of LP basis.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  The routine fhv_create_it returns a pointer to the object created. */
alpar@9: 
alpar@9: FHV *fhv_create_it(void)
alpar@9: {     FHV *fhv;
alpar@9:       fhv = xmalloc(sizeof(FHV));
alpar@9:       fhv->m_max = fhv->m = 0;
alpar@9:       fhv->valid = 0;
alpar@9:       fhv->luf = luf_create_it();
alpar@9:       fhv->hh_max = 50;
alpar@9:       fhv->hh_nfs = 0;
alpar@9:       fhv->hh_ind = fhv->hh_ptr = fhv->hh_len = NULL;
alpar@9:       fhv->p0_row = fhv->p0_col = NULL;
alpar@9:       fhv->cc_ind = NULL;
alpar@9:       fhv->cc_val = NULL;
alpar@9:       fhv->upd_tol = 1e-6;
alpar@9:       fhv->nnz_h = 0;
alpar@9:       return fhv;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_factorize - compute LP basis factorization
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j,
alpar@9: *     int ind[], double val[]), void *info);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_factorize computes the factorization of the basis
alpar@9: *  matrix B specified by the routine col.
alpar@9: *
alpar@9: *  The parameter fhv specified the basis factorization data structure
alpar@9: *  created by the routine fhv_create_it.
alpar@9: *
alpar@9: *  The parameter m specifies the order of B, m > 0.
alpar@9: *
alpar@9: *  The formal routine col specifies the matrix B to be factorized. To
alpar@9: *  obtain j-th column of A the routine fhv_factorize calls the routine
alpar@9: *  col with the parameter j (1 <= j <= n). In response the routine col
alpar@9: *  should store row indices and numerical values of non-zero elements
alpar@9: *  of j-th column of B to locations ind[1,...,len] and val[1,...,len],
alpar@9: *  respectively, where len is the number of non-zeros in j-th column
alpar@9: *  returned on exit. Neither zero nor duplicate elements are allowed.
alpar@9: *
alpar@9: *  The parameter info is a transit pointer passed to the routine col.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  0  The factorization has been successfully computed.
alpar@9: *
alpar@9: *  FHV_ESING
alpar@9: *     The specified matrix is singular within the working precision.
alpar@9: *
alpar@9: *  FHV_ECOND
alpar@9: *     The specified matrix is ill-conditioned.
alpar@9: *
alpar@9: *  For more details see comments to the routine luf_factorize.
alpar@9: *
alpar@9: *  ALGORITHM
alpar@9: *
alpar@9: *  The routine fhv_factorize calls the routine luf_factorize (see the
alpar@9: *  module GLPLUF), which actually computes LU-factorization of the basis
alpar@9: *  matrix B in the form
alpar@9: *
alpar@9: *     [B] = (F, V, P, Q),
alpar@9: *
alpar@9: *  where F and V are such matrices that
alpar@9: *
alpar@9: *     B = F * V,
alpar@9: *
alpar@9: *  and P and Q are such permutation matrices that the matrix
alpar@9: *
alpar@9: *     L = P * F * inv(P)
alpar@9: *
alpar@9: *  is lower triangular with unity diagonal, and the matrix
alpar@9: *
alpar@9: *     U = P * V * Q
alpar@9: *
alpar@9: *  is upper triangular.
alpar@9: *
alpar@9: *  In order to build the complete representation of the factorization
alpar@9: *  (see formula (1) in the file glpfhv.h) the routine fhv_factorize just
alpar@9: *  additionally sets H = I and P0 = P. */
alpar@9: 
alpar@9: int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j,
alpar@9:       int ind[], double val[]), void *info)
alpar@9: {     int ret;
alpar@9:       if (m < 1)
alpar@9:          xfault("fhv_factorize: m = %d; invalid parameter\n", m);
alpar@9:       if (m > M_MAX)
alpar@9:          xfault("fhv_factorize: m = %d; matrix too big\n", m);
alpar@9:       fhv->m = m;
alpar@9:       /* invalidate the factorization */
alpar@9:       fhv->valid = 0;
alpar@9:       /* allocate/reallocate arrays, if necessary */
alpar@9:       if (fhv->hh_ind == NULL)
alpar@9:          fhv->hh_ind = xcalloc(1+fhv->hh_max, sizeof(int));
alpar@9:       if (fhv->hh_ptr == NULL)
alpar@9:          fhv->hh_ptr = xcalloc(1+fhv->hh_max, sizeof(int));
alpar@9:       if (fhv->hh_len == NULL)
alpar@9:          fhv->hh_len = xcalloc(1+fhv->hh_max, sizeof(int));
alpar@9:       if (fhv->m_max < m)
alpar@9:       {  if (fhv->p0_row != NULL) xfree(fhv->p0_row);
alpar@9:          if (fhv->p0_col != NULL) xfree(fhv->p0_col);
alpar@9:          if (fhv->cc_ind != NULL) xfree(fhv->cc_ind);
alpar@9:          if (fhv->cc_val != NULL) xfree(fhv->cc_val);
alpar@9:          fhv->m_max = m + 100;
alpar@9:          fhv->p0_row = xcalloc(1+fhv->m_max, sizeof(int));
alpar@9:          fhv->p0_col = xcalloc(1+fhv->m_max, sizeof(int));
alpar@9:          fhv->cc_ind = xcalloc(1+fhv->m_max, sizeof(int));
alpar@9:          fhv->cc_val = xcalloc(1+fhv->m_max, sizeof(double));
alpar@9:       }
alpar@9:       /* try to factorize the basis matrix */
alpar@9:       switch (luf_factorize(fhv->luf, m, col, info))
alpar@9:       {  case 0:
alpar@9:             break;
alpar@9:          case LUF_ESING:
alpar@9:             ret = FHV_ESING;
alpar@9:             goto done;
alpar@9:          case LUF_ECOND:
alpar@9:             ret = FHV_ECOND;
alpar@9:             goto done;
alpar@9:          default:
alpar@9:             xassert(fhv != fhv);
alpar@9:       }
alpar@9:       /* the basis matrix has been successfully factorized */
alpar@9:       fhv->valid = 1;
alpar@9:       /* H := I */
alpar@9:       fhv->hh_nfs = 0;
alpar@9:       /* P0 := P */
alpar@9:       memcpy(&fhv->p0_row[1], &fhv->luf->pp_row[1], sizeof(int) * m);
alpar@9:       memcpy(&fhv->p0_col[1], &fhv->luf->pp_col[1], sizeof(int) * m);
alpar@9:       /* currently H has no factors */
alpar@9:       fhv->nnz_h = 0;
alpar@9:       ret = 0;
alpar@9: done: /* return to the calling program */
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_h_solve - solve system H*x = b or H'*x = b
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  void fhv_h_solve(FHV *fhv, int tr, double x[]);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_h_solve solves either the system H*x = b (if the
alpar@9: *  flag tr is zero) or the system H'*x = b (if the flag tr is non-zero),
alpar@9: *  where the matrix H is a component of the factorization specified by
alpar@9: *  the parameter fhv, H' is a matrix transposed to H.
alpar@9: *
alpar@9: *  On entry the array x should contain elements of the right-hand side
alpar@9: *  vector b in locations x[1], ..., x[m], where m is the order of the
alpar@9: *  matrix H. On exit this array will contain elements of the solution
alpar@9: *  vector x in the same locations. */
alpar@9: 
alpar@9: void fhv_h_solve(FHV *fhv, int tr, double x[])
alpar@9: {     int nfs = fhv->hh_nfs;
alpar@9:       int *hh_ind = fhv->hh_ind;
alpar@9:       int *hh_ptr = fhv->hh_ptr;
alpar@9:       int *hh_len = fhv->hh_len;
alpar@9:       int *sv_ind = fhv->luf->sv_ind;
alpar@9:       double *sv_val = fhv->luf->sv_val;
alpar@9:       int i, k, beg, end, ptr;
alpar@9:       double temp;
alpar@9:       if (!fhv->valid)
alpar@9:          xfault("fhv_h_solve: the factorization is not valid\n");
alpar@9:       if (!tr)
alpar@9:       {  /* solve the system H*x = b */
alpar@9:          for (k = 1; k <= nfs; k++)
alpar@9:          {  i = hh_ind[k];
alpar@9:             temp = x[i];
alpar@9:             beg = hh_ptr[k];
alpar@9:             end = beg + hh_len[k] - 1;
alpar@9:             for (ptr = beg; ptr <= end; ptr++)
alpar@9:                temp -= sv_val[ptr] * x[sv_ind[ptr]];
alpar@9:             x[i] = temp;
alpar@9:          }
alpar@9:       }
alpar@9:       else
alpar@9:       {  /* solve the system H'*x = b */
alpar@9:          for (k = nfs; k >= 1; k--)
alpar@9:          {  i = hh_ind[k];
alpar@9:             temp = x[i];
alpar@9:             if (temp == 0.0) continue;
alpar@9:             beg = hh_ptr[k];
alpar@9:             end = beg + hh_len[k] - 1;
alpar@9:             for (ptr = beg; ptr <= end; ptr++)
alpar@9:                x[sv_ind[ptr]] -= sv_val[ptr] * temp;
alpar@9:          }
alpar@9:       }
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_ftran - perform forward transformation (solve system B*x = b)
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  void fhv_ftran(FHV *fhv, double x[]);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_ftran performs forward transformation, i.e. solves
alpar@9: *  the system B*x = b, where B is the basis matrix, x is the vector of
alpar@9: *  unknowns to be computed, b is the vector of right-hand sides.
alpar@9: *
alpar@9: *  On entry elements of the vector b should be stored in dense format
alpar@9: *  in locations x[1], ..., x[m], where m is the number of rows. On exit
alpar@9: *  the routine stores elements of the vector x in the same locations. */
alpar@9: 
alpar@9: void fhv_ftran(FHV *fhv, double x[])
alpar@9: {     int *pp_row = fhv->luf->pp_row;
alpar@9:       int *pp_col = fhv->luf->pp_col;
alpar@9:       int *p0_row = fhv->p0_row;
alpar@9:       int *p0_col = fhv->p0_col;
alpar@9:       if (!fhv->valid)
alpar@9:          xfault("fhv_ftran: the factorization is not valid\n");
alpar@9:       /* B = F*H*V, therefore inv(B) = inv(V)*inv(H)*inv(F) */
alpar@9:       fhv->luf->pp_row = p0_row;
alpar@9:       fhv->luf->pp_col = p0_col;
alpar@9:       luf_f_solve(fhv->luf, 0, x);
alpar@9:       fhv->luf->pp_row = pp_row;
alpar@9:       fhv->luf->pp_col = pp_col;
alpar@9:       fhv_h_solve(fhv, 0, x);
alpar@9:       luf_v_solve(fhv->luf, 0, x);
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_btran - perform backward transformation (solve system B'*x = b)
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  void fhv_btran(FHV *fhv, double x[]);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_btran performs backward transformation, i.e. solves
alpar@9: *  the system B'*x = b, where B' is a matrix transposed to the basis
alpar@9: *  matrix B, x is the vector of unknowns to be computed, b is the vector
alpar@9: *  of right-hand sides.
alpar@9: *
alpar@9: *  On entry elements of the vector b should be stored in dense format
alpar@9: *  in locations x[1], ..., x[m], where m is the number of rows. On exit
alpar@9: *  the routine stores elements of the vector x in the same locations. */
alpar@9: 
alpar@9: void fhv_btran(FHV *fhv, double x[])
alpar@9: {     int *pp_row = fhv->luf->pp_row;
alpar@9:       int *pp_col = fhv->luf->pp_col;
alpar@9:       int *p0_row = fhv->p0_row;
alpar@9:       int *p0_col = fhv->p0_col;
alpar@9:       if (!fhv->valid)
alpar@9:          xfault("fhv_btran: the factorization is not valid\n");
alpar@9:       /* B = F*H*V, therefore inv(B') = inv(F')*inv(H')*inv(V') */
alpar@9:       luf_v_solve(fhv->luf, 1, x);
alpar@9:       fhv_h_solve(fhv, 1, x);
alpar@9:       fhv->luf->pp_row = p0_row;
alpar@9:       fhv->luf->pp_col = p0_col;
alpar@9:       luf_f_solve(fhv->luf, 1, x);
alpar@9:       fhv->luf->pp_row = pp_row;
alpar@9:       fhv->luf->pp_col = pp_col;
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_update_it - update LP basis factorization
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  int fhv_update_it(FHV *fhv, int j, int len, const int ind[],
alpar@9: *     const double val[]);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_update_it updates the factorization of the basis
alpar@9: *  matrix B after replacing its j-th column by a new vector.
alpar@9: *
alpar@9: *  The parameter j specifies the number of column of B, which has been
alpar@9: *  replaced, 1 <= j <= m, where m is the order of B.
alpar@9: *
alpar@9: *  Row indices and numerical values of non-zero elements of the new
alpar@9: *  column of B should be placed in locations ind[1], ..., ind[len] and
alpar@9: *  val[1], ..., val[len], resp., where len is the number of non-zeros
alpar@9: *  in the column. Neither zero nor duplicate elements are allowed.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  0  The factorization has been successfully updated.
alpar@9: *
alpar@9: *  FHV_ESING
alpar@9: *     The adjacent basis matrix is structurally singular, since after
alpar@9: *     changing j-th column of matrix V by the new column (see algorithm
alpar@9: *     below) the case k1 > k2 occured.
alpar@9: *
alpar@9: *  FHV_ECHECK
alpar@9: *     The factorization is inaccurate, since after transforming k2-th
alpar@9: *     row of matrix U = P*V*Q, its diagonal element u[k2,k2] is zero or
alpar@9: *     close to zero,
alpar@9: *
alpar@9: *  FHV_ELIMIT
alpar@9: *     Maximal number of H factors has been reached.
alpar@9: *
alpar@9: *  FHV_EROOM
alpar@9: *     Overflow of the sparse vector area.
alpar@9: *
alpar@9: *  In case of non-zero return code the factorization becomes invalid.
alpar@9: *  It should not be used until it has been recomputed with the routine
alpar@9: *  fhv_factorize.
alpar@9: *
alpar@9: *  ALGORITHM
alpar@9: *
alpar@9: *  The routine fhv_update_it is based on the transformation proposed by
alpar@9: *  Forrest and Tomlin.
alpar@9: *
alpar@9: *  Let j-th column of the basis matrix B have been replaced by new
alpar@9: *  column B[j]. In order to keep the equality B = F*H*V j-th column of
alpar@9: *  matrix V should be replaced by the column inv(F*H)*B[j].
alpar@9: *
alpar@9: *  From the standpoint of matrix U = P*V*Q, replacement of j-th column
alpar@9: *  of matrix V is equivalent to replacement of k1-th column of matrix U,
alpar@9: *  where k1 is determined by permutation matrix Q. Thus, matrix U loses
alpar@9: *  its upper triangular form and becomes the following:
alpar@9: *
alpar@9: *         1   k1       k2   m
alpar@9: *     1   x x * x x x x x x x
alpar@9: *         . x * x x x x x x x
alpar@9: *     k1  . . * x x x x x x x
alpar@9: *         . . * x x x x x x x
alpar@9: *         . . * . x x x x x x
alpar@9: *         . . * . . x x x x x
alpar@9: *         . . * . . . x x x x
alpar@9: *     k2  . . * . . . . x x x
alpar@9: *         . . . . . . . . x x
alpar@9: *     m   . . . . . . . . . x
alpar@9: *
alpar@9: *  where row index k2 corresponds to the lowest non-zero element of
alpar@9: *  k1-th column.
alpar@9: *
alpar@9: *  The routine moves rows and columns k1+1, k1+2, ..., k2 of matrix U
alpar@9: *  by one position to the left and upwards and moves k1-th row and k1-th
alpar@9: *  column to position k2. As the result of such symmetric permutations
alpar@9: *  matrix U becomes the following:
alpar@9: *
alpar@9: *         1   k1       k2   m
alpar@9: *     1   x x x x x x x * x x
alpar@9: *         . x x x x x x * x x
alpar@9: *     k1  . . x x x x x * x x
alpar@9: *         . . . x x x x * x x
alpar@9: *         . . . . x x x * x x
alpar@9: *         . . . . . x x * x x
alpar@9: *         . . . . . . x * x x
alpar@9: *     k2  . . x x x x x * x x
alpar@9: *         . . . . . . . . x x
alpar@9: *     m   . . . . . . . . . x
alpar@9: *
alpar@9: *  Then the routine performs gaussian elimination to eliminate elements
alpar@9: *  u[k2,k1], u[k2,k1+1], ..., u[k2,k2-1] using diagonal elements
alpar@9: *  u[k1,k1], u[k1+1,k1+1], ..., u[k2-1,k2-1] as pivots in the same way
alpar@9: *  as described in comments to the routine luf_factorize (see the module
alpar@9: *  GLPLUF). Note that actually all operations are performed on matrix V,
alpar@9: *  not on matrix U. During the elimination process the routine permutes
alpar@9: *  neither rows nor columns, so only k2-th row of matrix U is changed.
alpar@9: *
alpar@9: *  To keep the main equality B = F*H*V, each time when the routine
alpar@9: *  applies elementary gaussian transformation to the transformed row of
alpar@9: *  matrix V (which corresponds to k2-th row of matrix U), it also adds
alpar@9: *  a new element (gaussian multiplier) to the current row-like factor
alpar@9: *  of matrix H, which corresponds to the transformed row of matrix V. */
alpar@9: 
alpar@9: int fhv_update_it(FHV *fhv, int j, int len, const int ind[],
alpar@9:       const double val[])
alpar@9: {     int m = fhv->m;
alpar@9:       LUF *luf = fhv->luf;
alpar@9:       int *vr_ptr = luf->vr_ptr;
alpar@9:       int *vr_len = luf->vr_len;
alpar@9:       int *vr_cap = luf->vr_cap;
alpar@9:       double *vr_piv = luf->vr_piv;
alpar@9:       int *vc_ptr = luf->vc_ptr;
alpar@9:       int *vc_len = luf->vc_len;
alpar@9:       int *vc_cap = luf->vc_cap;
alpar@9:       int *pp_row = luf->pp_row;
alpar@9:       int *pp_col = luf->pp_col;
alpar@9:       int *qq_row = luf->qq_row;
alpar@9:       int *qq_col = luf->qq_col;
alpar@9:       int *sv_ind = luf->sv_ind;
alpar@9:       double *sv_val = luf->sv_val;
alpar@9:       double *work = luf->work;
alpar@9:       double eps_tol = luf->eps_tol;
alpar@9:       int *hh_ind = fhv->hh_ind;
alpar@9:       int *hh_ptr = fhv->hh_ptr;
alpar@9:       int *hh_len = fhv->hh_len;
alpar@9:       int *p0_row = fhv->p0_row;
alpar@9:       int *p0_col = fhv->p0_col;
alpar@9:       int *cc_ind = fhv->cc_ind;
alpar@9:       double *cc_val = fhv->cc_val;
alpar@9:       double upd_tol = fhv->upd_tol;
alpar@9:       int i, i_beg, i_end, i_ptr, j_beg, j_end, j_ptr, k, k1, k2, p, q,
alpar@9:          p_beg, p_end, p_ptr, ptr, ret;
alpar@9:       double f, temp;
alpar@9:       if (!fhv->valid)
alpar@9:          xfault("fhv_update_it: the factorization is not valid\n");
alpar@9:       if (!(1 <= j && j <= m))
alpar@9:          xfault("fhv_update_it: j = %d; column number out of range\n",
alpar@9:             j);
alpar@9:       /* check if the new factor of matrix H can be created */
alpar@9:       if (fhv->hh_nfs == fhv->hh_max)
alpar@9:       {  /* maximal number of updates has been reached */
alpar@9:          fhv->valid = 0;
alpar@9:          ret = FHV_ELIMIT;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       /* convert new j-th column of B to dense format */
alpar@9:       for (i = 1; i <= m; i++)
alpar@9:          cc_val[i] = 0.0;
alpar@9:       for (k = 1; k <= len; k++)
alpar@9:       {  i = ind[k];
alpar@9:          if (!(1 <= i && i <= m))
alpar@9:             xfault("fhv_update_it: ind[%d] = %d; row number out of rang"
alpar@9:                "e\n", k, i);
alpar@9:          if (cc_val[i] != 0.0)
alpar@9:             xfault("fhv_update_it: ind[%d] = %d; duplicate row index no"
alpar@9:                "t allowed\n", k, i);
alpar@9:          if (val[k] == 0.0)
alpar@9:             xfault("fhv_update_it: val[%d] = %g; zero element not allow"
alpar@9:                "ed\n", k, val[k]);
alpar@9:          cc_val[i] = val[k];
alpar@9:       }
alpar@9:       /* new j-th column of V := inv(F * H) * (new B[j]) */
alpar@9:       fhv->luf->pp_row = p0_row;
alpar@9:       fhv->luf->pp_col = p0_col;
alpar@9:       luf_f_solve(fhv->luf, 0, cc_val);
alpar@9:       fhv->luf->pp_row = pp_row;
alpar@9:       fhv->luf->pp_col = pp_col;
alpar@9:       fhv_h_solve(fhv, 0, cc_val);
alpar@9:       /* convert new j-th column of V to sparse format */
alpar@9:       len = 0;
alpar@9:       for (i = 1; i <= m; i++)
alpar@9:       {  temp = cc_val[i];
alpar@9:          if (temp == 0.0 || fabs(temp) < eps_tol) continue;
alpar@9:          len++, cc_ind[len] = i, cc_val[len] = temp;
alpar@9:       }
alpar@9:       /* clear old content of j-th column of matrix V */
alpar@9:       j_beg = vc_ptr[j];
alpar@9:       j_end = j_beg + vc_len[j] - 1;
alpar@9:       for (j_ptr = j_beg; j_ptr <= j_end; j_ptr++)
alpar@9:       {  /* get row index of v[i,j] */
alpar@9:          i = sv_ind[j_ptr];
alpar@9:          /* find v[i,j] in the i-th row */
alpar@9:          i_beg = vr_ptr[i];
alpar@9:          i_end = i_beg + vr_len[i] - 1;
alpar@9:          for (i_ptr = i_beg; sv_ind[i_ptr] != j; i_ptr++) /* nop */;
alpar@9:          xassert(i_ptr <= i_end);
alpar@9:          /* remove v[i,j] from the i-th row */
alpar@9:          sv_ind[i_ptr] = sv_ind[i_end];
alpar@9:          sv_val[i_ptr] = sv_val[i_end];
alpar@9:          vr_len[i]--;
alpar@9:       }
alpar@9:       /* now j-th column of matrix V is empty */
alpar@9:       luf->nnz_v -= vc_len[j];
alpar@9:       vc_len[j] = 0;
alpar@9:       /* add new elements of j-th column of matrix V to corresponding
alpar@9:          row lists; determine indices k1 and k2 */
alpar@9:       k1 = qq_row[j], k2 = 0;
alpar@9:       for (ptr = 1; ptr <= len; ptr++)
alpar@9:       {  /* get row index of v[i,j] */
alpar@9:          i = cc_ind[ptr];
alpar@9:          /* at least one unused location is needed in i-th row */
alpar@9:          if (vr_len[i] + 1 > vr_cap[i])
alpar@9:          {  if (luf_enlarge_row(luf, i, vr_len[i] + 10))
alpar@9:             {  /* overflow of the sparse vector area */
alpar@9:                fhv->valid = 0;
alpar@9:                luf->new_sva = luf->sv_size + luf->sv_size;
alpar@9:                xassert(luf->new_sva > luf->sv_size);
alpar@9:                ret = FHV_EROOM;
alpar@9:                goto done;
alpar@9:             }
alpar@9:          }
alpar@9:          /* add v[i,j] to i-th row */
alpar@9:          i_ptr = vr_ptr[i] + vr_len[i];
alpar@9:          sv_ind[i_ptr] = j;
alpar@9:          sv_val[i_ptr] = cc_val[ptr];
alpar@9:          vr_len[i]++;
alpar@9:          /* adjust index k2 */
alpar@9:          if (k2 < pp_col[i]) k2 = pp_col[i];
alpar@9:       }
alpar@9:       /* capacity of j-th column (which is currently empty) should be
alpar@9:          not less than len locations */
alpar@9:       if (vc_cap[j] < len)
alpar@9:       {  if (luf_enlarge_col(luf, j, len))
alpar@9:          {  /* overflow of the sparse vector area */
alpar@9:             fhv->valid = 0;
alpar@9:             luf->new_sva = luf->sv_size + luf->sv_size;
alpar@9:             xassert(luf->new_sva > luf->sv_size);
alpar@9:             ret = FHV_EROOM;
alpar@9:             goto done;
alpar@9:          }
alpar@9:       }
alpar@9:       /* add new elements of matrix V to j-th column list */
alpar@9:       j_ptr = vc_ptr[j];
alpar@9:       memmove(&sv_ind[j_ptr], &cc_ind[1], len * sizeof(int));
alpar@9:       memmove(&sv_val[j_ptr], &cc_val[1], len * sizeof(double));
alpar@9:       vc_len[j] = len;
alpar@9:       luf->nnz_v += len;
alpar@9:       /* if k1 > k2, diagonal element u[k2,k2] of matrix U is zero and
alpar@9:          therefore the adjacent basis matrix is structurally singular */
alpar@9:       if (k1 > k2)
alpar@9:       {  fhv->valid = 0;
alpar@9:          ret = FHV_ESING;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       /* perform implicit symmetric permutations of rows and columns of
alpar@9:          matrix U */
alpar@9:       i = pp_row[k1], j = qq_col[k1];
alpar@9:       for (k = k1; k < k2; k++)
alpar@9:       {  pp_row[k] = pp_row[k+1], pp_col[pp_row[k]] = k;
alpar@9:          qq_col[k] = qq_col[k+1], qq_row[qq_col[k]] = k;
alpar@9:       }
alpar@9:       pp_row[k2] = i, pp_col[i] = k2;
alpar@9:       qq_col[k2] = j, qq_row[j] = k2;
alpar@9:       /* now i-th row of the matrix V is k2-th row of matrix U; since
alpar@9:          no pivoting is used, only this row will be transformed */
alpar@9:       /* copy elements of i-th row of matrix V to the working array and
alpar@9:          remove these elements from matrix V */
alpar@9:       for (j = 1; j <= m; j++) work[j] = 0.0;
alpar@9:       i_beg = vr_ptr[i];
alpar@9:       i_end = i_beg + vr_len[i] - 1;
alpar@9:       for (i_ptr = i_beg; i_ptr <= i_end; i_ptr++)
alpar@9:       {  /* get column index of v[i,j] */
alpar@9:          j = sv_ind[i_ptr];
alpar@9:          /* store v[i,j] to the working array */
alpar@9:          work[j] = sv_val[i_ptr];
alpar@9:          /* find v[i,j] in the j-th column */
alpar@9:          j_beg = vc_ptr[j];
alpar@9:          j_end = j_beg + vc_len[j] - 1;
alpar@9:          for (j_ptr = j_beg; sv_ind[j_ptr] != i; j_ptr++) /* nop */;
alpar@9:          xassert(j_ptr <= j_end);
alpar@9:          /* remove v[i,j] from the j-th column */
alpar@9:          sv_ind[j_ptr] = sv_ind[j_end];
alpar@9:          sv_val[j_ptr] = sv_val[j_end];
alpar@9:          vc_len[j]--;
alpar@9:       }
alpar@9:       /* now i-th row of matrix V is empty */
alpar@9:       luf->nnz_v -= vr_len[i];
alpar@9:       vr_len[i] = 0;
alpar@9:       /* create the next row-like factor of the matrix H; this factor
alpar@9:          corresponds to i-th (transformed) row */
alpar@9:       fhv->hh_nfs++;
alpar@9:       hh_ind[fhv->hh_nfs] = i;
alpar@9:       /* hh_ptr[] will be set later */
alpar@9:       hh_len[fhv->hh_nfs] = 0;
alpar@9:       /* up to (k2 - k1) free locations are needed to add new elements
alpar@9:          to the non-trivial row of the row-like factor */
alpar@9:       if (luf->sv_end - luf->sv_beg < k2 - k1)
alpar@9:       {  luf_defrag_sva(luf);
alpar@9:          if (luf->sv_end - luf->sv_beg < k2 - k1)
alpar@9:          {  /* overflow of the sparse vector area */
alpar@9:             fhv->valid = luf->valid = 0;
alpar@9:             luf->new_sva = luf->sv_size + luf->sv_size;
alpar@9:             xassert(luf->new_sva > luf->sv_size);
alpar@9:             ret = FHV_EROOM;
alpar@9:             goto done;
alpar@9:          }
alpar@9:       }
alpar@9:       /* eliminate subdiagonal elements of matrix U */
alpar@9:       for (k = k1; k < k2; k++)
alpar@9:       {  /* v[p,q] = u[k,k] */
alpar@9:          p = pp_row[k], q = qq_col[k];
alpar@9:          /* this is the crucial point, where even tiny non-zeros should
alpar@9:             not be dropped */
alpar@9:          if (work[q] == 0.0) continue;
alpar@9:          /* compute gaussian multiplier f = v[i,q] / v[p,q] */
alpar@9:          f = work[q] / vr_piv[p];
alpar@9:          /* perform gaussian transformation:
alpar@9:             (i-th row) := (i-th row) - f * (p-th row)
alpar@9:             in order to eliminate v[i,q] = u[k2,k] */
alpar@9:          p_beg = vr_ptr[p];
alpar@9:          p_end = p_beg + vr_len[p] - 1;
alpar@9:          for (p_ptr = p_beg; p_ptr <= p_end; p_ptr++)
alpar@9:             work[sv_ind[p_ptr]] -= f * sv_val[p_ptr];
alpar@9:          /* store new element (gaussian multiplier that corresponds to
alpar@9:             p-th row) in the current row-like factor */
alpar@9:          luf->sv_end--;
alpar@9:          sv_ind[luf->sv_end] = p;
alpar@9:          sv_val[luf->sv_end] = f;
alpar@9:          hh_len[fhv->hh_nfs]++;
alpar@9:       }
alpar@9:       /* set pointer to the current row-like factor of the matrix H
alpar@9:          (if no elements were added to this factor, it is unity matrix
alpar@9:          and therefore can be discarded) */
alpar@9:       if (hh_len[fhv->hh_nfs] == 0)
alpar@9:          fhv->hh_nfs--;
alpar@9:       else
alpar@9:       {  hh_ptr[fhv->hh_nfs] = luf->sv_end;
alpar@9:          fhv->nnz_h += hh_len[fhv->hh_nfs];
alpar@9:       }
alpar@9:       /* store new pivot which corresponds to u[k2,k2] */
alpar@9:       vr_piv[i] = work[qq_col[k2]];
alpar@9:       /* new elements of i-th row of matrix V (which are non-diagonal
alpar@9:          elements u[k2,k2+1], ..., u[k2,m] of matrix U = P*V*Q) now are
alpar@9:          contained in the working array; add them to matrix V */
alpar@9:       len = 0;
alpar@9:       for (k = k2+1; k <= m; k++)
alpar@9:       {  /* get column index and value of v[i,j] = u[k2,k] */
alpar@9:          j = qq_col[k];
alpar@9:          temp = work[j];
alpar@9:          /* if v[i,j] is close to zero, skip it */
alpar@9:          if (fabs(temp) < eps_tol) continue;
alpar@9:          /* at least one unused location is needed in j-th column */
alpar@9:          if (vc_len[j] + 1 > vc_cap[j])
alpar@9:          {  if (luf_enlarge_col(luf, j, vc_len[j] + 10))
alpar@9:             {  /* overflow of the sparse vector area */
alpar@9:                fhv->valid = 0;
alpar@9:                luf->new_sva = luf->sv_size + luf->sv_size;
alpar@9:                xassert(luf->new_sva > luf->sv_size);
alpar@9:                ret = FHV_EROOM;
alpar@9:                goto done;
alpar@9:             }
alpar@9:          }
alpar@9:          /* add v[i,j] to j-th column */
alpar@9:          j_ptr = vc_ptr[j] + vc_len[j];
alpar@9:          sv_ind[j_ptr] = i;
alpar@9:          sv_val[j_ptr] = temp;
alpar@9:          vc_len[j]++;
alpar@9:          /* also store v[i,j] to the auxiliary array */
alpar@9:          len++, cc_ind[len] = j, cc_val[len] = temp;
alpar@9:       }
alpar@9:       /* capacity of i-th row (which is currently empty) should be not
alpar@9:          less than len locations */
alpar@9:       if (vr_cap[i] < len)
alpar@9:       {  if (luf_enlarge_row(luf, i, len))
alpar@9:          {  /* overflow of the sparse vector area */
alpar@9:             fhv->valid = 0;
alpar@9:             luf->new_sva = luf->sv_size + luf->sv_size;
alpar@9:             xassert(luf->new_sva > luf->sv_size);
alpar@9:             ret = FHV_EROOM;
alpar@9:             goto done;
alpar@9:          }
alpar@9:       }
alpar@9:       /* add new elements to i-th row list */
alpar@9:       i_ptr = vr_ptr[i];
alpar@9:       memmove(&sv_ind[i_ptr], &cc_ind[1], len * sizeof(int));
alpar@9:       memmove(&sv_val[i_ptr], &cc_val[1], len * sizeof(double));
alpar@9:       vr_len[i] = len;
alpar@9:       luf->nnz_v += len;
alpar@9:       /* updating is finished; check that diagonal element u[k2,k2] is
alpar@9:          not very small in absolute value among other elements in k2-th
alpar@9:          row and k2-th column of matrix U = P*V*Q */
alpar@9:       /* temp = max(|u[k2,*]|, |u[*,k2]|) */
alpar@9:       temp = 0.0;
alpar@9:       /* walk through k2-th row of U which is i-th row of V */
alpar@9:       i = pp_row[k2];
alpar@9:       i_beg = vr_ptr[i];
alpar@9:       i_end = i_beg + vr_len[i] - 1;
alpar@9:       for (i_ptr = i_beg; i_ptr <= i_end; i_ptr++)
alpar@9:          if (temp < fabs(sv_val[i_ptr])) temp = fabs(sv_val[i_ptr]);
alpar@9:       /* walk through k2-th column of U which is j-th column of V */
alpar@9:       j = qq_col[k2];
alpar@9:       j_beg = vc_ptr[j];
alpar@9:       j_end = j_beg + vc_len[j] - 1;
alpar@9:       for (j_ptr = j_beg; j_ptr <= j_end; j_ptr++)
alpar@9:          if (temp < fabs(sv_val[j_ptr])) temp = fabs(sv_val[j_ptr]);
alpar@9:       /* check that u[k2,k2] is not very small */
alpar@9:       if (fabs(vr_piv[i]) < upd_tol * temp)
alpar@9:       {  /* the factorization seems to be inaccurate and therefore must
alpar@9:             be recomputed */
alpar@9:          fhv->valid = 0;
alpar@9:          ret = FHV_ECHECK;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       /* the factorization has been successfully updated */
alpar@9:       ret = 0;
alpar@9: done: /* return to the calling program */
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  fhv_delete_it - delete LP basis factorization
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpfhv.h"
alpar@9: *  void fhv_delete_it(FHV *fhv);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine fhv_delete_it deletes LP basis factorization specified
alpar@9: *  by the parameter fhv and frees all memory allocated to this program
alpar@9: *  object. */
alpar@9: 
alpar@9: void fhv_delete_it(FHV *fhv)
alpar@9: {     luf_delete_it(fhv->luf);
alpar@9:       if (fhv->hh_ind != NULL) xfree(fhv->hh_ind);
alpar@9:       if (fhv->hh_ptr != NULL) xfree(fhv->hh_ptr);
alpar@9:       if (fhv->hh_len != NULL) xfree(fhv->hh_len);
alpar@9:       if (fhv->p0_row != NULL) xfree(fhv->p0_row);
alpar@9:       if (fhv->p0_col != NULL) xfree(fhv->p0_col);
alpar@9:       if (fhv->cc_ind != NULL) xfree(fhv->cc_ind);
alpar@9:       if (fhv->cc_val != NULL) xfree(fhv->cc_val);
alpar@9:       xfree(fhv);
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: /* eof */