00001
00002
00003
00004
00005
00006
00007
00008
00009 #ifndef CoinSimpFactorization_H
00010 #define CoinSimpFactorization_H
00011
00012 #include <iostream>
00013 #include <string>
00014 #include <cassert>
00015 #include "CoinFinite.hpp"
00016 #include "CoinIndexedVector.hpp"
00017 #include "CoinDenseFactorization.hpp"
00018 class CoinPackedMatrix;
00019
00020
00022 class FactorPointers{
00023 public:
00024 double *rowMax;
00025 int *firstRowKnonzeros;
00026 int *prevRow;
00027 int *nextRow;
00028 int *firstColKnonzeros;
00029 int *prevColumn;
00030 int *nextColumn;
00031 int *newCols;
00032
00033 FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
00034
00035 ~ FactorPointers();
00036 };
00037
00038 class CoinSimpFactorization : public CoinSmallFactorization {
00039 friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir );
00040
00041 public:
00042
00045
00046 CoinSimpFactorization ( );
00048 CoinSimpFactorization ( const CoinSimpFactorization &other);
00049
00051 virtual ~CoinSimpFactorization ( );
00053 CoinSimpFactorization & operator = ( const CoinSimpFactorization & other );
00055 virtual CoinSmallFactorization * clone() const ;
00057
00060
00061 virtual void getAreas ( int numberRows,
00062 int numberColumns,
00063 CoinBigIndex maximumL,
00064 CoinBigIndex maximumU );
00065
00067 virtual void preProcess ( );
00073 virtual int factor ( );
00075 virtual void postProcess(const int * sequence, int * pivotVariable);
00077 virtual void makeNonSingular(int * sequence, int numberColumns);
00079
00082
00083 virtual inline int numberElements ( ) const {
00084 return numberRows_*(numberColumns_+numberPivots_);
00085 }
00087 double maximumCoefficient() const;
00089
00092
00100 virtual int replaceColumn ( CoinIndexedVector * regionSparse,
00101 int pivotRow,
00102 double pivotCheck ,
00103 bool checkBeforeModifying=false);
00105
00116 virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
00117 CoinIndexedVector * regionSparse2,
00118 bool noPermute=false);
00119
00122 virtual int updateColumn ( CoinIndexedVector * regionSparse,
00123 CoinIndexedVector * regionSparse2,
00124 bool noPermute=false) const;
00126 virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
00127 CoinIndexedVector * regionSparse2,
00128 CoinIndexedVector * regionSparse3,
00129 bool noPermute=false);
00131 int upColumn ( CoinIndexedVector * regionSparse,
00132 CoinIndexedVector * regionSparse2,
00133 bool noPermute=false, bool save=false) const;
00138 virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
00139 CoinIndexedVector * regionSparse2) const;
00141 int upColumnTranspose ( CoinIndexedVector * regionSparse,
00142 CoinIndexedVector * regionSparse2) const;
00144
00145
00149
00150 inline void clearArrays()
00151 { gutsOfDestructor();}
00153 inline int * indices() const
00154 { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
00156 virtual inline int * permute() const
00157 { return pivotRow_;}
00159
00161 void gutsOfDestructor();
00163 void gutsOfInitialize();
00165 void gutsOfCopy(const CoinSimpFactorization &other);
00166
00167
00169 void factorize(int numberOfRows,
00170 int numberOfColumns,
00171 const int colStarts[],
00172 const int indicesRow[],
00173 const double elements[]);
00175 int mainLoopFactor (FactorPointers &pointers );
00177 void copyLbyRows();
00179 void copyUbyColumns();
00181 int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
00183 int findPivotShCol(FactorPointers &pointers, int &r, int &s);
00185 int findPivotSimp(FactorPointers &pointers, int &r, int &s);
00187 void GaussEliminate(FactorPointers &pointers, int &r, int &s);
00189 int findShortRow(const int column, const int length, int &minRow,
00190 int &minRowLength, FactorPointers &pointers);
00192 int findShortColumn(const int row, const int length, int &minCol,
00193 int &minColLength, FactorPointers &pointers);
00195 double findMaxInRrow(const int row, FactorPointers &pointers);
00197 void pivoting(const int pivotRow, const int pivotColumn,
00198 const double invPivot, FactorPointers &pointers);
00200 void updateCurrentRow(const int pivotRow, const int row,
00201 const double multiplier, FactorPointers &pointers,
00202 int &newNonZeros);
00204 void increaseLsize();
00206 void increaseRowSize(const int row, const int newSize);
00208 void increaseColSize(const int column, const int newSize, const bool b);
00210 void enlargeUrow(const int numNewElements);
00212 void enlargeUcol(const int numNewElements, const bool b);
00214 int findInRow(const int row, const int column);
00216 int findInColumn(const int column, const int row);
00218 void removeRowFromActSet(const int row, FactorPointers &pointers);
00220 void removeColumnFromActSet(const int column, FactorPointers &pointers);
00222 void allocateSpaceForU();
00224 void allocateSomeArrays();
00226 void initialSomeNumbers();
00228 void Lxeqb(double *b) const;
00230 void Lxeqb2(double *b1, double *b2) const;
00232 void Uxeqb(double *b, double *sol) const;
00234 void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
00236 void xLeqb(double *b) const;
00238 void xUeqb(double *b, double *sol) const;
00240 int LUupdate(int newBasicCol);
00242 void newEta(int row, int numNewElements);
00244 void copyRowPermutations();
00246 void Hxeqb(double *b) const;
00248 void Hxeqb2(double *b1, double *b2) const;
00250 void xHeqb(double *b) const;
00252 void ftran(double *b, double *sol, bool save) const;
00254 void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
00256 void btran(double *b, double *sol) const;
00258
00259
00260
00262 protected:
00265 int checkPivot(double saveFromU, double oldPivot) const;
00267 protected:
00268
00271
00272 double *denseVector_;
00274 double *workArea2_;
00276 double *workArea3_;
00278 int *vecLabels_;
00280 int *indVector_;
00281
00283 double *auxVector_;
00285 int *auxInd_;
00286
00288 double *vecKeep_;
00290 int *indKeep_;
00292 mutable int keepSize_;
00293
00294
00295
00297 int *LrowStarts_;
00299 int *LrowLengths_;
00301 double *Lrows_;
00303 int *LrowInd_;
00305 int LrowSize_;
00307 int LrowCap_;
00308
00310 int *LcolStarts_;
00312 int *LcolLengths_;
00314 double *Lcolumns_;
00316 int *LcolInd_;
00318 int LcolSize_;
00320 int LcolCap_;
00321
00322
00324 int *UrowStarts_;
00326 int *UrowLengths_;
00327 #ifdef COIN_SIMP_CAPACITY
00329 int *UrowCapacities_;
00330 #endif
00332 double *Urows_;
00334 int *UrowInd_;
00336 int UrowMaxCap_;
00338 int UrowEnd_;
00340 int firstRowInU_;
00342 int lastRowInU_;
00344 int *prevRowInU_;
00346 int *nextRowInU_;
00347
00349 int *UcolStarts_;
00351 int *UcolLengths_;
00352 #ifdef COIN_SIMP_CAPACITY
00354 int *UcolCapacities_;
00355 #endif
00357 double *Ucolumns_;
00359 int *UcolInd_;
00361 int *prevColInU_;
00363 int *nextColInU_;
00365 int firstColInU_;
00367 int lastColInU_;
00369 int UcolMaxCap_;
00371 int UcolEnd_;
00373 int *colSlack_;
00374
00376 double *invOfPivots_;
00377
00379 int *colOfU_;
00381 int *colPosition_;
00383 int *rowOfU_;
00385 int *rowPosition_;
00387 int *secRowOfU_;
00389 int *secRowPosition_;
00390
00392 int *EtaPosition_;
00394 int *EtaStarts_;
00396 int *EtaLengths_;
00398 int *EtaInd_;
00400 double *Eta_;
00402 int EtaSize_;
00404 int lastEtaRow_;
00406 int maxEtaRows_;
00408 int EtaMaxCap_;
00409
00411 int minIncrease_;
00413 double updateTol_;
00415 bool doSuhlHeuristic_;
00417 double maxU_;
00419 double maxGrowth_;
00421 double maxA_;
00423 int pivotCandLimit_;
00425 int numberSlacks_;
00427 int firstNumberSlacks_;
00429 };
00430 #endif
