MatrixLogarithm.h
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2011, 2013 Jitse Niesen <jitse@maths.leeds.ac.uk>
00005 // Copyright (C) 2011 Chen-Pang He <jdh8@ms63.hinet.net>
00006 //
00007 // This Source Code Form is subject to the terms of the Mozilla
00008 // Public License v. 2.0. If a copy of the MPL was not distributed
00009 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
00010 
00011 #ifndef EIGEN_MATRIX_LOGARITHM
00012 #define EIGEN_MATRIX_LOGARITHM
00013 
00014 namespace Eigen { 
00015 
00016 namespace internal { 
00017 
00018 template <typename Scalar>
00019 struct matrix_log_min_pade_degree 
00020 {
00021   static const int value = 3;
00022 };
00023 
00024 template <typename Scalar>
00025 struct matrix_log_max_pade_degree 
00026 {
00027   typedef typename NumTraits<Scalar>::Real RealScalar;
00028   static const int value = std::numeric_limits<RealScalar>::digits<= 24?  5:  // single precision
00029                            std::numeric_limits<RealScalar>::digits<= 53?  7:  // double precision
00030                            std::numeric_limits<RealScalar>::digits<= 64?  8:  // extended precision
00031                            std::numeric_limits<RealScalar>::digits<=106? 10:  // double-double
00032                                                                          11;  // quadruple precision
00033 };
00034 
00036 template <typename MatrixType>
00037 void matrix_log_compute_2x2(const MatrixType& A, MatrixType& result)
00038 {
00039   typedef typename MatrixType::Scalar Scalar;
00040   typedef typename MatrixType::RealScalar RealScalar;
00041   using std::abs;
00042   using std::ceil;
00043   using std::imag;
00044   using std::log;
00045 
00046   Scalar logA00 = log(A(0,0));
00047   Scalar logA11 = log(A(1,1));
00048 
00049   result(0,0) = logA00;
00050   result(1,0) = Scalar(0);
00051   result(1,1) = logA11;
00052 
00053   Scalar y = A(1,1) - A(0,0);
00054   if (y==Scalar(0))
00055   {
00056     result(0,1) = A(0,1) / A(0,0);
00057   }
00058   else if ((abs(A(0,0)) < RealScalar(0.5)*abs(A(1,1))) || (abs(A(0,0)) > 2*abs(A(1,1))))
00059   {
00060     result(0,1) = A(0,1) * (logA11 - logA00) / y;
00061   }
00062   else
00063   {
00064     // computation in previous branch is inaccurate if A(1,1) \approx A(0,0)
00065     int unwindingNumber = static_cast<int>(ceil((imag(logA11 - logA00) - RealScalar(EIGEN_PI)) / RealScalar(2*EIGEN_PI)));
00066     result(0,1) = A(0,1) * (numext::log1p(y/A(0,0)) + Scalar(0,2*EIGEN_PI*unwindingNumber)) / y;
00067   }
00068 }
00069 
00070 /* \brief Get suitable degree for Pade approximation. (specialized for RealScalar = float) */
00071 inline int matrix_log_get_pade_degree(float normTminusI)
00072 {
00073   const float maxNormForPade[] = { 2.5111573934555054e-1 /* degree = 3 */ , 4.0535837411880493e-1,
00074             5.3149729967117310e-1 };
00075   const int minPadeDegree = matrix_log_min_pade_degree<float>::value;
00076   const int maxPadeDegree = matrix_log_max_pade_degree<float>::value;
00077   int degree = minPadeDegree;
00078   for (; degree <= maxPadeDegree; ++degree) 
00079     if (normTminusI <= maxNormForPade[degree - minPadeDegree])
00080       break;
00081   return degree;
00082 }
00083 
00084 /* \brief Get suitable degree for Pade approximation. (specialized for RealScalar = double) */
00085 inline int matrix_log_get_pade_degree(double normTminusI)
00086 {
00087   const double maxNormForPade[] = { 1.6206284795015624e-2 /* degree = 3 */ , 5.3873532631381171e-2,
00088             1.1352802267628681e-1, 1.8662860613541288e-1, 2.642960831111435e-1 };
00089   const int minPadeDegree = matrix_log_min_pade_degree<double>::value;
00090   const int maxPadeDegree = matrix_log_max_pade_degree<double>::value;
00091   int degree = minPadeDegree;
00092   for (; degree <= maxPadeDegree; ++degree)
00093     if (normTminusI <= maxNormForPade[degree - minPadeDegree])
00094       break;
00095   return degree;
00096 }
00097 
00098 /* \brief Get suitable degree for Pade approximation. (specialized for RealScalar = long double) */
00099 inline int matrix_log_get_pade_degree(long double normTminusI)
00100 {
00101 #if   LDBL_MANT_DIG == 53         // double precision
00102   const long double maxNormForPade[] = { 1.6206284795015624e-2L /* degree = 3 */ , 5.3873532631381171e-2L,
00103             1.1352802267628681e-1L, 1.8662860613541288e-1L, 2.642960831111435e-1L };
00104 #elif LDBL_MANT_DIG <= 64         // extended precision
00105   const long double maxNormForPade[] = { 5.48256690357782863103e-3L /* degree = 3 */, 2.34559162387971167321e-2L,
00106             5.84603923897347449857e-2L, 1.08486423756725170223e-1L, 1.68385767881294446649e-1L,
00107             2.32777776523703892094e-1L };
00108 #elif LDBL_MANT_DIG <= 106        // double-double
00109   const long double maxNormForPade[] = { 8.58970550342939562202529664318890e-5L /* degree = 3 */,
00110             9.34074328446359654039446552677759e-4L, 4.26117194647672175773064114582860e-3L,
00111             1.21546224740281848743149666560464e-2L, 2.61100544998339436713088248557444e-2L,
00112             4.66170074627052749243018566390567e-2L, 7.32585144444135027565872014932387e-2L,
00113             1.05026503471351080481093652651105e-1L };
00114 #else                             // quadruple precision
00115   const long double maxNormForPade[] = { 4.7419931187193005048501568167858103e-5L /* degree = 3 */,
00116             5.8853168473544560470387769480192666e-4L, 2.9216120366601315391789493628113520e-3L,
00117             8.8415758124319434347116734705174308e-3L, 1.9850836029449446668518049562565291e-2L,
00118             3.6688019729653446926585242192447447e-2L, 5.9290962294020186998954055264528393e-2L,
00119             8.6998436081634343903250580992127677e-2L, 1.1880960220216759245467951592883642e-1L };
00120 #endif
00121   const int minPadeDegree = matrix_log_min_pade_degree<long double>::value;
00122   const int maxPadeDegree = matrix_log_max_pade_degree<long double>::value;
00123   int degree = minPadeDegree;
00124   for (; degree <= maxPadeDegree; ++degree)
00125     if (normTminusI <= maxNormForPade[degree - minPadeDegree])
00126       break;
00127   return degree;
00128 }
00129 
00130 /* \brief Compute Pade approximation to matrix logarithm */
00131 template <typename MatrixType>
00132 void matrix_log_compute_pade(MatrixType& result, const MatrixType& T, int degree)
00133 {
00134   typedef typename NumTraits<typename MatrixType::Scalar>::Real RealScalar;
00135   const int minPadeDegree = 3;
00136   const int maxPadeDegree = 11;
00137   assert(degree >= minPadeDegree && degree <= maxPadeDegree);
00138 
00139   const RealScalar nodes[][maxPadeDegree] = { 
00140     { 0.1127016653792583114820734600217600L, 0.5000000000000000000000000000000000L,  // degree 3
00141       0.8872983346207416885179265399782400L }, 
00142     { 0.0694318442029737123880267555535953L, 0.3300094782075718675986671204483777L,  // degree 4
00143       0.6699905217924281324013328795516223L, 0.9305681557970262876119732444464048L },
00144     { 0.0469100770306680036011865608503035L, 0.2307653449471584544818427896498956L,  // degree 5
00145       0.5000000000000000000000000000000000L, 0.7692346550528415455181572103501044L,
00146       0.9530899229693319963988134391496965L },
00147     { 0.0337652428984239860938492227530027L, 0.1693953067668677431693002024900473L,  // degree 6
00148       0.3806904069584015456847491391596440L, 0.6193095930415984543152508608403560L,
00149       0.8306046932331322568306997975099527L, 0.9662347571015760139061507772469973L },
00150     { 0.0254460438286207377369051579760744L, 0.1292344072003027800680676133596058L,  // degree 7
00151       0.2970774243113014165466967939615193L, 0.5000000000000000000000000000000000L,
00152       0.7029225756886985834533032060384807L, 0.8707655927996972199319323866403942L,
00153       0.9745539561713792622630948420239256L },
00154     { 0.0198550717512318841582195657152635L, 0.1016667612931866302042230317620848L,  // degree 8
00155       0.2372337950418355070911304754053768L, 0.4082826787521750975302619288199080L,
00156       0.5917173212478249024697380711800920L, 0.7627662049581644929088695245946232L,
00157       0.8983332387068133697957769682379152L, 0.9801449282487681158417804342847365L },
00158     { 0.0159198802461869550822118985481636L, 0.0819844463366821028502851059651326L,  // degree 9
00159       0.1933142836497048013456489803292629L, 0.3378732882980955354807309926783317L,
00160       0.5000000000000000000000000000000000L, 0.6621267117019044645192690073216683L,
00161       0.8066857163502951986543510196707371L, 0.9180155536633178971497148940348674L,
00162       0.9840801197538130449177881014518364L },
00163     { 0.0130467357414141399610179939577740L, 0.0674683166555077446339516557882535L,  // degree 10
00164       0.1602952158504877968828363174425632L, 0.2833023029353764046003670284171079L,
00165       0.4255628305091843945575869994351400L, 0.5744371694908156054424130005648600L,
00166       0.7166976970646235953996329715828921L, 0.8397047841495122031171636825574368L,
00167       0.9325316833444922553660483442117465L, 0.9869532642585858600389820060422260L },
00168     { 0.0108856709269715035980309994385713L, 0.0564687001159523504624211153480364L,  // degree 11
00169       0.1349239972129753379532918739844233L, 0.2404519353965940920371371652706952L,
00170       0.3652284220238275138342340072995692L, 0.5000000000000000000000000000000000L,
00171       0.6347715779761724861657659927004308L, 0.7595480646034059079628628347293048L,
00172       0.8650760027870246620467081260155767L, 0.9435312998840476495375788846519636L,
00173       0.9891143290730284964019690005614287L } };
00174 
00175   const RealScalar weights[][maxPadeDegree] = { 
00176     { 0.2777777777777777777777777777777778L, 0.4444444444444444444444444444444444L,  // degree 3
00177       0.2777777777777777777777777777777778L },
00178     { 0.1739274225687269286865319746109997L, 0.3260725774312730713134680253890003L,  // degree 4
00179       0.3260725774312730713134680253890003L, 0.1739274225687269286865319746109997L },
00180     { 0.1184634425280945437571320203599587L, 0.2393143352496832340206457574178191L,  // degree 5
00181       0.2844444444444444444444444444444444L, 0.2393143352496832340206457574178191L,
00182       0.1184634425280945437571320203599587L },
00183     { 0.0856622461895851725201480710863665L, 0.1803807865240693037849167569188581L,  // degree 6
00184       0.2339569672863455236949351719947755L, 0.2339569672863455236949351719947755L,
00185       0.1803807865240693037849167569188581L, 0.0856622461895851725201480710863665L },
00186     { 0.0647424830844348466353057163395410L, 0.1398526957446383339507338857118898L,  // degree 7
00187       0.1909150252525594724751848877444876L, 0.2089795918367346938775510204081633L,
00188       0.1909150252525594724751848877444876L, 0.1398526957446383339507338857118898L,
00189       0.0647424830844348466353057163395410L },
00190     { 0.0506142681451881295762656771549811L, 0.1111905172266872352721779972131204L,  // degree 8
00191       0.1568533229389436436689811009933007L, 0.1813418916891809914825752246385978L,
00192       0.1813418916891809914825752246385978L, 0.1568533229389436436689811009933007L,
00193       0.1111905172266872352721779972131204L, 0.0506142681451881295762656771549811L },
00194     { 0.0406371941807872059859460790552618L, 0.0903240803474287020292360156214564L,  // degree 9
00195       0.1303053482014677311593714347093164L, 0.1561735385200014200343152032922218L,
00196       0.1651196775006298815822625346434870L, 0.1561735385200014200343152032922218L,
00197       0.1303053482014677311593714347093164L, 0.0903240803474287020292360156214564L,
00198       0.0406371941807872059859460790552618L },
00199     { 0.0333356721543440687967844049466659L, 0.0747256745752902965728881698288487L,  // degree 10
00200       0.1095431812579910219977674671140816L, 0.1346333596549981775456134607847347L,
00201       0.1477621123573764350869464973256692L, 0.1477621123573764350869464973256692L,
00202       0.1346333596549981775456134607847347L, 0.1095431812579910219977674671140816L,
00203       0.0747256745752902965728881698288487L, 0.0333356721543440687967844049466659L },
00204     { 0.0278342835580868332413768602212743L, 0.0627901847324523123173471496119701L,  // degree 11
00205       0.0931451054638671257130488207158280L, 0.1165968822959952399592618524215876L,
00206       0.1314022722551233310903444349452546L, 0.1364625433889503153572417641681711L,
00207       0.1314022722551233310903444349452546L, 0.1165968822959952399592618524215876L,
00208       0.0931451054638671257130488207158280L, 0.0627901847324523123173471496119701L,
00209       0.0278342835580868332413768602212743L } };
00210 
00211   MatrixType TminusI = T - MatrixType::Identity(T.rows(), T.rows());
00212   result.setZero(T.rows(), T.rows());
00213   for (int k = 0; k < degree; ++k) {
00214     RealScalar weight = weights[degree-minPadeDegree][k];
00215     RealScalar node = nodes[degree-minPadeDegree][k];
00216     result += weight * (MatrixType::Identity(T.rows(), T.rows()) + node * TminusI)
00217                        .template triangularView<Upper>().solve(TminusI);
00218   }
00219 } 
00220 
00223 template <typename MatrixType>
00224 void matrix_log_compute_big(const MatrixType& A, MatrixType& result)
00225 {
00226   typedef typename MatrixType::Scalar Scalar;
00227   typedef typename NumTraits<Scalar>::Real RealScalar;
00228   using std::pow;
00229 
00230   int numberOfSquareRoots = 0;
00231   int numberOfExtraSquareRoots = 0;
00232   int degree;
00233   MatrixType T = A, sqrtT;
00234 
00235   int maxPadeDegree = matrix_log_max_pade_degree<Scalar>::value;
00236   const RealScalar maxNormForPade = maxPadeDegree<= 5? 5.3149729967117310e-1L:                    // single precision
00237                                     maxPadeDegree<= 7? 2.6429608311114350e-1L:                    // double precision
00238                                     maxPadeDegree<= 8? 2.32777776523703892094e-1L:                // extended precision
00239                                     maxPadeDegree<=10? 1.05026503471351080481093652651105e-1L:    // double-double
00240                                                        1.1880960220216759245467951592883642e-1L;  // quadruple precision
00241 
00242   while (true) {
00243     RealScalar normTminusI = (T - MatrixType::Identity(T.rows(), T.rows())).cwiseAbs().colwise().sum().maxCoeff();
00244     if (normTminusI < maxNormForPade) {
00245       degree = matrix_log_get_pade_degree(normTminusI);
00246       int degree2 = matrix_log_get_pade_degree(normTminusI / RealScalar(2));
00247       if ((degree - degree2 <= 1) || (numberOfExtraSquareRoots == 1)) 
00248         break;
00249       ++numberOfExtraSquareRoots;
00250     }
00251     matrix_sqrt_triangular(T, sqrtT);
00252     T = sqrtT.template triangularView<Upper>();
00253     ++numberOfSquareRoots;
00254   }
00255 
00256   matrix_log_compute_pade(result, T, degree);
00257   result *= pow(RealScalar(2), numberOfSquareRoots);
00258 }
00259 
00268 template <typename MatrixType>
00269 class MatrixLogarithmAtomic
00270 {
00271 public:
00276   MatrixType compute(const MatrixType& A);
00277 };
00278 
00279 template <typename MatrixType>
00280 MatrixType MatrixLogarithmAtomic<MatrixType>::compute(const MatrixType& A)
00281 {
00282   using std::log;
00283   MatrixType result(A.rows(), A.rows());
00284   if (A.rows() == 1)
00285     result(0,0) = log(A(0,0));
00286   else if (A.rows() == 2)
00287     matrix_log_compute_2x2(A, result);
00288   else
00289     matrix_log_compute_big(A, result);
00290   return result;
00291 }
00292 
00293 } // end of namespace internal
00294 
00307 template<typename Derived> class MatrixLogarithmReturnValue
00308 : public ReturnByValue<MatrixLogarithmReturnValue<Derived> >
00309 {
00310 public:
00311   typedef typename Derived::Scalar Scalar;
00312   typedef typename Derived::Index Index;
00313 
00314 protected:
00315   typedef typename internal::ref_selector<Derived>::type DerivedNested;
00316 
00317 public:
00318 
00323   explicit MatrixLogarithmReturnValue(const Derived& A) : m_A(A) { }
00324   
00329   template <typename ResultType>
00330   inline void evalTo(ResultType& result) const
00331   {
00332     typedef typename internal::nested_eval<Derived, 10>::type DerivedEvalType;
00333     typedef typename internal::remove_all<DerivedEvalType>::type DerivedEvalTypeClean;
00334     typedef internal::traits<DerivedEvalTypeClean> Traits;
00335     static const int RowsAtCompileTime = Traits::RowsAtCompileTime;
00336     static const int ColsAtCompileTime = Traits::ColsAtCompileTime;
00337     typedef std::complex<typename NumTraits<Scalar>::Real> ComplexScalar;
00338     typedef Matrix<ComplexScalar, Dynamic, Dynamic, 0, RowsAtCompileTime, ColsAtCompileTime> DynMatrixType;
00339     typedef internal::MatrixLogarithmAtomic<DynMatrixType> AtomicType;
00340     AtomicType atomic;
00341     
00342     internal::matrix_function_compute<DerivedEvalTypeClean>::run(m_A, atomic, result);
00343   }
00344 
00345   Index rows() const { return m_A.rows(); }
00346   Index cols() const { return m_A.cols(); }
00347   
00348 private:
00349   const DerivedNested m_A;
00350 };
00351 
00352 namespace internal {
00353   template<typename Derived>
00354   struct traits<MatrixLogarithmReturnValue<Derived> >
00355   {
00356     typedef typename Derived::PlainObject ReturnType;
00357   };
00358 }
00359 
00360 
00361 /********** MatrixBase method **********/
00362 
00363 
00364 template <typename Derived>
00365 const MatrixLogarithmReturnValue<Derived> MatrixBase<Derived>::log() const
00366 {
00367   eigen_assert(rows() == cols());
00368   return MatrixLogarithmReturnValue<Derived>(derived());
00369 }
00370 
00371 } // end namespace Eigen
00372 
00373 #endif // EIGEN_MATRIX_LOGARITHM
 All Classes Functions Variables Typedefs Enumerator