00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #ifndef CoinSimpFactorization_H
00011 #define CoinSimpFactorization_H
00012
00013 #include <iostream>
00014 #include <string>
00015 #include <cassert>
00016 #include "CoinFinite.hpp"
00017 #include "CoinIndexedVector.hpp"
00018 #include "CoinDenseFactorization.hpp"
00019 class CoinPackedMatrix;
00020
00021
00023 class FactorPointers{
00024 public:
00025 double *rowMax;
00026 int *firstRowKnonzeros;
00027 int *prevRow;
00028 int *nextRow;
00029 int *firstColKnonzeros;
00030 int *prevColumn;
00031 int *nextColumn;
00032 int *newCols;
00033
00034 FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
00035
00036 ~ FactorPointers();
00037 };
00038
00039 class CoinSimpFactorization : public CoinOtherFactorization {
00040 friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir );
00041
00042 public:
00043
00046
00047 CoinSimpFactorization ( );
00049 CoinSimpFactorization ( const CoinSimpFactorization &other);
00050
00052 virtual ~CoinSimpFactorization ( );
00054 CoinSimpFactorization & operator = ( const CoinSimpFactorization & other );
00056 virtual CoinOtherFactorization * clone() const ;
00058
00061
00062 virtual void getAreas ( int numberRows,
00063 int numberColumns,
00064 CoinBigIndex maximumL,
00065 CoinBigIndex maximumU );
00066
00068 virtual void preProcess ( );
00074 virtual int factor ( );
00076 virtual void postProcess(const int * sequence, int * pivotVariable);
00078 virtual void makeNonSingular(int * sequence, int numberColumns);
00080
00083
00084 virtual inline int numberElements ( ) const {
00085 return numberRows_*(numberColumns_+numberPivots_);
00086 }
00088 double maximumCoefficient() const;
00090
00093
00101 virtual int replaceColumn ( CoinIndexedVector * regionSparse,
00102 int pivotRow,
00103 double pivotCheck ,
00104 bool checkBeforeModifying=false,
00105 double acceptablePivot=1.0e-8);
00107
00118 virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
00119 CoinIndexedVector * regionSparse2,
00120 bool noPermute=false);
00121
00124 virtual int updateColumn ( CoinIndexedVector * regionSparse,
00125 CoinIndexedVector * regionSparse2,
00126 bool noPermute=false) const;
00128 virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
00129 CoinIndexedVector * regionSparse2,
00130 CoinIndexedVector * regionSparse3,
00131 bool noPermute=false);
00133 int upColumn ( CoinIndexedVector * regionSparse,
00134 CoinIndexedVector * regionSparse2,
00135 bool noPermute=false, bool save=false) const;
00140 virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
00141 CoinIndexedVector * regionSparse2) const;
00143 int upColumnTranspose ( CoinIndexedVector * regionSparse,
00144 CoinIndexedVector * regionSparse2) const;
00146
00147
00151
00152 inline void clearArrays()
00153 { gutsOfDestructor();}
00155 inline int * indices() const
00156 { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
00158 virtual inline int * permute() const
00159 { return pivotRow_;}
00161
00163 void gutsOfDestructor();
00165 void gutsOfInitialize();
00167 void gutsOfCopy(const CoinSimpFactorization &other);
00168
00169
00171 void factorize(int numberOfRows,
00172 int numberOfColumns,
00173 const int colStarts[],
00174 const int indicesRow[],
00175 const double elements[]);
00177 int mainLoopFactor (FactorPointers &pointers );
00179 void copyLbyRows();
00181 void copyUbyColumns();
00183 int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
00185 int findPivotShCol(FactorPointers &pointers, int &r, int &s);
00187 int findPivotSimp(FactorPointers &pointers, int &r, int &s);
00189 void GaussEliminate(FactorPointers &pointers, int &r, int &s);
00191 int findShortRow(const int column, const int length, int &minRow,
00192 int &minRowLength, FactorPointers &pointers);
00194 int findShortColumn(const int row, const int length, int &minCol,
00195 int &minColLength, FactorPointers &pointers);
00197 double findMaxInRrow(const int row, FactorPointers &pointers);
00199 void pivoting(const int pivotRow, const int pivotColumn,
00200 const double invPivot, FactorPointers &pointers);
00202 void updateCurrentRow(const int pivotRow, const int row,
00203 const double multiplier, FactorPointers &pointers,
00204 int &newNonZeros);
00206 void increaseLsize();
00208 void increaseRowSize(const int row, const int newSize);
00210 void increaseColSize(const int column, const int newSize, const bool b);
00212 void enlargeUrow(const int numNewElements);
00214 void enlargeUcol(const int numNewElements, const bool b);
00216 int findInRow(const int row, const int column);
00218 int findInColumn(const int column, const int row);
00220 void removeRowFromActSet(const int row, FactorPointers &pointers);
00222 void removeColumnFromActSet(const int column, FactorPointers &pointers);
00224 void allocateSpaceForU();
00226 void allocateSomeArrays();
00228 void initialSomeNumbers();
00230 void Lxeqb(double *b) const;
00232 void Lxeqb2(double *b1, double *b2) const;
00234 void Uxeqb(double *b, double *sol) const;
00236 void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
00238 void xLeqb(double *b) const;
00240 void xUeqb(double *b, double *sol) const;
00242 int LUupdate(int newBasicCol);
00244 void newEta(int row, int numNewElements);
00246 void copyRowPermutations();
00248 void Hxeqb(double *b) const;
00250 void Hxeqb2(double *b1, double *b2) const;
00252 void xHeqb(double *b) const;
00254 void ftran(double *b, double *sol, bool save) const;
00256 void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
00258 void btran(double *b, double *sol) const;
00260
00261
00262
00264 protected:
00267 int checkPivot(double saveFromU, double oldPivot) const;
00269 protected:
00270
00273
00274 double *denseVector_;
00276 double *workArea2_;
00278 double *workArea3_;
00280 int *vecLabels_;
00282 int *indVector_;
00283
00285 double *auxVector_;
00287 int *auxInd_;
00288
00290 double *vecKeep_;
00292 int *indKeep_;
00294 mutable int keepSize_;
00295
00296
00297
00299 int *LrowStarts_;
00301 int *LrowLengths_;
00303 double *Lrows_;
00305 int *LrowInd_;
00307 int LrowSize_;
00309 int LrowCap_;
00310
00312 int *LcolStarts_;
00314 int *LcolLengths_;
00316 double *Lcolumns_;
00318 int *LcolInd_;
00320 int LcolSize_;
00322 int LcolCap_;
00323
00324
00326 int *UrowStarts_;
00328 int *UrowLengths_;
00329 #ifdef COIN_SIMP_CAPACITY
00331 int *UrowCapacities_;
00332 #endif
00334 double *Urows_;
00336 int *UrowInd_;
00338 int UrowMaxCap_;
00340 int UrowEnd_;
00342 int firstRowInU_;
00344 int lastRowInU_;
00346 int *prevRowInU_;
00348 int *nextRowInU_;
00349
00351 int *UcolStarts_;
00353 int *UcolLengths_;
00354 #ifdef COIN_SIMP_CAPACITY
00356 int *UcolCapacities_;
00357 #endif
00359 double *Ucolumns_;
00361 int *UcolInd_;
00363 int *prevColInU_;
00365 int *nextColInU_;
00367 int firstColInU_;
00369 int lastColInU_;
00371 int UcolMaxCap_;
00373 int UcolEnd_;
00375 int *colSlack_;
00376
00378 double *invOfPivots_;
00379
00381 int *colOfU_;
00383 int *colPosition_;
00385 int *rowOfU_;
00387 int *rowPosition_;
00389 int *secRowOfU_;
00391 int *secRowPosition_;
00392
00394 int *EtaPosition_;
00396 int *EtaStarts_;
00398 int *EtaLengths_;
00400 int *EtaInd_;
00402 double *Eta_;
00404 int EtaSize_;
00406 int lastEtaRow_;
00408 int maxEtaRows_;
00410 int EtaMaxCap_;
00411
00413 int minIncrease_;
00415 double updateTol_;
00417 bool doSuhlHeuristic_;
00419 double maxU_;
00421 double maxGrowth_;
00423 double maxA_;
00425 int pivotCandLimit_;
00427 int numberSlacks_;
00429 int firstNumberSlacks_;
00431 };
00432 #endif
