latest version v1.9 - last update 10 Apr 2010 |
00001 /* 00002 * Copyright (C) 2003, 2004, 2005, 2006 00003 * Lehrstuhl fuer Technische Informatik, RWTH-Aachen, Germany 00004 * 00005 * This file is part of the LTI-Computer Vision Library (LTI-Lib) 00006 * 00007 * The LTI-Lib is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU Lesser General Public License (LGPL) 00009 * as published by the Free Software Foundation; either version 2.1 of 00010 * the License, or (at your option) any later version. 00011 * 00012 * The LTI-Lib is distributed in the hope that it will be 00013 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 00014 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public 00018 * License along with the LTI-Lib; see the file LICENSE. If 00019 * not, write to the Free Software Foundation, Inc., 59 Temple Place - 00020 * Suite 330, Boston, MA 02111-1307, USA. 00021 */ 00022 00023 00024 /*-------------------------------------------------------------------- 00025 * project ....: LTI-Lib: Image Processing and Computer Vision Library 00026 * file .......: ltiForwardSubstitution.h 00027 * authors ....: Peter Doerfler 00028 * organization: LTI, RWTH Aachen 00029 * creation ...: 20.5.2003 00030 * revisions ..: $Id: ltiForwardSubstitution.h,v 1.9 2006/02/08 12:22:12 ltilib Exp $ 00031 */ 00032 00033 #ifndef _LTI_FORWARD_SUBSTITUTION_H_ 00034 #define _LTI_FORWARD_SUBSTITUTION_H_ 00035 00036 #include "ltiLinearAlgebraFunctor.h" 00037 #include "ltiVector.h" 00038 #include "ltiMatrix.h" 00039 #include "ltiTriangularMatrixType.h" 00040 00041 namespace lti { 00042 /** 00043 * Forward substitution. Let \a L be a lower triangular matrix and 00044 * \a U an upper triangular matrix. Forward substitution solves the 00045 * following linear equation systems for \a x: 00046 * 00047 * L*x=b or x*U=b 00048 * 00049 * In the first case, \a x and \a b are column vectors, in the latter 00050 * case they are row vectors. The data %matrix can be given to the 00051 * functor via the parameters or directly in the apply 00052 * methods. There are also apply methods that calculate the forward 00053 * substitution for multiple right-sides \a b. The vectors are 00054 * treated as before, ie they are in columns for the first case and 00055 * in rows for the second. 00056 * 00057 * \b Note that the column vector matrix will be transposed twice 00058 * and thus takes longer to compute, try to use the vector-apply 00059 * instead. 00060 * 00061 * @see lti::backSubstitution 00062 */ 00063 template<class T> 00064 class forwardSubstitution : public linearAlgebraFunctor { 00065 public: 00066 /** 00067 * the parameters for the class forwardSubstitution 00068 */ 00069 class parameters 00070 : public linearAlgebraFunctor::parameters, 00071 virtual public triangularMatrixType { 00072 public: 00073 00074 /** 00075 * default constructor. The triangularType is Lower by default. 00076 */ 00077 parameters() : linearAlgebraFunctor::parameters(), theMatrix() { 00078 //TODO: Initialize your parameter values! 00079 // If you add more parameters manually, do not forget to do following: 00080 // 1. indicate in the default constructor the default values 00081 // 2. make sure that the copy member also copy your new parameters 00082 // 3. make sure that the read and write members also read and 00083 // write your parameters 00084 00085 triangularType = Lower; 00086 }; 00087 00088 /** 00089 * copy constructor 00090 * @param other the parameters object to be copied 00091 */ 00092 parameters(const parameters& other) : linearAlgebraFunctor::parameters() { 00093 copy(other); 00094 } 00095 00096 /** 00097 * destructor 00098 */ 00099 ~parameters() { 00100 }; 00101 00102 /** 00103 * returns name of this type 00104 */ 00105 const char* getTypeName() const { 00106 return "forwardSubstitution::parameters"; 00107 }; 00108 00109 /** 00110 * copy the contents of a parameters object 00111 * @param other the parameters object to be copied 00112 * @return a reference to this parameters object 00113 */ 00114 parameters& copy(const parameters& other) { 00115 # ifndef _LTI_MSC_6 00116 // MS Visual C++ 6 is not able to compile this... 00117 linearAlgebraFunctor::parameters::copy(other); 00118 # else 00119 // ...so we have to use this workaround. 00120 // Conditional on that, copy may not be virtual. 00121 functor::parameters& (functor::parameters::* p_copy) 00122 (const functor::parameters&) = 00123 functor::parameters::copy; 00124 (this->*p_copy)(other); 00125 # endif 00126 triangularMatrixType::copy(other); 00127 00128 theMatrix.copy(other.theMatrix); 00129 00130 return *this; 00131 }; 00132 00133 /** 00134 * copy the contents of a parameters object 00135 * @param other the parameters object to be copied 00136 * @return a reference to this parameters object 00137 */ 00138 parameters& operator=(const parameters& other) { 00139 return copy(other); 00140 }; 00141 00142 /** 00143 * returns a pointer to a clone of the parameters 00144 */ 00145 virtual functor::parameters* clone() const { 00146 return new parameters(*this); 00147 }; 00148 00149 # ifndef _LTI_MSC_6 00150 /** 00151 * write the parameters in the given ioHandler 00152 * @param handler the ioHandler to be used 00153 * @param complete if true (the default) the enclosing begin/end will 00154 * be also written, otherwise only the data block will be written. 00155 * @return true if write was successful 00156 */ 00157 virtual bool write(ioHandler& handler,const bool complete=true) const 00158 # else 00159 /** 00160 * this function is required by MSVC only, as a workaround for a 00161 * very awful bug, which exists since MSVC V.4.0, and still by 00162 * V.6.0 with all bugfixes (so called "service packs") remains 00163 * there... This method is also public due to another bug, so please 00164 * NEVER EVER call this method directly: use write() instead 00165 */ 00166 bool writeMS(ioHandler& handler,const bool complete=true) const 00167 # endif 00168 { 00169 bool b = true; 00170 if (complete) { 00171 b = handler.writeBegin(); 00172 } 00173 00174 if (b) { 00175 00176 lti::write(handler,"theMatrix", theMatrix); 00177 00178 } 00179 00180 # ifndef _LTI_MSC_6 00181 // This is the standard C++ code, which MS Visual C++ 6 is not able to 00182 // compile... 00183 b = b && linearAlgebraFunctor::parameters::write(handler,false); 00184 # else 00185 bool (linearAlgebraFunctor::parameters::* p_writeMS)(ioHandler&, 00186 const bool) const = 00187 linearAlgebraFunctor::parameters::writeMS; 00188 b = b && (this->*p_writeMS)(handler,false); 00189 # endif 00190 b = b && triangularMatrixType::write(handler,false); 00191 00192 if (complete) { 00193 b = b && handler.writeEnd(); 00194 } 00195 00196 return b; 00197 } 00198 00199 # ifdef _LTI_MSC_6 00200 /** 00201 * write the parameters in the given ioHandler 00202 * @param handler the ioHandler to be used 00203 * @param complete if true (the default) the enclosing begin/end will 00204 * be also written, otherwise only the data block will be written. 00205 * @return true if write was successful 00206 */ 00207 bool write(ioHandler& handler, 00208 const bool complete=true) const { 00209 // ...we need this workaround to cope with another really 00210 // awful MSVC bug. 00211 return writeMS(handler,complete); 00212 } 00213 # endif 00214 00215 00216 # ifndef _LTI_MSC_6 00217 /** 00218 * read the parameters from the given ioHandler 00219 * @param handler the ioHandler to be used 00220 * @param complete if true (the default) the enclosing begin/end will 00221 * be also written, otherwise only the data block will be written. 00222 * @return true if write was successful 00223 */ 00224 virtual bool read(ioHandler& handler,const bool complete=true) 00225 # else 00226 /** 00227 * this function is required by MSVC only, as a workaround for a 00228 * very awful bug, which exists since MSVC V.4.0, and still by 00229 * V.6.0 with all bugfixes (so called "service packs") remains 00230 * there... This method is also public due to another bug, so please 00231 * NEVER EVER call this method directly: use read() instead 00232 */ 00233 bool readMS(ioHandler& handler,const bool complete=true) 00234 # endif 00235 { 00236 bool b = true; 00237 if (complete) { 00238 b = handler.readBegin(); 00239 } 00240 00241 if (b) { 00242 00243 lti::read(handler,"theMatrix", theMatrix); 00244 } 00245 00246 # ifndef _LTI_MSC_6 00247 // This is the standard C++ code, which MS Visual C++ 6 is not 00248 // able to compile... 00249 b = b && linearAlgebraFunctor::parameters::read(handler,false); 00250 # else 00251 bool (linearAlgebraFunctor::parameters::* p_readMS)(ioHandler&, 00252 const bool) = 00253 linearAlgebraFunctor::parameters::readMS; 00254 b = b && (this->*p_readMS)(handler,false); 00255 # endif 00256 b = b && triangularMatrixType::read(handler,false); 00257 00258 if (complete) { 00259 b = b && handler.readEnd(); 00260 } 00261 00262 return b; 00263 } 00264 00265 # ifdef _LTI_MSC_6 00266 /** 00267 * read the parameters from the given ioHandler 00268 * @param handler the ioHandler to be used 00269 * @param complete if true (the default) the enclosing begin/end will 00270 * be also written, otherwise only the data block will be written. 00271 * @return true if write was successful 00272 */ 00273 bool read(ioHandler& handler,const bool complete=true) { 00274 // ...we need this workaround to cope with another really awful MSVC 00275 // bug. 00276 return readMS(handler,complete); 00277 } 00278 # endif 00279 00280 // ------------------------------------------------ 00281 // the parameters 00282 // ------------------------------------------------ 00283 00284 /** 00285 * The data matrix. 00286 */ 00287 matrix<T> theMatrix; 00288 00289 }; 00290 00291 /** 00292 * default constructor 00293 */ 00294 forwardSubstitution(); 00295 00296 /** 00297 * constructor, sets the data matrix and its triangular type in 00298 * the parameters. 00299 * 00300 * \b Note: Using this constructor, the data matrix is copied 00301 * twice (Once to internally put it into a parameters object and 00302 * then when setting the parameters). It can be better to let 00303 * parameters::theMatrix use the data of some matrix you have: 00304 * 00305 * \code 00306 * matrix<double> myData; //let this contain the data 00307 * forwardSubstitution<double>::parameters param; 00308 * param.theMatrix.useExternData(myData.rows(),myData.columns(),&myData.at(0,0)) 00309 * forwardSubstitution<double> mySubst(param); 00310 * \endcode 00311 * 00312 * The fastest method is to use one of the apply-methods where the 00313 * data matrix is an argument. 00314 * 00315 * @param theMatrix the data matrix 00316 * @param tType triangularType of \a theMatrix 00317 */ 00318 forwardSubstitution(const matrix<T>& theMatrix, 00319 const typename parameters::eTriangularType& tType= 00320 parameters::Lower); 00321 00322 /** 00323 * Construct a functor using the given parameters 00324 */ 00325 forwardSubstitution(const parameters& par); 00326 00327 /** 00328 * copy constructor 00329 * @param other the object to be copied 00330 */ 00331 forwardSubstitution(const forwardSubstitution& other); 00332 00333 /** 00334 * destructor 00335 */ 00336 virtual ~forwardSubstitution(); 00337 00338 /** 00339 * returns the name of this type ("forwardSubstitution") 00340 */ 00341 virtual const char* getTypeName() const; 00342 00343 //TODO: comment your apply methods! 00344 00345 00346 /** 00347 * Performs forward substitution with unknown \a x. L*x=b if \a 00348 * theMatrix is lower triagonal and x*U=b if \a theMatrix is upper 00349 * triagonal. The result \a x is left in \a b. The matrix in the 00350 * parameters is used. 00351 * 00352 * @param b the right side of the forward substitution. The result 00353 * will be left here too. 00354 * @return true if apply successful or false otherwise. 00355 */ 00356 bool apply(vector<T>& b) const; 00357 00358 /** 00359 * Performs forward substitution with unknown \a x. L*x=b if \a 00360 * theMatrix is lower triagonal and x*U=b if \a theMatrix is upper 00361 * triagonal. The matrix in the parameters is used. 00362 * 00363 * @param b the right side of the forward substitution. 00364 * @param x the result. 00365 * @return true if apply successful or false otherwise. 00366 */ 00367 bool apply(const vector<T>& b, vector<T>& x) const; 00368 00369 /** 00370 * Performs forward substitution with unknown \a x. L*x=b if \a 00371 * theMatrix is lower triagonal and x*U=b if \a theMatrix is upper 00372 * triagonal. The result \a x is left in \a b. 00373 * 00374 * @param theMatrix data matrix (L or U) 00375 * @param b the right side of the forward substitution. The result 00376 * will be left here too. 00377 * @param tType defines whether theMatrix is lower or upper triangular 00378 * @return true if apply successful or false otherwise. 00379 */ 00380 bool apply(const matrix<T>& theMatrix, vector<T>& b, 00381 const typename parameters::eTriangularType& tType) const; 00382 00383 /** 00384 * Performs forward substitution with unknown \a x. L*x=b if \a 00385 * theMatrix is lower triagonal and x*U=b if \a theMatrix is upper 00386 * triagonal. 00387 * 00388 * @param theMatrix data matrix (L or U) 00389 * @param b the right side of the forward substitution. The result 00390 * will be left here too. 00391 * @param x the result. 00392 * @param tType defines whether theMatrix is lower or upper triangular 00393 * @return true if apply successful or false otherwise. 00394 */ 00395 bool apply(const matrix<T>& theMatrix, const vector<T>& b, 00396 vector<T>& x, const typename parameters::eTriangularType& tType) const; 00397 00398 00399 /** 00400 * Performs forward substitution with unknowns \a X. L*X=B if \a 00401 * theMatrix is lower triagonal and X*U=B if \a theMatrix is upper 00402 * triagonal. In the first case \a X and \a B contain the vectors 00403 * in colums, in the latter case in rows. The result \a x is left 00404 * in \a b. The matrix in the parameters is used. 00405 * 00406 * @param b the right side of the forward substitution. The result 00407 * will be left here too. 00408 * @return true if apply successful or false otherwise. 00409 */ 00410 bool apply(matrix<T>& b) const; 00411 00412 /** 00413 * Performs forward substitution with unknowns \a X. L*X=B if \a 00414 * theMatrix is lower triagonal and X*U=B if \a theMatrix is upper 00415 * triagonal. In the first case \a X and \a B contain the vectors 00416 * in colums, in the latter case in rows. The data matrix in the 00417 * parameters is used. 00418 * 00419 * @param b the right side of the forward substitution. 00420 * @param x the result 00421 * @return true if apply successful or false otherwise. 00422 */ 00423 bool apply(const matrix<T>& b, matrix<T>& x) const; 00424 00425 /** 00426 * Performs forward substitution with unknowns \a X. L*X=B if \a 00427 * theMatrix is lower triagonal and X*U=B if \a theMatrix is upper 00428 * triagonal. In the first case \a X and \a B contain the vectors 00429 * in colums, in the latter case in rows. The result \a x is left 00430 * in \a b. 00431 * 00432 * @param theMatrix data matrix (L or U) 00433 * @param b the right side of the forward substitution. The result 00434 * will be left here too. 00435 * @param tType defines whether theMatrix is lower or upper triangular 00436 * @return true if apply successful or false otherwise. 00437 */ 00438 bool apply(const matrix<T>& theMatrix, matrix<T>& b, 00439 const typename parameters::eTriangularType& tType) const; 00440 00441 /** 00442 * Performs forward substitution with unknowns \a X. L*X=B if \a 00443 * theMatrix is lower triagonal and X*U=B if \a theMatrix is upper 00444 * triagonal. In the first case \a X and \a B contain the vectors 00445 * in colums, in the latter case in rows. 00446 * 00447 * @param theMatrix data matrix (L or U) 00448 * @param b the right side of the forward substitution. The result 00449 * will be left here too. 00450 * @param x the result 00451 * @param tType defines whether theMatrix is lower or upper triangular 00452 * @return true if apply successful or false otherwise. 00453 */ 00454 bool apply(const matrix<T>& theMatrix, const matrix<T>& b, 00455 matrix<T>& x, const typename parameters::eTriangularType& tType) const; 00456 00457 /** 00458 * copy data of "other" functor. 00459 * @param other the functor to be copied 00460 * @return a reference to this functor object 00461 */ 00462 forwardSubstitution& copy(const forwardSubstitution& other); 00463 00464 /** 00465 * alias for copy member 00466 * @param other the functor to be copied 00467 * @return a reference to this functor object 00468 */ 00469 forwardSubstitution& operator=(const forwardSubstitution& other); 00470 00471 /** 00472 * returns a pointer to a clone of this functor. 00473 */ 00474 virtual functor* clone() const; 00475 00476 /** 00477 * returns used parameters 00478 */ 00479 const parameters& getParameters() const; 00480 00481 //TODO: comment the attributes of your functor 00482 // If you add more attributes manually, do not forget to do following: 00483 // 1. indicate in the default constructor the default values 00484 // 2. make sure that the copy member also copy your new attributes, or 00485 // to ensure there, that these attributes are properly initialized. 00486 00487 }; 00488 } 00489 00490 #endif