Main MRPT website > C++ reference
MRPT logo

StableNorm.h

Go to the documentation of this file.
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2009 Gael Guennebaud <gael.guennebaud@inria.fr>
00005 //
00006 // Eigen is free software; you can redistribute it and/or
00007 // modify it under the terms of the GNU Lesser General Public
00008 // License as published by the Free Software Foundation; either
00009 // version 3 of the License, or (at your option) any later version.
00010 //
00011 // Alternatively, you can redistribute it and/or
00012 // modify it under the terms of the GNU General Public License as
00013 // published by the Free Software Foundation; either version 2 of
00014 // the License, or (at your option) any later version.
00015 //
00016 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
00017 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00018 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
00019 // GNU General Public License for more details.
00020 //
00021 // You should have received a copy of the GNU Lesser General Public
00022 // License and a copy of the GNU General Public License along with
00023 // Eigen. If not, see <http://www.gnu.org/licenses/>.
00024 
00025 #ifndef EIGEN_STABLENORM_H
00026 #define EIGEN_STABLENORM_H
00027 
00028 namespace internal {
00029 template<typename ExpressionType, typename Scalar>
00030 inline void stable_norm_kernel(const ExpressionType& bl, Scalar& ssq, Scalar& scale, Scalar& invScale)
00031 {
00032   Scalar max = bl.cwiseAbs().maxCoeff();
00033   if (max>scale)
00034   {
00035     ssq = ssq * abs2(scale/max);
00036     scale = max;
00037     invScale = Scalar(1)/scale;
00038   }
00039   // TODO if the max is much much smaller than the current scale,
00040   // then we can neglect this sub vector
00041   ssq += (bl*invScale).squaredNorm();
00042 }
00043 }
00044 
00045 /** \returns the \em l2 norm of \c *this avoiding underflow and overflow.
00046   * This version use a blockwise two passes algorithm:
00047   *  1 - find the absolute largest coefficient \c s
00048   *  2 - compute \f$ s \Vert \frac{*this}{s} \Vert \f$ in a standard way
00049   *
00050   * For architecture/scalar types supporting vectorization, this version
00051   * is faster than blueNorm(). Otherwise the blueNorm() is much faster.
00052   *
00053   * \sa norm(), blueNorm(), hypotNorm()
00054   */
00055 template<typename Derived>
00056 inline typename NumTraits<typename internal::traits<Derived>::Scalar>::Real
00057 MatrixBase<Derived>::stableNorm() const
00058 {
00059   const Index blockSize = 4096;
00060   RealScalar scale = 0;
00061   RealScalar invScale = 1;
00062   RealScalar ssq = 0; // sum of square
00063   enum {
00064     Alignment = (int(Flags)&DirectAccessBit) || (int(Flags)&AlignedBit) ? 1 : 0
00065   };
00066   Index n = size();
00067   Index bi = internal::first_aligned(derived());
00068   if (bi>0)
00069     internal::stable_norm_kernel(this->head(bi), ssq, scale, invScale);
00070   for (; bi<n; bi+=blockSize)
00071     internal::stable_norm_kernel(this->segment(bi,std::min(blockSize, n - bi)).template forceAlignedAccessIf<Alignment>(), ssq, scale, invScale);
00072   return scale * internal::sqrt(ssq);
00073 }
00074 
00075 /** \returns the \em l2 norm of \c *this using the Blue's algorithm.
00076   * A Portable Fortran Program to Find the Euclidean Norm of a Vector,
00077   * ACM TOMS, Vol 4, Issue 1, 1978.
00078   *
00079   * For architecture/scalar types without vectorization, this version
00080   * is much faster than stableNorm(). Otherwise the stableNorm() is faster.
00081   *
00082   * \sa norm(), stableNorm(), hypotNorm()
00083   */
00084 template<typename Derived>
00085 inline typename NumTraits<typename internal::traits<Derived>::Scalar>::Real
00086 MatrixBase<Derived>::blueNorm() const
00087 {
00088   static Index nmax = -1;
00089   static RealScalar b1, b2, s1m, s2m, overfl, rbig, relerr;
00090   if(nmax <= 0)
00091   {
00092     int nbig, ibeta, it, iemin, iemax, iexp;
00093     RealScalar abig, eps;
00094     // This program calculates the machine-dependent constants
00095     // bl, b2, slm, s2m, relerr overfl, nmax
00096     // from the "basic" machine-dependent numbers
00097     // nbig, ibeta, it, iemin, iemax, rbig.
00098     // The following define the basic machine-dependent constants.
00099     // For portability, the PORT subprograms "ilmaeh" and "rlmach"
00100     // are used. For any specific computer, each of the assignment
00101     // statements can be replaced
00102     nbig  = std::numeric_limits<Index>::max();            // largest integer
00103     ibeta = std::numeric_limits<RealScalar>::radix;         // base for floating-point numbers
00104     it    = std::numeric_limits<RealScalar>::digits;        // number of base-beta digits in mantissa
00105     iemin = std::numeric_limits<RealScalar>::min_exponent;  // minimum exponent
00106     iemax = std::numeric_limits<RealScalar>::max_exponent;  // maximum exponent
00107     rbig  = std::numeric_limits<RealScalar>::max();         // largest floating-point number
00108 
00109     iexp  = -((1-iemin)/2);
00110     b1    = RealScalar(std::pow(RealScalar(ibeta),RealScalar(iexp)));  // lower boundary of midrange
00111     iexp  = (iemax + 1 - it)/2;
00112     b2    = RealScalar(std::pow(RealScalar(ibeta),RealScalar(iexp)));   // upper boundary of midrange
00113 
00114     iexp  = (2-iemin)/2;
00115     s1m   = RealScalar(std::pow(RealScalar(ibeta),RealScalar(iexp)));   // scaling factor for lower range
00116     iexp  = - ((iemax+it)/2);
00117     s2m   = RealScalar(std::pow(RealScalar(ibeta),RealScalar(iexp)));   // scaling factor for upper range
00118 
00119     overfl  = rbig*s2m;             // overflow boundary for abig
00120     eps     = RealScalar(std::pow(double(ibeta), 1-it));
00121     relerr  = internal::sqrt(eps);         // tolerance for neglecting asml
00122     abig    = RealScalar(1.0/eps - 1.0);
00123     if (RealScalar(nbig)>abig)  nmax = int(abig);  // largest safe n
00124     else                        nmax = nbig;
00125   }
00126   Index n = size();
00127   RealScalar ab2 = b2 / RealScalar(n);
00128   RealScalar asml = RealScalar(0);
00129   RealScalar amed = RealScalar(0);
00130   RealScalar abig = RealScalar(0);
00131   for(Index j=0; j<n; ++j)
00132   {
00133     RealScalar ax = internal::abs(coeff(j));
00134     if(ax > ab2)     abig += internal::abs2(ax*s2m);
00135     else if(ax < b1) asml += internal::abs2(ax*s1m);
00136     else             amed += internal::abs2(ax);
00137   }
00138   if(abig > RealScalar(0))
00139   {
00140     abig = internal::sqrt(abig);
00141     if(abig > overfl)
00142     {
00143       eigen_assert(false && "overflow");
00144       return rbig;
00145     }
00146     if(amed > RealScalar(0))
00147     {
00148       abig = abig/s2m;
00149       amed = internal::sqrt(amed);
00150     }
00151     else
00152       return abig/s2m;
00153   }
00154   else if(asml > RealScalar(0))
00155   {
00156     if (amed > RealScalar(0))
00157     {
00158       abig = internal::sqrt(amed);
00159       amed = internal::sqrt(asml) / s1m;
00160     }
00161     else
00162       return internal::sqrt(asml)/s1m;
00163   }
00164   else
00165     return internal::sqrt(amed);
00166   asml = std::min(abig, amed);
00167   abig = std::max(abig, amed);
00168   if(asml <= abig*relerr)
00169     return abig;
00170   else
00171     return abig * internal::sqrt(RealScalar(1) + internal::abs2(asml/abig));
00172 }
00173 
00174 /** \returns the \em l2 norm of \c *this avoiding undeflow and overflow.
00175   * This version use a concatenation of hypot() calls, and it is very slow.
00176   *
00177   * \sa norm(), stableNorm()
00178   */
00179 template<typename Derived>
00180 inline typename NumTraits<typename internal::traits<Derived>::Scalar>::Real
00181 MatrixBase<Derived>::hypotNorm() const
00182 {
00183   return this->cwiseAbs().redux(internal::scalar_hypot_op<RealScalar>());
00184 }
00185 
00186 #endif // EIGEN_STABLENORM_H



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011